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

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

Berikutnya: Kilas balik: Himpunan

Ditulis oleh
Ari Prasetyo
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
kombinatorika algoritma