Comment dois-je faire une correspondance approximative de noms de société dans MYSQL avec PHP pour l'auto-complétion?

Mes utilisateurs à importer par le biais de couper et de coller une grande chaîne qui contiendra les noms de société.

J'ai déjà un et la croissance de MYSQL base de données de noms de sociétés, chacune avec un unique company_id.

Je veux être en mesure d'analyser à travers la chaîne et d'attribuer à chaque utilisateur d'inscription des noms de société une correspondance floue.

Dès maintenant, il suffit de faire un straight-up de la chaîne de match, est aussi lent. ** Les Soundex indexation être plus rapide? Comment puis-je donner à l'utilisateur des options de frappe? **

Par exemple, quelqu'un a écrit:

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

J'ai trouvé les threads suivants qui semblent similaires à cette question, mais l'affiche n'a pas approuvé et je ne suis pas sûr si leurs cas d'utilisation est applicable:

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

L'appariement inexact noms de société en Java

Désolé pour la mauvaise édition, j'ai négligé le second lien.
Ma réponse ci-dessous permettra d'éliminer la nécessité d'une recherche floue et fournira indexés à la recherche de tout nom partiel - check it out!

OriginalL'auteur AFG | 2008-12-15

51

Vous pouvez commencer avec l'aide de SOUNDEX(), ce sera sans doute ce qu'il vous faut (j'ai l'image d'une auto-suggestion boîte de déjà-les alternatives existantes pour ce que l'utilisateur tape).

Les inconvénients de SOUNDEX() sont:
- son incapacité à différencier des chaînes plus longues. Seulement les premiers caractères sont pris en compte, en plus des chaînes de caractères qui diffèrent à la fin de générer le même SOUNDEX valeur
- le fait que la première lettre doit être le même ou vous ne trouverez pas un match facile. SQL Server a une DIFFÉRENCE (de) fonction pour vous dire combien les deux SOUNDEX valeurs sont à part, mais je pense que MySQL n'a rien de ce genre à être construit dans.
- pour MySQL, au moins selon les docs, SOUNDEX est brisé pour la saisie unicode
Exemple:
```
SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */
```
Pour les plus avancés besoins, je pense que vous avez besoin de regarder le Levenshtein (également appelé "distance d'édition") de deux chaînes et de travailler avec un seuil. C'est le plus complexe (=plus lent) de la solution, mais il permet une plus grande flexibilité.

Principal inconvénient est que vous avez besoin de chaînes pour calculer la distance entre eux. Avec SOUNDEX vous pouvez stocker un pré-calculé SOUNDEX dans votre tableau et comparer/tri/groupe/filtre sur que. Avec la distance de Levenshtein, vous trouverez peut-être que la différence entre "Microsoft" et "Nzcrosoft" est à seulement 2, mais il faudra beaucoup plus de temps pour arriver à ce résultat.

En tout cas, un exemple de Levenshtein fonction for MySQL peut être trouvé à codejanitor.com: Levenshtein comme MySQL Fonction Stockée (Fév. 10th, 2007).

Utiliser les deux; sélectionner un premier ensemble de résultats à l'aide soundex, le tri et la possibilité de filtrer les résultats par Levenshtein.
Toujours la "première lettre" du problème qui doit être pris en charge. Si vous commencez à taper avec la mauvaise lettre, le SOUNDEX les résultats seront mis en place.
Je n'attends pas de filtrage nécessaire - je ne pas attendre, il y aura trop de correspondances possibles; plutôt pas assez (ou pas les bons). Ensuite, il ne vous aide pas à éliminer certains d'entre eux.
Peut-être. Si le nombre d'options est limité, et qu'un utilisateur est présenté d'une simple zone de liste déroulante, SOUNDEX sans complications suffira.
Levenshtein est un bel algorithme. Mais il n'est pas susceptible d'être optimisé par tout type d'index, comme SOUNDEX ou double Metaphone peut-être. Donc, si votre entreprise de base de données est grande, votre caractère par caractère match-suggestion pourrait s'avérer très coûteuse.

OriginalL'auteur Tomalak
22

SOUNDEX est OK algorithme pour cela, mais il y a eu des avancées récentes sur ce sujet. Un autre algorithme a été créé appelé le Metaphone, et il a ensuite été révisé à un Double Metaphone algorithme. J'ai personnellement utilisé le java apache commons mise en œuvre de la double metaphone et il est personnalisable et précis.

Ils ont mises en œuvre dans beaucoup d'autres langues sur la page de wikipedia pour elle, trop. Cette question a été posée, mais si vous trouvez l'un des problèmes identifiés avec le SOUNDEX figurant dans votre application, il est bon de savoir que il ya des options. Parfois, il peut générer le même code pour les deux mots différents. Double metaphone a été créé pour aider à prendre soin de ce problème.

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

Comme une réponse à des lacunes dans les
L'algorithme Soundex, Laurent Philips
développé l'algorithme Metaphone pour
dans le même but. Philips plus tard
développé une amélioration de Metaphone,
qu'il a appelé Double Metaphone.
Double Metaphone comprend un bien
les grandes règles de codage ensemble de ses
prédécesseur, gère un sous-ensemble de
caractères non latins, et renvoie un
primaire et secondaire de l'encodage
compte pour les différentes prononciations
d'un seul mot en anglais.

Au bas de la double metaphone page, ils ont en œuvre pour toutes sortes de langages de programmation: http://en.wikipedia.org/wiki/Double-Metaphone

Python & MySQL mise en œuvre: https://github.com/AtomBoy/double-metaphone

MySQL Double Metaphone de la mise en œuvre est en mouvement sur: atomodo.com/code/double-metaphone
veuillez noter que levenshtein est très très lourd sur une base de données, sauf si vous êtes en mesure de normaliser les données, il n'est pas une bonne option pour un moyen-lourd utilisé le site.
dm fonction donne des résultats précis, comme un exemple, consultez la sortie de ci-dessous deux OÙ est, OÙ dm(prenom) = dm('james') OÙ SOUNDEX(prenom) = SOUNDEX('james')

OriginalL'auteur Cheese Daneish
9

Tout d'abord, je tiens à ajouter que vous devez être très prudent lors de l'utilisation de toute forme de Phonétique/Fuzzy Algorithme de mise en Correspondance, comme ce genre de logique est exactement ça, Floue ou pour le dire plus simplement, potentiellement inexactes. Particulièrement vrai lorsqu'il est utilisé pour l'appariement des noms de société.

Une bonne approche est de chercher à corroborer d'autres données, telles que l'adresse, le code postal, les nombres de téléphone, Geo Coordonnées, etc. Cela permettra de confirmer la probabilité de vos données soit correctement appariés.

Il y a tout un éventail de questions liées à B2B Appariement de Données trop nombreuses pour être abordé ici, je l'ai écrit plus sur Nom De La Société Correspondant dans mon blog, mais en résumé, les principaux problèmes sont:
- À la recherche à l'ensemble de la chaîne est en vain que la partie la plus importante
  d'un Nom de Société n'est pas nécessairement au début de la Société
  Nom. c'est à dire "Le Proctor et Gamble Company" ou " Fédéral des États-unis
  Réserve"
- Abréviations courantes dans les Noms de Société c'est à dire HP, GM, GE, P&G,
  D&B, etc..
- Certaines entreprises délibérément épeler leurs noms incorrectement dans le cadre de
  leur image de marque et de se différencier des autres entreprises.
Correspondance exacte des données est facile, mais correspondant à des non-exacte des données peut être beaucoup plus de temps et je dirais que vous devriez considérer comment vous allez la validation de la non-correspondances exactes pour s'assurer qu'ils sont de qualité acceptable.

Avant de nous construit Match2Lists.com, nous avons consacré énormément de temps à la validation des correspondances floues. Dans Match2Lists nous avons incorporé un puissant outil de Visualisation permettant d'examiner les non-correspondances exactes, cela s'est avéré être un véritable changeur de jeu en termes de match de validation, de réduire nos coûts et nous permettant de fournir des résultats beaucoup plus rapidement.

Bonne Chance!!

OriginalL'auteur Derren
4

Voici un lien vers le php discussion de la soundex fonctions dans mysql et php. J'aimerais commencer à partir de là, puis développez vos autres pas-si-bien-exigences définies.

Votre référence références Levenshtein méthodologie pour la mise en correspondance. Deux problèmes. 1. Il est plus approprié pour la mesure de la différence entre les deux mots connus, pas pour la recherche. 2. Il présente une solution destiné à détecter des choses comme les erreurs d'édition (à l'aide de "Levenshtien" pour "Levenshtein") plutôt que de fautes d'orthographe (où l'utilisateur ne sait pas comment l'écrire, dire "Levenshtein" et les types "Levinstein". J'ai l'habitude de l'associer à la recherche d'une phrase dans un livre plutôt que d'une valeur de clé dans une base de données.

EDIT: En réponse au commentaire--
1. Pouvez-vous obtenir au moins les utilisateurs à mettre les noms de la société en de multiples zones de texte; 2. ou utiliser un unambigous nom de délimiteur (disons barre oblique inverse); 3. laissez de côté les articles ("Le") et les génériques des abréviations (ou vous pouvez filtrer ces); 4. Squoosh les espaces et faire correspondre aussi (donc Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Filtrer la ponctuation; 6. Faire "OU" les recherches sur les mots ("nu" OU "essentiels") - les gens vont inévitablement laisser l'un ou l'autre parfois.
De Test comme un fou et l'utilisation de la boucle de rétroaction auprès des utilisateurs.

D'autres exigences il serait utile?
Ajouté que les modifications à la réponse ci-dessus.
+1 pour le "Levenshtein est conçu pour détecter les erreurs d'édition plutôt que de fautes d'orthographe"

OriginalL'auteur dkretz
0

la meilleure fonction pour la correspondance floue est levenshtein. il est traditionnellement utilisé par les vérificateurs d'orthographe, de sorte que pourrait être le chemin à parcourir. il y a un UDF de il disponible ici: http://joshdrew.com/

l'inconvénient à l'utilisation de levenshtein est qu'il ne pas très bien. une meilleure idée pourrait être de faire un dump de la totalité de la table dans un correcteur d'orthographe fichier de dictionnaire et de faire une suggestion du niveau de votre application au lieu de la couche de base de données.

OriginalL'auteur
0

Ce résultat réponses indicielles de recherche de presque n'importe quelle entité en utilisant la saisie de 2 ou 3 caractères ou plus.

Fondamentalement, créer une nouvelle table avec 2 colonnes, mot clé. Exécuter un processus original sur la table contenant la colonne à être floue recherché. Ce processus permettra d'extraire chaque mot de la colonne d'origine et d'écrire ces mots au tableau word avec la clé d'origine. Au cours de ce processus, fréquentes des mots comme 'la','et', etc doivent être jetés.

Nous avons ensuite créer plusieurs indices sur le mot table, comme suit...
- Normal, minuscule indice sur le mot de la touche +
- Un index sur la 2ème et la 5ème caractère de la touche +
- Un index sur la 3e de la 6e caractère de la touche +
  
  Alternativement, créer un SOUNDEX() index sur la colonne "mot".
Une fois cela en place, nous prenons toutes les entrées de l'utilisateur et de recherche à l'aide de word normal = entrée ou COMME entrée%. Nous ne faisons jamais une %d'entrée que nous sommes toujours à la recherche d'un match sur l'un des 3 premiers caractères, qui sont indexés.

Si l'original de votre table est massive, vous pouvez partitionner le tableau word par morceaux de l'alphabet pour assurer l'entrée de l'utilisateur est limité à un candidat lignes immédiatement.

OriginalL'auteur Rodney P. Barbati

Vous devez vous connecter pour publier un commentaire.