Acelerando 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. Toma alrededor de 11 minutos comparar ~ 500 cadenas únicas.

Antes de ejecutar esto, compruebo las bases de datos para ver si se ha procesado en el pasado, por lo que cada vez que se ejecuta de manera inme- diata es casi instantánea.

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

Answer 1

Al final, tanto levenshtein como similar_text fueron demasiado lentos con el número de cadenas que tuvo que pasar, incluso con muchos controles y solo usándolos uno de ellos como último recurso.

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

siguiente que añade un campo adicional a la tabla y se utiliza la doble extensión PECL metaphone 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 he optado por el enfoque más simple, MySQLs texto completo que funcionaba muy bien. Ocasionalmente hay errores, aunque son fáciles de detectar y corregir. También funciona muy rápido, en alrededor de 3-4 segundos.

Answer 2

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

Como @ Jason tomó nota, un O (N^3) algoritmo nunca va a ser una buena opción.

Answer 3

Al utilizar autómata levenshtein (autómata que coincide con una cadena con la distancia k) que puede hacer un cheque de juego en O(n), donde n es la longitud de la cadena que está mirando. La construcción del autómata tomará O(kn), donde k es la distancia máxima y n longitud de la cadena base.