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:
- Hapus n karakter pada posisi p.
- Sisipkan rangkaian karakter s pada posisi p.
Eksplorasi
- Diberikan kalimat,
Poki menggigit anjingnya hingga berdarah.
Kamu hendak mengeditnya menjadi,
Poki menggigit anjingnya yang sudah berdarah. Buatlah instruksi untuk editan ini. - Diberikan rangkaian,
AAAKKKUUUHHHAAANNNTUUU
Berapa banyak instruksi minimum untuk membuatnya menjadi rangkaian,AAAAKKUUUUMMMEENAANNTUUUMUUU
- Jika dibatasi bahwa semua instruksi hapus harus dikerjakan di awal, apakah batasan ini mengubah efisiensinya? Jelaskan dengan contoh!
Berikutnya: Kilas balik: Himpunan