Comment puis-je faire une correspondance floue des noms D'entreprise dans MYSQL avec PHP pour Auto-complete?
mes utilisateurs importeront par couper et coller une grande corde qui contiendra des noms de compagnie.
j'ai une base de données MYSQL existante et croissante de noms d'entreprises, chacun avec un company_id unique.
je veux pouvoir analyser à travers la chaîne de caractères et assigner à chacun des noms d'entreprise entrés par l'utilisateur une correspondance floue.
en ce moment, juste faire un match string, est aussi lent. ** Indexation de Soundex être plus vite? Comment puis-je donner à l'utilisateur des options de frappe? **
par exemple, quelqu'un écrit:
Microsoft -> Microsoft Bare Essentials -> Bare Escentuals Polycom, Inc. -> Polycom
j'ai trouvé les fils suivants qui semblent similaires à cette question, mais l'affiche n'a pas approuvé et je ne suis pas sûr si leur cas d'utilisation est applicable:
7 réponses
vous pouvez commencer par utiliser SOUNDEX() , cela fera probablement pour ce que vous avez besoin (j'imagine une boîte d'Auto-suggestion des alternatives déjà existantes pour ce que l'utilisateur tape).
les inconvénients de SOUNDEX() sont:
- son incapacité à différencier les cordes plus longues. Seuls les premiers caractères sont pris en compte, les chaînes plus longues qui divergent à la fin génèrent la même valeur SOUNDEX
- le fait que la première lettre doit être la même ou vous ne trouverez pas facilement une correspondance. SQL Server a la fonction DIFFERENCE () pour vous dire combien deux valeurs de SOUNDEX sont séparées, mais je pense que MySQL n'a rien de ce genre construit.
- pour MySQL, au moins selon the docs , SOUNDEX est cassé pour l'entrée unicode
exemple:
SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')
/* all of these return 'M262' */
pour plus avancé besoins, je pense que vous devez regarder le distance Levenshtein (également appelé "distance d'édition") de deux chaînes et de travailler avec un seuil. C'est la solution la plus complexe (=plus lente), mais elle permet une plus grande flexibilité.
le principal inconvénient est que vous avez besoin des deux chaînes pour calculer la distance entre elles. Avec SOUNDEX vous pouvez stocker un SOUNDEX pré-calculé dans votre table et comparer/trier/group/filter sur cela. Avec la distance Levenshtein, vous pourrait trouver que la différence entre "Microsoft" et "Nzcrosoft" est seulement 2, mais il faudra beaucoup plus de temps pour arriver à ce résultat.
dans tous les cas, un exemple de fonction de distance Levenshtein pour MySQL peut être trouvé à codejanitor.com: Levenshtein Distance as a MySQL Stored Function (Feb. 10th, 2007) .
SOUNDEX est un algorithme correct pour cela, mais il y a eu des avancées récentes sur ce sujet. Un autre algorithme a été créé appelé la Métaphone, et il a été plus tard révisé à une double Métaphone algorithme. J'ai personnellement utilisé l'implémentation java apache commons de double métaphone et elle est personnalisable et précise.
ils ont des implémentations dans beaucoup d'autres langues sur la page wikipedia pour cela, aussi. Cette question a été répondue, mais si vous trouvez n'importe lequel des problèmes identifiés avec le SOUNDEX apparaissant dans votre application, il est agréable de savoir qu'il y a des options. Parfois, il peut générer le même code pour les deux mots différents. Double métaphone a été créé pour aider à prendre soin de ce problème.
volé sur wikipedia: http://en.wikipedia.org/wiki/Soundex
en réponse aux lacunes de la Algorithme de Soundex, Lawrence Philips développé L'algorithme Métaphone pour dans le même but. Philips plus tard développé une amélioration à la Métaphone, ce qu'il a appelé une double métaphore. La double Métaphone inclut un ensemble de règles d'encodage plus grand que son prédécesseur, gère un sous-ensemble de caractères non latins, et renvoie un encodage primaire et secondaire tenir compte des différentes prononciations d'un seul mot en anglais.
au bas de la double page métaphone, ils ont les implémentations de TI pour tous les types de langages de programmation: http://en.wikipedia.org/wiki/Double-Metaphone
Python & MySQL implementation: https://github.com/AtomBoy/double-metaphone
tout d'abord, je voudrais ajouter que vous devez être très prudent lorsque vous utilisez une forme D'algorithme D'appariement phonétique/flou, car ce genre de logique est exactement cela, flou ou pour le dire plus simplement; potentiellement inexacte. Particulièrement vrai lorsqu'il est utilisé pour apparier les noms d'entreprises.
une bonne approche consiste à rechercher la corroboration à partir d'autres données, telles que l'adresse, les codes postaux, les numéros de téléphone, Les coordonnées géographiques, etc. Cela permettra de confirmer la probabilité de vos données être parfaitement assorti.
il y a toute une gamme de questions liées au couplage de données B2B trop nombreux pour être abordés ici, j'ai écrit plus sur correspondance de nom D'entreprise dans mon blog, mais en résumé, les questions clés sont:
- regarder la chaîne entière est inutile comme la partie la plus importante d'une raison sociale n'est pas nécessairement au début de la société Nom. c'est à dire "Le Proctor et Gamble Company" ou ‘Fédérale Des États-Unis Réserve 1519100920"
- les abréviations sont courantes dans les noms de sociétés, c.-à-d. HP, GM, GE, P & G, D&B etc..
- certaines entreprises orthographient délibérément mal leur nom dans le cadre de leur image de marque et de se différencier des autres entreprises.
appariement des données exactes est facile, mais appariement des données non exactes peut être beaucoup plus long et je suggérerais que vous devriez considérer comment vous serez valider les correspondances Non exactes pour s'assurer qu'elles sont de qualité acceptable.
avant que nous construisions Match2Lists.com on passait un temps malsain à valider des correspondances floues. Dans les Match2Lists, nous avons incorporé un outil de Visualisation puissant nous permettant de passer en revue les matches Non-exacts, ce qui s'est avéré être un véritable changeur de jeu en termes de validation des matches, réduisant nos coûts et nous permettant d'obtenir des résultats beaucoup plus rapidement.
bonne chance!!
voici un lien vers la discussion en php des fonctions dans mysql et php. Je commencerai par là, puis je m'étendrai sur vos autres exigences pas si bien définies.
votre référence fait référence à la méthodologie Levenshtein pour l'appariement. Deux problèmes. 1. C'est plus approprié pour mesurer la différence entre deux mots connus, pas pour chercher. 2. Il discute une solution conçue plus pour détecter des choses comme les erreurs de correction (en utilisant "Levenshtien" pour "Levenshtein") plutôt que des fautes d'orthographe (où l'utilisateur ne sait pas épeler, dites" Levenshtein "et tapez"Levinstein". Je l'associe habituellement à la recherche d'une phrase dans un livre plutôt qu'une valeur clé dans une base de données.
EDIT: En réponse au commentaire--
- Pouvez-vous obtenir au moins les utilisateurs à mettre les noms de la société en de multiples zones de texte; 2. ou utilisez un délimiteur de nom non ambigu( par exemple antislash); 3. laisser articles ("le") et abréviations génériques (ou vous pouvez filtrer pour ceux-ci); 4. Squoosh les espaces et faire correspondre aussi (donc Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtrer la ponctuation; 6. Faites des recherches sur les mots ("nu" ou "essentiels") - les gens laisseront inévitablement l'un ou l'autre parfois.
Tester comme mad et utiliser la boucle de rétroaction des utilisateurs.
la meilleure fonction pour une correspondance floue est levenshtein. c'est traditionnellement utilisé par les correcteurs orthographiques, donc c'est peut-être la solution. il y a un UDF disponible ici: http://joshdrew.com/
de l'inconvénient à l'utilisation de levenshtein est qu'il ne pas très bien. une meilleure idée pourrait être de vider la table entière dans un fichier de dictionnaire personnalisé de correcteur orthographique et de faire la suggestion de votre application tier au lieu de la base de données tier.
cette réponse résulte en une recherche indexée de presque n'importe quelle entité utilisant une entrée de 2 ou 3 caractères ou plus.
Fondamentalement, créer une nouvelle table avec 2 colonnes, mot clé. Exécutez un processus sur la table originale contenant la colonne à rechercher floue. Ce processus extraira chaque mot de la colonne originale et écrira ces mots à la table des mots avec la clé originale. Au cours de ce processus, les mots courants comme "le", "et", etc. doit être jeté.
nous créons ensuite plusieurs indices sur la table des mots, comme suit...
- normal, minuscule indice sur le mot + touche
- Un indice sur la 2ème et la 5ème caractère de la touche +
-
Un indice sur le 3e de la 6e caractère de la touche +
alternativement, créez un index SOUNDEX() sur la colonne word.
une fois ceci est en place, nous prenons n'importe quelle entrée d'utilisateur et la recherche en utilisant mot normal = entrée ou comme entrée%. Nous ne faisons jamais d'entrée de type %car nous sommes toujours à la recherche d'une correspondance sur l'un des 3 premiers caractères, qui sont tous indexés.
si votre table originale est massive, vous pouvez diviser la table des mots par morceaux de l'alphabet pour s'assurer que l'entrée de l'utilisateur est réduite à des lignes de candidat immédiatement.
est peut-être trop tard, mais cela pourrait aider les autres. Regardez ce lien.Il utilise les mesures de distance de levenshtein mais est beaucoup plus rapide. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html