J'utilise actuellement similaire_text pour comparer une chaîne contre Une liste d'~ 50 000 qui fonctionne bien qu'en raison du nombre de comparaisons, c'est très lent. Il faut environ 11 minutes pour comparer ~ 500 chaînes uniques.
Avant d'exécuter cela, je vérifie les bases de données pour voir si elle a été traitée dans le passé, donc à chaque fois que la course intale est proche de l'instant.
Je suis sûr que j'utilise Levenshtein serait légèrement plus rapide et le LEVENSHTEDINDISTINISTINISTINITÉNAIRE Une personne postée dans le manuel semble intéressante. Est-ce que je manque quelque chose qui pourrait rendre cela nettement plus rapide?
3 Réponses :
Peut-être que vous pourriez «court-circuiter» quelques chèques en comparant d'abord votre chaîne pour une correspondance exacte (et en comparant d'abord si la longueur identique), et si elle ignore le plus cher comme @jason noté, un algorithme O (n ^ 3) ne sera jamais un bon choix. similaire_text appel.
à la fin, En tant qu'expérience, j'ai porté une partie du code à C # pour voir combien de fois ce serait plus rapide sur le code interpété. Il a couru dans 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 touches pour chaque ligne. Les résultats étaient bons, bien que certains chiffres incluaient certaines duplicates. Je suppose que je pourrais alors avoir couru chacun à travers les fonctions ci-dessus, mais décidé de ne pas.
À la fin, j'ai opté pour l'approche la plus simple, le texte intégral mysqls qui a très bien fonctionné. De temps en temps, il y a des erreurs bien qu'elles soient faciles à détecter et à corriger. De plus, il court très vite, environ 3-4 secondes. Levenshtein et similaire_text étaient les deux trop lents avec le nombre de cordes qu'il devait passer, même avec beaucoup de chèques et ne les utiliser qu'un seul d'entre eux en dernier recours.
Lorsque vous utilisez Levenshtein Automaton (automate qui correspond à une chaîne avec distance k ), vous pouvez effectuer une vérification de la correspondance dans O (n) , où n < / code> est la longueur de la chaîne que vous vérifiez. Construire l'automate prendra O (kN) , où k est max distance et n longueur de la chaîne de base.
O (n ** 3) où n est la longueur de la chaîne la plus longue poursimilaire_text ...Quelle est la longueur moyenne des cordes? AAANDD ... Combien de données dans la chaîne est réellement pertinente pour la recherche? C'est-à-dire combien vient de cruft?
La longueur moyenne est d'environ 20 caractères et un pourcentage élevé des données est pertinente, peut-être 85-95%. Je pense que peut-être utiliser ceux-ci sont un peu surkill et je pourrais probablement simplement utiliser une recherche de texte complète dans MySQL suivie de quelques chèques.
Si seulement des correspondances rapprochées sont nécessaires, des vérifications rapides à l'aide de la longueur de la chaîne peuvent être effectuées.