Comment faire une correspondance floue des noms de sociétés dans MYSQL avec PHP pour l'auto-complétion ?

Question

Mes utilisateurs vont importer par copier-coller une grande chaîne contenant des noms de sociétés.

Je dispose d'une base de données MYSQL existante et en pleine expansion contenant des noms d'entreprises, chacune ayant un numéro d'entreprise unique.

Je veux être en mesure d'analyser la chaîne et d'attribuer à chacun des noms de société attribués par l'utilisateur une correspondance floue.

À l'heure actuelle, le simple fait de faire une correspondance directe entre des chaînes de caractères est également lent. ** L'indexation par Soundex sera-t-elle plus rapide ? Comment puis-je donner à l'utilisateur quelques options pendant qu'il tape ? **

Par exemple, quelqu'un écrit :

Microsoft       -> Microsoft
Bare Essentials -> Bare Escentuals
Polycom, Inc.   -> Polycom

J'ai trouvé les fils de discussion suivants qui semblent similaires à cette question, mais l'auteur n'a pas approuvé et je ne suis pas sûr que leur cas d'utilisation soit applicable :

Comment trouver la meilleure correspondance floue pour une chaîne de caractères dans une grande base de données de chaînes de caractères ?

Correspondance de noms de sociétés inexacts en Java

Answer 1

Vous pouvez commencer par utiliser SOUNDEX() J'imagine une boîte de suggestions automatiques d'alternatives déjà existantes pour ce que l'utilisateur est en train de taper.

Les inconvénients de SOUNDEX() sont :

• son incapacité à différencier les chaînes de caractères 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, sinon vous ne trouverez pas facilement de correspondance. Le serveur SQL dispose de la fonction DIFFERENCE() pour vous indiquer de combien deux valeurs SOUNDEX sont séparées, mais je pense que MySQL n'a rien de ce genre intégré.
• pour MySQL, du moins selon les docs SOUNDEX est cassé pour l'entrée unicode.

Ejemplo:

SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */

Pour des besoins plus avancés, je pense qu'il faut regarder du côté de l' distance de Levenshtein (également appelée "distance d'édition") de deux chaînes de caractères 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 cordes pour calculer la distance qui les sépare. Avec SOUNDEX, vous pouvez stocker un SOUNDEX précalculé dans votre table et comparer/trier/grouper/filtrer sur cette base. Avec la distance de Levenshtein, vous pouvez trouver que la différence entre "Microsoft" et "Nzcrosoft" n'est que de 2, mais il vous faudra beaucoup plus de temps pour arriver à ce résultat.

Dans tous les cas, un exemple de fonction de distance de Levenshtein pour MySQL peut être trouvé à l'adresse suivante codejanitor.com : Distance de Levenshtein en tant que fonction stockée MySQL (10 févr. 2007) .

Answer 2

SOUNDEX est un bon algorithme pour cela, mais il y a eu des avancées récentes sur ce sujet. Un autre algorithme a été créé, appelé le Métaphone, et il a ensuite été révisé pour devenir un algorithme de Double Métaphone. J'ai personnellement utilisé l'implémentation java apache commons du double métaphone et elle est personnalisable et précise.

La page wikipedia présente également des implémentations dans de nombreux autres langages. Cette question a reçu une réponse, mais si vous rencontrez l'un des problèmes identifiés avec l'apparition du SOUNDEX dans votre application, il est bon de savoir qu'il existe des options. Parfois, il peut générer le même code pour deux mots vraiment différents. Le double métaphone a été créé pour remédier à ce problème.

Volé de wikipedia : http://en.wikipedia.org/wiki/Soundex

En réponse aux déficiences de la l'algorithme Soundex, Lawrence Philips a développé l'algorithme Metaphone pour le même objectif. Philips a ensuite a développé une amélioration de Metaphone, qu'il a appelé Double-Métaphone. Double-Métaphone comprend un ensemble de règles de codage jeu de règles de codage beaucoup plus important que son prédécesseur, gère un sous-ensemble de caractères non-latins, et renvoie un primaire et secondaire pour tenir compte pour tenir compte des différentes prononciations d'un même mot en anglais.

Au bas de la page du double métaphone, on trouve les implémentations de celui-ci pour toutes sortes de langages de programmation : http://en.wikipedia.org/wiki/Double-Metaphone

Mise en œuvre de Python et MySQL : https://github.com/AtomBoy/double-metaphone

Answer 3

Tout d'abord, je voudrais ajouter que vous devez être très prudent lorsque vous utilisez une forme d'algorithme de correspondance phonétique/floue, car ce type de logique est exactement cela, floue ou, pour le dire plus simplement, potentiellement inexacte. C'est particulièrement vrai lorsqu'il s'agit de faire correspondre des noms de sociétés.

Une bonne approche consiste à chercher à corroborer d'autres données, telles que des informations sur l'adresse, les codes postaux, les numéros de téléphone, les coordonnées géographiques, etc. Cela permettra de confirmer la probabilité d'une correspondance exacte de vos données.

Il existe toute une série de questions liées à la comparaison de données entre entreprises, trop nombreuses pour être abordées ici. Correspondance de noms de sociétés dans mon blog (également un article actualisé ), mais en résumé, les questions clés sont les suivantes :

• Regarder l'ensemble de la chaîne n'est pas utile car la partie la plus importante d'un nom de société n'est pas nécessairement au début du nom de la société. de la société. Par exemple, "The Proctor and Gamble Company" ou "United States Federal Réserve fédérale des États-Unis ".
• Les abréviations sont courantes dans les noms de sociétés, par exemple HP, GM, GE, P&G, D&B, etc.
• Certaines entreprises orthographient délibérément leur nom de manière incorrecte dans le cadre de leur stratégie de leur image de marque et pour se différencier des autres entreprises.

Il est facile de faire correspondre des données exactes, mais faire correspondre des données non exactes peut prendre beaucoup plus de temps et je vous suggère de réfléchir à la manière dont vous allez valider les correspondances non exactes pour vous assurer qu'elles sont de qualité acceptable.

Avant de créer Match2Lists.com, nous passions un temps fou à valider les correspondances floues. Dans Match2Lists, nous avons incorporé un puissant outil de visualisation nous permettant d'examiner les correspondances non exactes, ce qui a changé la donne en termes de validation des correspondances, réduisant nos coûts et nous permettant de fournir des résultats beaucoup plus rapidement.

Bonne chance !

Answer 4

Voici un lien vers la discussion php sur les fonctions soundex en mysql et en php. Je commencerais à partir de là, puis j'élargirais à vos autres exigences pas si bien définies.

Votre référence fait référence à la méthodologie Levenshtein pour la correspondance. Deux problèmes. 1. Elle est plus appropriée pour mesurer la différence entre deux mots connus, pas pour la recherche. 2. Elle traite d'une solution conçue plutôt pour détecter des choses comme les erreurs de correction (en utilisant "Levenshtien" pour "Levenshtein") que les erreurs d'orthographe (lorsque l'utilisateur ne sait pas comment épeler, disons "Levenshtein" et tape "Levinstein". Je l'associe généralement à la recherche d'une phrase dans un livre plutôt que d'une valeur clé dans une base de données.

EDIT : En réponse au commentaire--

1. Pouvez-vous au moins faire en sorte que les utilisateurs inscrivent les noms des sociétés dans plusieurs zones de texte ; 2. ou utiliser un délimiteur de nom non ambigu (disons la barre oblique inversée) ; 3. laisser de côté les articles ("Le") et les abréviations génériques (ou vous pouvez les filtrer) ; 4. supprimer les espaces et les faire correspondre aussi (donc Micro Soft => microsoft => bareessentials) ; 5. Supprimez les espaces et faites une correspondance pour cela aussi (donc Micro Soft => microsoft, Bare Essentials => bareessentials) ; 5. filtrez la ponctuation ; 6. faites des recherches "OR" sur les mots ("bare" OR "essentials") - les gens vont inévitablement oublier l'un ou l'autre parfois.

Testez comme un fou et utilisez la boucle de rétroaction des utilisateurs.

Answer 5

Cette réponse permet de rechercher de manière indexée presque toutes les entités en utilisant des entrées de 2 ou 3 caractères ou plus.

En gros, créez un nouveau tableau avec 2 colonnes, mot et clé. Exécutez un processus sur la table originale contenant la colonne qui doit faire l'objet d'une recherche floue. Ce processus va extraire chaque mot individuel de la colonne originale et écrire ces mots dans la table des mots avec la clé originale. Au cours de ce processus, les mots courants tels que "le", "et", etc. doivent être éliminés.

Nous créons ensuite plusieurs indices sur la table des mots, comme suit...

• Un index normal, en minuscules, sur mot + clé
• Un index sur le 2ème à 5ème caractère + touche

• Un index sur le 3ème à 6ème caractère + clé

  Vous pouvez également créer un index SOUNDEX() sur la colonne des mots.

Une fois que cela est en place, nous prenons n'importe quelle entrée de l'utilisateur et effectuons une recherche en utilisant le mot normal = entrée ou LIKE entrée%. Nous ne faisons jamais de LIKE %input car nous recherchons toujours une correspondance sur l'un des 3 premiers caractères, qui sont tous indexés.

Si votre tableau d'origine est très volumineux, vous pouvez partitionner le tableau de mots par morceaux de l'alphabet pour vous assurer que l'entrée de l'utilisateur est immédiatement réduite aux lignes candidates.