Pertanyaan Levenshtein Distance Algorithm lebih baik daripada O (n * m)?


Saya telah mencari algoritma jarak jauh levenshtein, dan yang terbaik yang saya temukan sejauh ini adalah O (n * m) di mana n dan m adalah panjang dari dua string. Alasan mengapa algoritma ini pada skala ini adalah karena ruang, bukan waktu, dengan penciptaan matriks dari dua string seperti ini:

alt text

Apakah ada algoritma levenshtein yang tersedia secara umum yang lebih baik daripada O (n * m)? Saya tidak takut untuk melihat makalah ilmu komputer canggih & penelitian, tetapi belum dapat menemukan apa pun. Saya telah menemukan satu perusahaan, Exorbyte, yang konon telah membangun algoritma Levenshtein super canggih dan super cepat tetapi tentu saja itu adalah rahasia dagang. Saya sedang membangun aplikasi iPhone yang saya ingin gunakan perhitungan jarak Levenshtein. Ada implementasi obyektif-c yang tersedia, tetapi dengan jumlah memori terbatas pada iPod dan iPhone, saya ingin menemukan algoritma yang lebih baik jika memungkinkan.


32
2017-10-30 06:17


asal


Jawaban:


Apakah Anda tertarik untuk mengurangi kompleksitas waktu atau kompleksitas ruang? Kerumitan waktu rata-rata dapat dikurangi O (n + d ^ 2), di mana n adalah panjang string yang lebih panjang dan d adalah jarak edit. Jika Anda hanya tertarik pada jarak edit dan tidak tertarik merekonstruksi urutan pengeditan, Anda hanya perlu menyimpan dua baris terakhir dari matriks dalam memori, sehingga akan menjadi urutan (n).

Jika Anda mampu memperkirakan, ada perkiraan poly-logarithmic.

Untuk algoritma O (n + d ^ 2) mencari optimasi Ukkonen atau peningkatannya Peningkatan Ukkonen. Pendekatan terbaik yang saya tahu adalah yang satu ini Andoni, Krauthgamer, Onak


35
2017-10-30 06:40



Jika Anda hanya menginginkan fungsi ambang - misalnya, untuk menguji apakah jaraknya berada di bawah ambang tertentu - Anda dapat mengurangi waktu dan kompleksitas ruang dengan hanya menghitung nilai n di kedua sisi diagonal utama dalam larik. Anda juga bisa menggunakan Levenshtein Automata untuk mengevaluasi banyak kata terhadap satu kata dasar dalam waktu O (n) - dan pembangunan otomat dapat dilakukan dalam waktu O (m) juga.


10
2017-11-01 11:52



Lihat di Wiki - mereka memiliki beberapa ide untuk meningkatkan algoritme ini ke kompleksitas ruang yang lebih baik:

Wiki-Link: jarak Levenshtein

Mengutip:

Kita dapat menyesuaikan algoritma untuk menggunakan lebih sedikit ruang, O (m) daripada O (mn), karena hanya mengharuskan baris sebelumnya dan baris saat ini disimpan pada satu waktu.


2
2017-10-30 06:24



Saya menemukan pengoptimalan lain yang mengklaim sebagai O (max (m, n)):

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C

(implementasi C kedua)


0
2017-12-19 08:13