Algoritmo di distanza di Levenshtein meglio di O (n * m)?

Question

Sono stato alla ricerca di un avanzato algoritmo di distanza levenshtein, e the best I have found so far è O (n * m) dove n e m sono le lunghezze delle due stringhe. Il motivo per cui l'algoritmo è a questa scala è a causa di spazio, non il tempo, con la creazione di una matrice delle due stringhe come questa:

C'è un algoritmo Levenshtein pubblicamente disponibili che è meglio di O (n * m)? Non sono contrario alla ricerca di documenti informatici avanzati &, ma non sono riuscito a trovare nulla. Ho trovato una società, Exorbyte, che presumibilmente ha costruito un algoritmo Levenshtein super avanzato e super veloce, ma naturalmente questo è un segreto commerciale. Sto costruendo un'applicazione per iPhone che mi piacerebbe utilizzare il calcolo della distanza di Levenshtein. There is an objective-c implementation available, ma con la quantità limitata di memoria su iPod e iPhone, mi piacerebbe trovare un algoritmo migliore, se possibile.

Answer 1

Sei interessato a ridurre la complessità del tempo o la complessità dello spazio? La complessità temporale media può essere ridotta O (n + d^2), dove n è la lunghezza della stringa più lunga e d è la distanza di modifica. Se ti interessa solo la distanza di modifica e non sei interessato a ricostruire la sequenza di modifica, devi solo tenere in memoria le ultime due righe della matrice, in modo che sia ordine (n).

Se ci si può permettere di approssimare, ci sono approssimazioni poli-logaritmiche.

Per l'algoritmo O (n + d^2) cercare l'ottimizzazione di Ukkonen o il suo miglioramento Enhanced Ukkonen. La migliore approssimazione che conosco è questa di Andoni, Krauthgamer, Onak

Answer 2

Cerca in Wiki - hanno alcune idee per migliorare questo algoritmo per una migliore complessità spaziale:

Wiki-Link: Levenshtein distance

Citando:

Siamo in grado di adattare l'algoritmo di utilizzare meno spazio, O (m) invece di O (mn), poiché richiede solo che la riga precedente e la riga corrente vengano memorizzate in qualsiasi momento.

Answer 3

Se si desidera solo la funzione di soglia - ad esempio, per verificare se la distanza è inferiore a una determinata soglia - è possibile ridurre la complessità di tempo e spazio calcolando solo il n valori su entrambi i lati della diagonale principale dell'array. Puoi anche usare Levenshtein Automata per valutare molte parole contro una singola parola base in tempo O (n) - e la costruzione degli automi può essere fatta anche nel tempo O (m).

Answer 4

ho trovato un altro ottimizzazione che sostiene di essere O (max (m, n)):

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

(la seconda implementazione C)