Menghitung jarak Levenshtein dengan cepat

24

Dengan basis data besar dari kata-kata yang diizinkan (diurutkan menurut abjad) dan sebuah kata, cari kata dari basis data yang paling dekat dengan kata yang diberikan dalam hal jarak Levenshtein.

Pendekatan naif, tentu saja, hanya menghitung jarak levenshtein antara kata yang diberikan dan semua kata dalam kamus (kita bisa melakukan pencarian biner dalam database sebelum benar-benar menghitung jarak).

Saya ingin tahu apakah ada solusi yang lebih efisien untuk masalah ini. Mungkin beberapa heuristik yang memungkinkan kita mengurangi jumlah kata untuk dicari, atau optimisasi ke algoritma levenshtein distance.

Tautan ke makalah tentang sambutan subjek.

ds.algorithms reference-request string-matching string-search Joshua Herman
sumber

16

Yang Anda tanyakan adalah masalah pencarian tetangga dekat di bawah jarak sunting. Anda tidak menyebutkan apakah Anda tertarik pada hasil teoritis atau heuristik, jadi saya akan menjawab yang pertama.

Jarak pengeditan agak buruk untuk menangani untuk membangun struktur pencarian tetangga dekat. Masalah utama adalah bahwa sebagai metrik, ia berperilaku (semacam) seperti metrik buruk terkenal lainnya seperti untuk tujuan pengurangan dan perkiraan dimensi. Ada banyak pekerjaan yang harus dilakukan untuk membaca tentang topik ini, dan sumber terbaik Anda adalah serangkaian makalah oleh Alex Andoni : dengan mengikuti petunjuk ke belakang (misalnya dari makalah FOCS 2010-nya) Anda akan mendapatkan serangkaian sumber yang bagus. $\ell_1$

Suresh Venkat
sumber

1

Yang saya tahu tentang ruang metrik adalah dari semantik, jadi pertanyaan: apakah ada embrio yang layak (dengan nilai layak) dari metrik Levenshtein menjadi ultrametrik? Begitu saja, yang mungkin menimbulkan algoritma binary-tree-ish.

Neel Krishnaswami

Saya tidak sepenuhnya yakin. Saya menduga jawabannya tidak secara umum, tetapi saya tidak punya maksud.

Suresh Venkat

Makalah kedua pada boytsov.info/pubs adalah survei yang bagus tentang solusi yang mungkin untuk pencarian tetangga dekat di bawah jarak sunting Levenshtein dan Damereau-Levenshtein.

a3nm

@NeelKrishnaswami Sebuah penyisipan ke ultrametrik akan memiliki distorsi setidaknya

mana

adalah panjang string. Ini mengikuti dari distorsi batas bawah untuk penanaman ke

karena Krauthgamer dan Rabani , karena ultrametrik menanamkan secara isometrik ke dalam ruang Euclidean, yang menanamkan secara isometrik ke dalam

.

Ω (\log d)

$\Omega(\log d)$

d

$d$

L_{1}

$L_1$

L_{1}

$L_1$

Sasho Nikolov

9

Levenshtein automatons: http://en.wikipedia.org/wiki/Levenshtein_automaton

Pohon BK: http://en.wikipedia.org/wiki/BK-tree

sclv
sumber

2

Saya menemukan referensi ke-3 di sana ( blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees ) berguna.

Teun D

5

Jika Anda memiliki sejumlah kecil kesalahan edit yang akan Anda toleransi, maka Anda dapat mencoba menggunakan pohon sufiks bertitik . Penafian: Saya menulis makalah itu, tetapi ia memecahkan apa yang Anda inginkan: ia memiliki biaya ruang disk yang tinggi, tetapi pertanyaannya sangat cepat.

Secara umum, lebih baik untuk melihatnya sebaliknya: Anda memiliki indeks dari semua kata dalam kamus. Sekarang, untuk kata input w, jika ada di kamus, berhenti. Jika tidak, hasilkan semua variasi pada jarak 1 dan cari itu. Jika tidak ada, cari variasi pada jarak 2, dan seterusnya ...

Ada beberapa perbaikan pada ide dasar ini.

luispedro
sumber

1

Anda harus menyertakan tautan ke arsip penelitian yang dapat direproduksi untuk makalah ini .

Dan D.

4

$O(m^{k+1} \cdot \sigma^{k})$ $m$ $\sigma$ $k$

Jouni Sirén
sumber

4

Saya menulis jawaban untuk pertanyaan yang sangat mirip di cs.stackexchange.com ( /cs//a/2096/1490 ) dan kemudian saya menemukan pertanyaan ini. Jawabannya ada untuk perkiraan pencarian tetangga dekat dalam jarak sunting (yaitu algoritma menghasilkan string yang kira-kira dekat dengan string permintaan sebagai tetangga terdekat dari string permintaan). Saya memposting di sini karena saya tidak menemukan referensi yang saya berikan di sana dalam jawaban yang diberikan di sini.

Sasho Nikolov
sumber

3

Saya pikir yang Anda inginkan adalah algoritma Wagner-Fischer: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm Wawasan utama adalah bahwa, karena kamus yang Anda lewati diurutkan, dua kata berurutan sangat mungkin untuk membagikan awalan yang panjang sehingga Anda tidak perlu memperbarui seluruh matriks untuk setiap perhitungan jarak.

Björn Lindqvist
sumber

2

Anda dapat menggunakan Apakah maksud Anda?

Dan kemudian temukan jarak Levenshtein antara jawaban yang dikembalikan oleh "Apakah maksud Anda" "dan masukkan string menggunakan Pemrograman Dinamis.

Pratik Deoghare
sumber

Saya tidak mengerti jawaban ini. Pertanyaannya bertanya bagaimana seseorang dapat secara efisien menemukan kata dalam kamus besar dengan jarak Levenshtein dekat ke input yang diberikan, bukan tentang bagaimana menghitung jarak Levenshtein atau tentang perbandingan dengan output kotak hitam pemeriksa ejaan kotak ...

Huck Bennett

@Huck Bennett: Saya pikir @Grigory Javadyan adalah Did you mean?fitur bangunan . Selain itu Did you mean?mengembalikan kata yang sangat dekat dengan input yang diberikan dan melakukannya dengan cukup efisien. :)

Pratik Deoghare

Saya pikir ide Anda bagus, tetapi tampaknya Grigory meminta sesuatu yang lebih dalam dan lebih spesifik.

Huck Bennett

@Huck Bennett: Ya Anda benar! :)

Pratik Deoghare

-1

Salah satu caranya adalah melatih model pembelajaran mesin untuk memetakan kata-kata ke vektor dan memetakan jarak levenshtein ke jarak euclidean. Kemudian Anda bisa membuat KDTree dari vektor untuk kamus yang ingin Anda gunakan. Saya membuat notebook jupyter yang melakukan ini di sini: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Sesuai komentar DW:

prosedur pelatihan = penurunan gradien stokastik dengan gradien adaptif
loss function = berarti kuadrat kesalahan antara jarak sunting yang benar dan jarak euclidean
data pelatihan = string acak yang panjangnya antara 1 dan 32 karakter (dapat ditingkatkan dengan data yang cocok dengan distribusi aktual dari kesalahan ketik umum)
hasil kuantitatif: Setelah pelatihan untuk sekitar 150 zaman dengan ukuran batch 2048 (waktu dinding = sekitar satu menit), menggunakan embeddings kata dari 512 dimensi, dengan satu lapisan tersembunyi, kesalahan absolut rata-rata antara jarak sunting yang benar dan jarak sunting yang diprediksi berada di sekitar 0,75, artinya jarak edit yang diprediksi kira-kira satu karakter tidak aktif

Ringkasan struktur model:

Buat penyematan terpelajar untuk setiap karakter, termasuk karakter nol (digunakan nanti untuk teks kanan di bawah batas karakter)
Pad sisi kanan teks dengan karakter nol hingga batas karakter (32)
Gabungkan embeddings ini
Jalankan embeddings melalui net-forward neural net untuk menghasilkan embedding kata dengan dimensi lebih rendah (512 dimensi)
Lakukan ini untuk kedua kata
Temukan jarak euclidean antara vektor
Atur kerugian menjadi kesalahan kuadrat rata-rata antara jarak Levenshtein yang sebenarnya dan jarak euclidean

Data pelatihan saya hanya string acak, tetapi saya pikir hasilnya benar-benar dapat meningkat jika data pelatihan itu (salah ketik / kata benar) berpasangan. Saya akhirnya hanya menggunakan /usr/share/dict/wordskarena itu tersedia secara umum.

michaelsnowden
sumber

2

Bagaimana Anda melatih model ML sehingga kata-kata yang ada di dekatnya di peta jarak Levenshtein ke vektor yang sama? Apa prosedur pelatihan dan fungsi kerugian yang Anda gunakan untuk itu? Bisakah Anda meringkas metode dalam jawaban Anda, sehingga jawabannya tetap berguna bahkan jika tautannya berhenti berfungsi, dan agar kami tidak perlu menggali buku catatan Anda untuk memahami metode yang Anda gunakan? Juga, dapatkah Anda mengevaluasi seberapa baik kerjanya secara kuantitatif? Apakah ini lebih baik daripada alternatifnya?

DW

Seperti berdiri, ini (saya pikir) cocok untuk CSTheory. Yaitu, tidak tahu apa yang disarankan secara khusus, dan tidak ada justifikasi teoretis untuk itu.

Clement C.

@ WD Maaf tentang hal itu - saya telah membuat suntingan yang cukup substansial yang harus komprehensif jika tautannya turun (atau jika Anda tidak ingin melihat-lihat buku catatan). Walaupun ini bukan teori CS karena ini bukan penelitian, saya pikir ini pendekatan praktis karena cepat dan mudah untuk pelatihan dan kesimpulan.

michaelsnowden

1

Anda melatih string acak. Jarak Levenshtein yang diharapkan antara dua string seperti itu akan menjadi sekitar panjang string yang lebih panjang. Dengan demikian, sangat mudah untuk memperkirakan jarak ini pada string acak, tetapi itu tidak berguna untuk berurusan dengan data dunia nyata. Saya menduga embeddings Anda mungkin hanya menyandikan panjang tali, dan dengan demikian Anda mungkin telah membangun cara mewah untuk melakukan sesuatu yang sepele dan tidak berguna. Ini adalah masalah dengan menggunakan ML; itu sangat sensitif terhadap fungsi kerugian yang Anda gunakan.

DW

@ DW Jika Anda melihat hasil di notebook, pengambilan akhirnya mengembalikan hasil yang layak - bukan hanya string dengan panjang yang sama. Saya benar-benar akan mendorong Anda untuk melihatnya. Saya tidak akan menyebutnya sepele dan tidak berguna.

michaelsnowden

Menghitung jarak Levenshtein dengan cepat

Jawaban: