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

algorithm big-o

Question

He estado buscando un algoritmo avanzado de distancia levenshtein, y lo mejor que he encontrado hasta ahora es O (n * m) donde n y m son las longitudes de las dos cadenas. La razón por la cual el algoritmo está en esta escala es por el espacio, no el tiempo, con la creación de una matriz de dos cadenas como esta:

¿Hay un algoritmo levenshtein disponible públicamente que sea mejor que O (n * m)? No soy reacio a buscar trabajos e investigaciones avanzados en informática, 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. Hay una implementación objetivo-c disponible , 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 Ukkonen mejorada . La mejor aproximación que conozco es esta de Andoni, Krauthgamer, Onak

Answer 2

Encontré otra optimización que dice ser O (max (m, n)):

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

(la segunda implementación de C)

Answer 3

Mire en Wiki: tienen algunas ideas para mejorar este algoritmo para mejorar la complejidad del espacio:

Wiki-Link: distancia Levenshtein

Citando:

Podemos adaptar el algoritmo para usar 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 4

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 del tiempo y el espacio calculando únicamente los n valores a cada lado de la diagonal principal de la matriz. También puede usar Levenshtein Automata para evaluar muchas palabras contra una sola palabra base en el tiempo O (n), y la construcción de los autómatas también puede realizarse en el tiempo O (m).