Jumlah pengeditan tersingkat antara dua kata

Saya mencari struktur data dan algoritma untuk menghitung jumlah minimum perubahan yang diperlukan untuk mengubah satu kata menjadi kata lain, mengingat dua kata sebagai input, di mana satu-satunya perubahan yang diizinkan adalah

• tambahkan surat di salah satu ekstremitas (misalnya, AB -> ABC),
• duplikat dan gabungkan seluruh kata (misalnya, ABC -> ABCABC),
• potong kata menjadi dua (dual duplikasi pemindahan, ABCABC -> ABC + ABC),
• hapus salah satu huruf (misalnya, ABC -> AC), dan
• ulangi salah satu huruf (misalnya, ABC -> ABBC).

Misalnya, urutan minimal perpindahan dari ABC ke BCBC adalah ABC -> BC (delete A) -> BCBC (duplikasi).

Saya tidak memiliki latar belakang dalam ilmu komputer. Mungkin ini adalah masalah yang terkenal, tetapi pencarian Google saya tidak memberi saya apa pun.

Apakah Anda tahu beberapa masalah terkait dan terdefinisi dengan baik?

Sunting : Seperti yang disarankan dalam jawaban oleh Anthony Labarre, saya membaca beberapa makalah tentang masalah permutasi / pengaturan poset yang mirip dengan masalah yang dijelaskan di atas. Adakah yang tahu lebih banyak tentang masalah ini? Apakah ini relevan?

Saya tidak tahu apakah masalah pasti ini telah dipelajari, tetapi Chaudhuri et al. mempelajari masalah terkait duplikasi-tandem kerugian acak : Anda diberi permutasi, dan Anda ingin mengubahnya menjadi permutasi identitas dengan (1) menduplikasi segmen dengan panjang berapa pun dan menambahkan salinan tepat setelah yang asli, kemudian (2) menghapus elemen sehingga Anda mendapatkan permutasi baru alih-alih string. Perhatikan bahwa menerapkan (1) lalu (2) merupakan satu operasi.

Varian yang berbeda dapat didefinisikan sesuai dengan bobot yang diberikan untuk setiap operasi, yang dalam makalahnya tergantung pada lebar segmen yang diduplikasi. Mereka juga mempelajari masalah serupa dengan duplikasi genom keseluruhan , yang merupakan jenis duplikasi yang Anda izinkan. Saya tidak ingat pernah membaca tentang mengatasi masalah ini dalam konteks string, tetapi saya harap ini setidaknya dapat memberi Anda titik awal untuk pencarian Anda.

Seperti yang telah ditunjukkan, masalah ini mirip dengan masalah jarak edit yang lebih dikenal (yang mendasari jarak Levenshtein ). Ini juga memiliki kesamaan dengan, misalnya, jarak Dynamic Time Warping (duplikasi, atau "gagap," dalam persyaratan terakhir Anda).

Langkah menuju pemrograman dinamis

$x=x_1\ldots x_n$$y=y_1\ldots y_m$$d(x,y)$

$$\min \begin{cases} d(x,y_1\ldots y_{m-1})+1 & &\text{▻ Add letter at end}\\ d(x,y_2\ldots y_m)+1 & & \text{▻ Add letter at beginning}\\ d(x,y_1\ldots y_{m/2})+1 & \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$} & \text{▻ Doubling}\\ d(x_1\ldots x_{n/2},y)+1 & \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$} & \text{▻ Halving}\\ d(x_1\ldots x_n,y) + 1 && \text{▻ Deletion}\\ d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) & \text{if $y_n = y_m$} & \text{▻ Ignoring last elt.}\\ \end{cases}$$

Di sini, opsi terakhir pada dasarnya mengatakan bahwa mengubah FOOX ke BARX sama dengan mengubah FOO ke BAR. Ini berarti bahwa Anda dapat menggunakan opsi “add letter at end” untuk mencapai efek kegagapan (duplikasi), dan penghapusan pada suatu titik. Masalahnya adalah bahwa secara otomatis memungkinkan Anda menambahkan sewenang-wenang karakter di tengah-tengah string juga , sesuatu yang Anda mungkin tidak ingin. (Ini "mengabaikan elemen terakhir yang identik" adalah cara standar untuk mencapai penghapusan dan kegagapan dalam posisi sewenang-wenang. Itu memang membuat melarang penyisipan sewenang-wenang, sambil memungkinkan penambahan di kedua ujung, sedikit rumit, meskipun ...)

Saya sudah memasukkan pengelompokan ini walaupun itu tidak melakukan pekerjaan sepenuhnya, kalau-kalau ada orang lain yang bisa "menyelamatkannya", dan karena saya menggunakannya dalam solusi heuristik saya, di bawah.

(Tentu saja, jika Anda bisa mendapatkan rincian seperti ini yang benar-benar menentukan jarak Anda, Anda hanya perlu menambahkan memoisasi, dan Anda akan punya solusinya. Namun, karena Anda tidak hanya bekerja dengan awalan, saya tidak mau ' t berpikir Anda bisa menggunakan hanya indeks untuk memoisasi Anda; Anda mungkin harus menyimpan string yang sebenarnya dimodifikasi untuk setiap panggilan, yang akan menjadi besar jika string Anda berukuran besar.)

Langkah menuju solusi heuristik

Pendekatan lain, yang mungkin lebih mudah dipahami, dan yang bisa menggunakan sedikit ruang lebih sedikit, adalah mencari "jalur edit" terpendek dari string pertama Anda ke yang kedua, menggunakan algoritma (pada dasarnya, terbaik- cabang-dan-terikat pertama). Ruang pencarian akan ditentukan secara langsung oleh operasi edit Anda. Sekarang, untuk string besar, Anda akan melakukannya$A^\ast$A ∗dapatkan lingkungan yang luas, karena Anda dapat menghapus karakter apa pun (memberi Anda tetangga untuk setiap penghapusan potensial), atau menduplikasi karakter apa pun (sekali lagi, memberi Anda jumlah tetangga linear), serta menambahkan karakter apa pun di kedua ujungnya, yang akan memberi Anda sejumlah tetangga sama dengan dua kali ukuran alfabet. (Hanya berharap Anda tidak menggunakan Unicode penuh ;-) Dengan fanout yang begitu besar, Anda dapat mencapai percepatan yang cukup besar menggunakan dua arah , atau relatif$A^*$ .

Agar berfungsi, Anda memerlukan batas bawah untuk jarak yang tersisa ke target Anda. Saya tidak yakin apakah ada pilihan yang jelas di sini, tetapi yang dapat Anda lakukan adalah mengimplementasikan solusi pemrograman dinamis berdasarkan dekomposisi rekursif yang saya berikan di atas (sekali lagi dengan masalah ruang yang mungkin jika string Anda sangat panjang). Sementara itu dekomposisi tidak tepat menghitung jarak, itu adalah dijamin akan lebih rendah terikat (karena lebih permisif), yang berarti itu akan bekerja sebagai heuristik di . (Seberapa ketat itu, saya tidak tahu, tetapi itu akan benar.) Tentu saja, memoisasi fungsi terikat Anda dapat dibagikan di semua perhitungan batas selamaA ∗ A $A^*$$A^*$$A^*$Lari. (Pengorbanan waktu / ruang di sana.)

Begitu…

Efisiensi dari solusi yang saya usulkan tampaknya sedikit bergantung pada (1) panjang string Anda, dan (2) ukuran alfabet Anda. Jika tidak ada yang besar, itu mungkin berhasil. Itu adalah:

• Terapkan batas bawah pada jarak Anda menggunakan dekomposisi rekursif saya dan pemrograman dinamis (misalnya, menggunakan fungsi memoise, rekursif).
• Terapkan (atau dua arah ) dengan operasi edit Anda sebagai "bergerak" di ruang-negara, dan batas bawah berbasis pemrograman dinamis.A $A^*$$A^*$

Saya benar-benar tidak bisa memberikan jaminan seberapa efisiennya, tetapi harus benar, dan mungkin akan jauh lebih baik daripada solusi brute-force.

Jika tidak ada yang lain, saya harap ini memberi Anda beberapa ide untuk penyelidikan lebih lanjut.

Beberapa masalah yang terkait dan terdefinisi dengan baik adalah masalah penyelarasan urutan . Ini berbeda karena tidak menggunakan operasi duplikasi. Operasi yang didefinisikan adalah: penyisipan karakter, penghapusan karakter, transformasi karakter. Algoritma populer untuk memecahkan masalah ini adalah Needleman-Wunsch .

Kecuali untuk duplikasi, jarak Levenstein mungkin patut dilihat: http://en.wikipedia.org/wiki/Levenshtein_distance