Acelerar levenshtein / similar_text en PHP

Question

Actualmente estoy usando similar_text para comparar una cadena con una lista de ~ 50,000 que funciona, aunque debido a la cantidad de comparaciones es muy lenta. Se necesitan alrededor de 11 minutos para comparar ~ 500 cadenas únicas.

Antes de ejecutar esto, verifico las bases de datos para ver si se ha procesado en el pasado, de modo que cada vez que se realiza la ejecución inicial es casi instantánea.

Estoy seguro de que usar levenshtein sería un poco más rápido y el La función LevenshteinDistance que alguien publicó en el manual parece interesante. ¿Me estoy perdiendo algo que pueda hacer esto significativamente más rápido?

Answer 1

Al final, tanto levenshtein como similar_text eran demasiado lentos con la cantidad de cadenas que tenía que pasar, incluso con muchas comprobaciones y solo usándolas una de ellos como último recurso.

Como experimento, porté parte del código a C # para ver cuánto más rápido sería sobre el código interperado. Se ejecutó en aproximadamente 3 minutos con el mismo conjunto de datos.

A continuación, agregué un campo adicional a la tabla y usé la extensión PECL de doble metafono para generar claves para cada fila. Los resultados fueron buenos, aunque dado que algunos números incluidos esto causó duplicados. Supongo que podría haber ejecutado cada una de las funciones anteriores, pero decidí no hacerlo.

Al final, opté por el enfoque más simple, el texto completo de MySQL que funcionó muy bien. Ocasionalmente hay errores, aunque son fáciles de detectar y corregir. También funciona muy rápido, en unos 3-4 segundos.

Answer 2

Tal vez podría 'cortocircuitar' algunas comprobaciones al comparar primero su cadena para una coincidencia exacta (y al comparar primero si la longitud es idéntica), y si se salta la llamada más costosa similar_text

Como señaló @jason, un algoritmo O (N ^ 3) nunca será una buena opción.

Answer 3

Cuando se usa el autómata levenshtein (autómata que coincide con una cadena con una distancia k ), puede hacer una comprobación de coincidencia en O (n) , donde n es la longitud de la cadena que está verificando. La construcción del autómata tomará O (kn) , donde k es la distancia máxima y n longitud de la cadena base.