Accélérer levenshtein / similar_text en PHP

Question

J'utilise actuellement similar_text pour comparer une chaîne avec une liste de ~ 50 000 qui fonctionne bien qu'en raison du nombre de comparaisons, il est très lent. Il faut environ 11 minutes pour comparer environ 500 chaînes uniques.

Avant de lancer ceci, je vérifie les bases de données pour voir si elles ont déjà été traitées, donc chaque fois après l'exécution initiale, c'est presque instantané.

Je suis sûr que levenshtein serait légèrement plus rapide et La fonction LevenshteinDistance, une personne postée dans le manuel semble intéressante. Me manque-t-il quelque chose qui pourrait rendre cela beaucoup plus rapide?

Answer 1

À la fin, levenshtein et similar_text étaient tous les deux trop lents avec le nombre de chaînes qu'il devait parcourir, même avec de nombreuses vérifications et en ne les utilisant qu'une seule. d'entre eux en dernier recours.

À titre d’expérience, j’ai porté une partie du code en C # pour voir à quel point le code serait interverti plus rapidement. Il a duré environ 3 minutes avec le même jeu de données.

Ensuite, j'ai ajouté un champ supplémentaire à la table et utilisé l'extension PECL à double métaphone pour générer des clés pour chaque ligne. Les résultats ont été bons, bien que certains numéros incluent des doublons. J'imagine que j'aurais alors pu exécuter chacune des fonctions ci-dessus, mais j'ai décidé de ne pas le faire.

Au final, j’ai opté pour l’approche la plus simple, le texte intégral de MySQL, qui a très bien fonctionné. Parfois, des erreurs sont commises bien qu’elles soient faciles à détecter et à corriger. En outre, il fonctionne très vite, en environ 3-4 secondes.

Answer 2

Peut-être pourriez-vous court-circuiter certaines vérifications en comparant d’abord votre chaîne pour une correspondance exacte (et en comparant d’abord si sa longueur est identique), et si elle saute l’appel plus cher similar_text .

Comme @jason l'a noté, un algorithme O (N ^ 3) ne sera jamais un bon choix.

Answer 3

Lorsque vous utilisez levenshtein automate (automate qui correspond à une chaîne avec distance k ), vous pouvez vérifier la correspondance dans O (n) , où n est la longueur de la chaîne que vous vérifiez. La construction de l'automate nécessite O (kn) , où k correspond à la distance maximale et à la longueur n de la chaîne de base.