Edit jarak dengan operasi pemindahan

Motivasi: Seorang penulis pendamping menyunting sebuah naskah dan saya ingin melihat ringkasan yang jelas dari suntingan itu. Semua "diff" -seperti alat cenderung tidak berguna jika Anda berdua bergerak teks di sekitar (misalnya, re-mengatur struktur) dan melakukan suntingan lokal. Apakah sangat sulit untuk memperbaikinya?

Definisi: Saya ingin mencari jarak pengeditan minimum, di mana operasi yang diizinkan adalah:

• operasi "murah": tambah / ubah / hapus satu karakter (operasi Levenshtein yang biasa),

• "mahal": operasi: memindahkan substring ke lokasi baru ( $abcd \mapsto acbd$ untuk string apa pun , , , ).b c $a$$b$$c$$d$

Diberikan dua string dan dan integer dan , saya ingin menyelesaikan masalah berikut:y k $x$$y$$k$$K$

• dapatkah Anda mengubah menjadi menggunakan paling banyak operasi murah dan paling banyak operasi mahal ?y k $x$$y$$k$$K$

Pertanyaan:

1. Apakah masalah ini memiliki nama? (Kedengarannya seperti pertanyaan yang sangat standar dalam konteks penyelarasan urutan.)

2. Apakah ini sulit?

3. Jika sulit, apakah parameternya tetap bisa ditelusuri dengan sebagai parameter?$K$

4. Apakah ada algoritma perkiraan yang efisien? (Misalnya, menemukan solusi dengan paling banyak murah dan operasi mahal jika solusi dengan murah dan operasi mahal ada.)2 K k $2k$$2K$$k$$K$

Saya mencoba untuk melihat metrik string yang tercantum di Wikipedia , tetapi tidak satupun yang terlihat benar.

Seperti dikomentari oleh Serge Gaspers, untuk masalahnya adalah Penyortiran oleh Transposisi , dan diperkenalkan oleh Bafna dan Pevzner pada tahun 1995. Kekerasan NP-nya telah terbukti hanya pada tahun 2010; lihat Laurent Bulteau, Guillaume Fertin, dan Irena Rusu, "Menyortir berdasarkan Transposisi itu Sulit" .$k=0$

Masalahnya menjadi lebih mudah, jika kita mempertimbangkan penghapusan panjang dan penyalinan substring alih-alih transposisi. Asumsikan bahwa kita menggunakan algoritma pemrograman dinamis standar untuk perhitungan mengedit jarak, dan bahwa operasi yang mahal panjang meningkatkan jarak dengan sebuah k + b , untuk beberapa konstanta a , b ≥ 0 . Konstanta ini mungkin berbeda untuk penghapusan panjang dan penyalinan substring.$k$$ak+b$$a,b \ge 0$

Penghapusan panjang adalah penghapusan substring sewenang-wenang dari . Mendukung mereka itu mudah, jika kita memecahnya menjadi dua jenis operasi sederhana: menghapus karakter pertama (biaya a + b ) dan memperluas penghapusan dengan satu karakter (biaya a ). Selain array standar A , di mana A [ i , j ] adalah jarak edit antara awalan x [ 1 ... i ] dan y [ 1 ... j ] , kami menggunakan array lain A $x$$a+b$$a$$A$$A[i,j]$$x[1 \dots i]$$y[1 \dots j]$$A_{d}$untuk menyimpan jarak edit, saat operasi terakhir yang digunakan adalah penghapusan yang panjang. Dengan larik ini, kita hanya perlu melihat , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] dan A d [ i - 1 , j ] saat menghitung A [ i , j ] dan A d [ $A[i-1,j]$$A[i-1,j-1]$$A[i,j-1]$$A_{d}[i-1,j]$$A[i,j]$ , memungkinkan kita untuk melakukannya dalam O ( 1 ) waktu.$A_{d}[i,j]$$O(1)$

Penyalinan substring berarti penyisipan substring sewenang-wenang dari ke string yang diedit. Seperti dengan penghapusan panjang, kami memecah operasi menjadi dua operasi sederhana: memasukkan karakter pertama dan memperluas penyisipan dengan satu karakter. Kami juga menggunakan berbagai A s untuk menyimpan mengedit jarak antara prefiks, asalkan operasi terakhir yang digunakan adalah substring menyalin.$x$$A_{s}$

Melakukan ini secara efisien lebih rumit daripada dengan penghapusan yang lama, dan saya tidak yakin apakah kita bisa mengamortisasi waktu per sel. Kami membangun pohon akhiran untuk x , yang membutuhkan waktu O ( | x | ) , dengan asumsi alfabet ukuran konstan. Kami menyimpan pointer ke simpul pohon akhiran saat ini dalam A s [ i , j - 1 ] , memungkinkan kami untuk memeriksa dalam waktu yang konstan, apakah kami dapat memperluas penyisipan dengan karakter y [ j ] . Jika itu benar, kita dapat menghitung A [ $O(1)$$x$$O(|x|)$$A_{s}[i,j-1]$$y[j]$ dan A s [ i , j ] dalam waktu konstan.$A[i,j]$$A_{s}[i,j]$

Jika tidak, , di mana z adalah substring yang dimasukkan yang digunakan untuk menghitung A s [ i , j - 1 ] , bukan substring dari x . Kami menggunakan pohon sufiks untuk menemukan sufiks terpanjang z ′ dari z , yang z ′ y [ j ] adalah substring dari x , dalam waktu O ( | z | - | z ′ | ) . Untuk menghitung$zy[j]$$z$$A_{s}[i,j-1]$$x$$z'$$z$$z'y[j]$$x$$O(|z|-|z'|)$ , kita sekarang perlu melihat sel A [ i , j - | z ′ | - 1 ] hingga A [ i , j - 1 ] . Menemukan akhiran z ′ hanya membutuhkan waktu diamortisasi O ( 1 ) per sel, tetapi menghitung A s [ i , j ] dengan pendekatan brute-force membutuhkan O ( | $A_{s}[i,j]$$A[i, j-|z'|-1]$$A[i,j-1]$$z'$$O(1)$$A_{s}[i,j]$ waktu. Mungkin ada beberapa cara untuk melakukan ini dengan lebih efisien, tetapi saya tidak dapat menemukannya sekarang.$O(|z'|)$

Dalam kasus terburuk, algoritma membutuhkan waktu , tetapi analisis yang lebih baik harus dimungkinkan. Jarak edit yang dihasilkan dengan penghapusan panjang dan penyalinan substring tidak simetris, tetapi itu seharusnya tidak menjadi masalah. Setelah semua, biasanya lebih mudah untuk mencapai string kosong dari yang kosong daripada sebaliknya.$O(\min(|x| \cdot |y|^{2}, |x|^{2} \cdot |y|))$