J'ai une table dans MySql avec des noms dedans. J'essaie, étant donné un nom d'entrée, de trouver tous les noms similaires dans le tableau. J'ai beaucoup entendu parler de la distance Levenshtien / Damerau – Levenshtein, mais il ne semble pas que cela fonctionne bien pour cela, j'expliquerai mon raisonnement plus tard.

Élaborer:

  • L'utilisateur entre un nom qui peut contenir, par exemple, cinq mots. Pour cet exemple, disons que le nom entré est «Juan Manuel Beldad».
  • J'essaye de trouver des noms similaires dans la base de données. Disons que la base de données comprend
    1. "Juan Beldad" (deuxième prénom manquant)
    2. "Juan Belded" (Belded et non Beldad)
    3. "Juan Manuel Sebastian Beldad" (deuxième prénom)
  • Je retourne les eux dans l'ordre duquel jamais on est plus proche de l'entrée, dans ce cas, ce serait: "Juan Beldad", "Juan Belded", "Juan Manuel Sebastian Beldad"

Mon raisonnement pour remettre en question l'utilisation de la distance Levenshtien / Damerau – Levenshtein dans ce cas est qu'il ne serait pas capable de détecter correctement les noms supplémentaires ou les noms manquants. Ma compréhension de la distance de Levenshtien est qu'elle trouve le nombre minimum de modifications à un seul caractère (insertions, suppressions ou substitutions) nécessaires pour changer un mot dans l'autre. Ainsi, ce qui suit serait considéré comme étant la même distance par rapport à la chaîne d'origine.

Original string: "Juan Beldad"
Want to find: "Juan Manuel Beldad"
(7 character insertion)
Would also find: "Mike Bell"
(5 character substitution (M-i-k-e-l), 2 character deletion(a-d))

Puisque les deux ont une distance de 7 montages, "Mike Bell" serait considéré à égale distance de "Juan Beldad" comme "Juan Manuel Beldad".

Je pensais interroger la base de données en supprimant le (s) deuxième (s) prénom (s) à la fois en entrée et côté table, puis faire une distance Levenshtien / Damerau – Levenshtein? Est-ce que je réfléchis trop à cela et y a-t-il une meilleure façon de le faire?

2
Bubinga 16 août 2020 à 02:58

2 réponses

Meilleure réponse

Il existe de nombreux problèmes possibles dont vous devez tenir compte lors de la correspondance des noms. Certains d'entre eux sont:

  • surnoms (Bob - Robert)
  • fautes de frappe
  • échange de nom (nom de famille remplacé par le prénom)
  • nom de jeune fille
  • initiales
  • noms tronqués
  • nom phonétiquement similaire (Jennifer - Jenny)

La distance Damerau – Levenshtein est l'un des modifier les algorithmes de distance que vous pouvez utiliser. Chaque algorithme prend en compte différentes opérations (insertion de caractères, remplacement, suppression, échange, etc.) et aucun n'est parfait mais chacun fournit une distance entre deux chaînes.

Vous devez décider du niveau d'erreur acceptable pour vous (c'est-à-dire le seuil des correspondances positives). L'exemple que vous avez donné comprend au minimum 7 opérations. Dans ces nombreuses opérations, de nombreux noms renverront la même distance.

Lorsque vous comparez des noms, vous devez essayer de rendre les deux côtés comparables en les normalisant: si un côté n'a que la première lettre du prénom par exemple, vous devez faire la même chose de l'autre côté afin que l'algorithme de distance d'édition vous donne un meilleur résultat .

De même, vous pouvez vous débarrasser du deuxième prénom si l'autre côté n'a pas le deuxième prénom (et vous pouvez ignorer les cas où un deuxième prénom est entré comme prénom). Mais une meilleure alternative est de générer toutes les paires de noms possibles en utilisant tous les mots disponibles dans un nom et de voir si l'une des paires produira une meilleure distance d'édition. Vous pouvez également comparer chaque mot seul et trouver la meilleure combinaison de mots avec le meilleur score (le compromis est d'ignorer les fautes de frappe aux limites des mots).

Vous devriez également envisager d'utiliser un algorithme de similarité phonétique comme Double Metaphone en plus de Damerau – Levenshtein et générer un score combiné. Les algorithmes phonétiques sont conçus pour une famille de langues spécifique et essaient de déterminer si les deux noms sembleraient similaires dans cette famille de langues. Le résultat n'est pas fiable en soi (au moins mon expérience était comme ça), mais cela, combiné à un algorithme d'édition de distance, améliorera votre correspondance.

Pour réduire le taux d'erreur, des éléments de données supplémentaires doivent être considérés comme ZIP, DOB, etc.

En fin de compte, tout est question de compromis: votre cas d'utilisation prévu, votre seuil acceptable pour les correspondances positives, la qualité de vos données, les limites de temps / coût, etc. Par exemple: vous pourriez simplement exiger la première lettre de la première le nom et la première lettre du nom de famille doivent être identiques en plus de la distance Damerau – Levenshtein. Cela réduira le pool de faux positifs avec un compromis ignorant les fautes de frappe aux premières lettres.

Comme dans beaucoup de choses de nos jours, je pense que le meilleur résultat dans ce domaine pourrait être obtenu grâce à un modèle d'apprentissage automatique bien formé. Je n'ai pas travaillé dans ce domaine depuis un certain temps, donc je ne suis pas sûr de ce qui existe, mais vous pourriez probablement trouver une bonne solution basée sur le cloud pour les meilleurs matchs de qualité, moyennant des frais bien sûr, si cela est important pour vous.

Vous pouvez voir un aperçu des techniques de correspondance de noms ici en tant que lecture supplémentaire.

2
K4M 16 août 2020 à 06:20

J'ai fini par faire Jaro-Winkler Distance avec un code de gestion de deuxième prénom. J'ai volé ma distance Jaro-Winkler à l'utilisateur leebickmtu ici btw. Donc, essentiellement, ce que je fais est:

  1. Supprimer le (s) deuxième (s) prénom (s) du nom d'entrée et les compter
  2. Obtenez tous les noms de la base de données avec lesquels vous souhaitez comparer
  3. Supprimez tous les seconds prénoms des noms de base de données et comptez-les
  4. Exécutez Jaro-Winkler sur le nom d'entrée sans deuxième prénom (s) vers les noms de base de données sans deuxième prénom (s). Arrêtez-vous ici pour les noms en dessous d'un seuil
  5. Pour chaque deuxième prénom, ajoutez une valeur au score Jaro-Winkler pour ce nom. J'ai choisi au hasard 1 / 35ème et cela semble fonctionner assez bien pour mes besoins.
  6. Trier par score
  7. Revenez à la base de données avec une liste de noms triés (maintenant plus courte) et obtenez les informations supplémentaires que vous souhaitez.
0
Bubinga 4 sept. 2020 à 02:45