Levenshtein Algoritmo de distancia mejor que O (n * m)?

Question

He estado buscando un algoritmo avanzado de distancia levenshtein, y the best I have found so far es O (n * m) donde n y m son las longitudes de las dos cadenas. La razón por la que el algoritmo es a esta escala es por falta de espacio, no el tiempo, con la creación de una matriz de las dos cadenas como este:

¿Existe un algoritmo levenshtein a disposición del público que es mejor que O (n * m)? No soy reacio a buscar trabajos avanzados de informática & investigación, pero no he podido encontrar nada. Encontré una compañía, Exorbyte, que supuestamente ha construido un algoritmo Levenshtein súper avanzado y súper rápido, pero por supuesto es un secreto comercial. Estoy construyendo una aplicación para iPhone en la que me gustaría usar el cálculo de distancia de Levenshtein. There is an objective-c implementation available, pero con la cantidad limitada de memoria en iPods y iPhones, me gustaría encontrar un mejor algoritmo si es posible.

Answer 1

¿Está interesado en reducir la complejidad del tiempo o la complejidad del espacio? La complejidad del tiempo promedio se puede reducir O (n + d^2), donde n es la longitud de la cadena más larga yd es la distancia de edición. Si solo está interesado en la distancia de edición y no está interesado en reconstruir la secuencia de edición, solo necesita mantener las últimas dos filas de la matriz en la memoria, por lo que será el orden (n).

Si puede permitirse aproximarse, hay aproximaciones polilogarítmicas.

Para el algoritmo O (n + d^2) busque la optimización de Ukkonen o su mejora Enhanced Ukkonen. La mejor aproximación que conozco es esta por Andoni, Krauthgamer, Onak

Answer 2

Buscar en Wiki - tienen algunas ideas para mejorar este algoritmo para mejor la complejidad del espacio:

Wiki-Link: Levenshtein distance

Citando:

Podemos adaptar el algoritmo para utilizar menos espacio, O (m) en lugar de O (mn), ya que solo requiere que la fila anterior y la fila actual se almacenen en cualquier momento.

Answer 3

Si solo desea la función de umbral, por ejemplo, para comprobar si la distancia está por debajo de un cierto umbral, puede reducir la complejidad de tiempo y espacio calculando valores a ambos lados de la diagonal principal en la matriz. También puede usar Levenshtein Automata para evaluar muchas palabras en una sola palabra base en el tiempo O (n), y la construcción de los autómatas también se puede hacer en el tiempo O (m).

Answer 4

he encontrado otra optimización que afirma ser O (max (m, n)):

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

(la segunda aplicación C)