Difference Algorithm

Dalam penyimpanan data yang terus menerus direvisi (seperti Google Docs), sangatlah tidak efisien untuk menyimpan keseluruhan dokumen setiap waktu. Misalnya jika Joni memiliki dokumen dengan 1000 kata, tetapi ia hanya memperbaiki kalimat, Mari kita semua berak dulu di kantin! menjadi, Mari kita semua break dulu di kantin! Tentunya akan sangat tidak efisien jika revisi kecil seperti ini harus disimpan sebagai sebuah file utuh dalam server. Karena itu komputer cukup mencatat perubahannya. Ketika dokumen dibuka kembali, server akan melakukan komputasi dan menyajikan dokumen hasil.

Dokumen awal

Dokumen awal	Wah, pekerjaan dari tadi tidak habis-habis! Mari kita semua berak dulu di kantin! Sambil makan pisang goreng dan ngopi-ngopi! `...`
Instruksi	Hapus 2 karakter pada posisi 63. Sisipkan re pada posisi 63.
Dokumen hasil	Wah, pekerjaan dari tadi tidak habis-habis! Mari kita semua break dulu di kantin! Sambil makan pisang goreng dan ngopi-ngopi! `...`

Wah, pekerjaan dari tadi tidak habis-habis! Mari kita semua berak dulu di kantin! Sambil makan pisang goreng dan ngopi-ngopi!

...

Instruksi Hapus 2 karakter pada posisi 63. Sisipkan re pada posisi 63.

Dokumen hasil

Wah, pekerjaan dari tadi tidak habis-habis! Mari kita semua break dulu di kantin! Sambil makan pisang goreng dan ngopi-ngopi!

...

Berarti ada dua macam instruksi yang dapat disimpan komputer:

Selain dua instruksi tersebut, ada kalanya kita tidak perlu melakukan edit, jadi kita bisa menambahkan instruksi ketiga, yaitu lewati karakter. Jadi ada 3 macam instruksi yang dapat dilakukan.

Instruksi: Hapus n karakter pada posisi p.; Sisipkan rangkaian karakter s pada posisi p.; Lewati karakter.

Kemudian total edit adalah jumlah total instruksi yang dilakukan (termasuk melewati karakter).

Eksplorasi

Diberikan kalimat, Poki menggigit anjingnya hingga berdarah. Kamu hendak mengeditnya menjadi, Poki menggigit anjingnya yang sudah berdarah. Buatlah instruksi.
Diberikan rangkaian, AAAKKKUUUHHHAAANNNTUUU Berapa banyak editan minimum untuk membuatnya menjadi rangkaian, AAAAKKUUUUMMMEENAANNTUUUMUUU
Jika dibatasi bahwa semua instruksi hapus harus dikerjakan di awal, apakah batasan ini mengubah efisiensinya? Jelaskan dengan contoh!
Pikirkan sejumlah skenario yang di dalamnya perubahan urutan edit mengakibatkan total editnya berkurang secara drastis.
Bagaimana algoritma untuk menentukan urutan edit yang akan mengakibatkan total editnya menjadi minimal?
Bagaimana jika kita memiliki satu kemungkinan instruksi tambahan, yaitu menujuk ke karakter ke-n?
Apakah kita selalu dapat membuat rangkaian instruksi edit dari sebuah teks ke teks yang lain?
Cobalah mengeksplorasi hal atau produk yang menerapkan solusi bagi permasalahan ini.

Berikutnya: Kilas balik: Himpunan