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 |
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 repada 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