Correspondance partielle de noms dans des millions d'enregistrements

10

Nous avons développé une application Web pour l'appariement des noms. Il fonctionne en divisant les noms en parties et la valeur Soundex de chaque partie est stockée dans une base de données. La métrique de distance Levenshtein est utilisée pour appliquer la correspondance en pourcentage du son ainsi que l'orthographe par rapport à un nom donné.

Au moment de l'exécution, nous chargeons tous les enregistrements en mémoire et appliquons la distance Levenshtein à toutes les valeurs Soundex et l'orthographe de toutes les parties de tous les noms.

Cela fonctionnait bien au début, car il y avait au maximum 20 000 noms, mais maintenant l'un de nos clients a 30 millions de noms. Charger cette énorme liste en mémoire pour chaque requête et appliquer ce type de correspondance est une approche pathétique, utilisant beaucoup de mémoire et de temps d'exécution.

Nous recherchons des suggestions pour rechercher dans la base de données de 30 millions d'enregistrements ou plus dans un avenir proche avec un pourcentage de correspondance entre le son et l'orthographe.

Fonctionnalité de base

L'utilisateur final saisit le nom à mettre en correspondance et le pourcentage minimum. Nous sommes censés afficher tous les noms dans la base de données pour lesquels une partie du nom correspond à une partie du nom donné jusqu'au pourcentage donné. Il n'est pas nécessaire de faire correspondre le nom complet, n'importe quelle partie si les correspondances jusqu'au pourcentage sont réussies. Par exemple.

Given Name: Helen Hunt
Name in DB: Holly Hunter 

Les deux parties des deux noms ne correspondent pas exactement, mais dans une certaine mesure, supposons 80%, donc si l'utilisateur entre 80%, le nom dans la base de données doit être affiché comme nom correspondant.

bjan
la source
1
Utilisez-vous SQL Server? Je vois que vous l'avez étiqueté asp.net. Penser à la possibilité d'un assemblage CLR qui empêcherait le trafic réseau et laisserait le serveur SQL gérer la mémoire.
RubberChickenLeader
@WindRaven nous utilisons à la fois SQL Server et Oracle
bjan
1
N'est-ce pas le même problème d'exploration de Google que Google résout?
candied_orange
@bjan où sont stockés les noms? sont-ils stockés dans SQL Server?
RubberChickenLeader
Que cherchez-vous? Les 100 premiers noms qui correspondent le mieux à une requête donnée?
Doc Brown

Réponses:

6

Sans connaître tous les détails de ce dont vous avez besoin, vous souhaiterez probablement effectuer l'une des opérations suivantes:

Je ne sais pas vraiment ce que cela implique d'installer et de configurer sphinx; mais j'ai l'impression que vous pouvez le pointer vers une base de données, lui dire quels champs indexer, comment pondérer les résultats, et cela vous donnera une liste ordonnée d'enregistrements correspondants.

Pour les informations destinées aux utilisateurs ou critiques, utilisez un outil de recherche existant.

Si vous vous sentez juste académique ... Jouez avec les ngrams:

Une table de recherche ngrams peut servir de votre ensemble initial de correspondances potentielles, et vous pouvez utiliser les distances de Levenshtein pour tailler et trier les résultats.

En supposant que vous vouliez rechercher people, vous pourriez faire quelque chose comme:

_ people _________
personId: int
name: varchar
soundex_name: varchar

_ people_ngrams __
personId: int
ngramId: int

_ ngrams _________
ngramId: int
ngram: char(3)
count: int

Vous pouvez soit reconstruire périodiquement vos ngrams, soit les construire à la volée. Quoi qu'il en soit, un algorithme de recherche simple et naïf peut ressembler à ceci:

search_ngrams = ngrammify(soundex(search_string));

notable_ngrams = select top 10 *
  from ngrams
  where ngram in (search_ngrams)
  order by count asc;

possible_matches = select top 1000 distinct people.*
  from people_ngrams, people
  where ngramId in (notable_ngrams);

best_matches = top 100 possible_matches
  ordered by Levenshtein_distance(match, soundex(search_string));

En utilisant quelque chose d' assez similaire à cela (mais avec un peu plus de réglage de «popularité» de ngram, de listes noires, de listes blanches, etc.), j'ai vu ce type d'algorithme fusionner de manière floue les enregistrements entre les ensembles de données en vrac, ainsi que faciliter la recherche floue personnalisée les services publics et les efforts continus de déduplication des dossiers.

Maintenant, dans mon cas, je ne correspondais pas à des millions d'enregistrements, je cherchais à sélectionner les meilleures fusions possibles entre deux ensembles de données de l'ordre de centaines de milliers d'enregistrements chacun. Et, nous voulions que cela fonctionne assez rapidement - en quelques minutes. (Vite, qu'est-ce que 100 000 * 100 000?) Et, nous avons réussi.

Donc, avec le bon réglage, ce genre de chose peut être rapide et efficace. Nous avons finalement pu produire un ensemble fusionné sur une machine dual-core humble et datée en quelques minutes, avec des fusions "douteuses" automatiquement signalées pour une révision manuelle. Mais, il a fallu beaucoup de temps pour trouver le point idéal de popularité / pertinence du ngram, et les bons seuils de distance de chaîne, et les listes noires et les listes blanches ... etc.

Cela dit , vous pouvez vraiment être aspiré dans un trou en travaillant sur ce genre de choses. Pour tout élément de production réel, vous devez généralement utiliser un outil bien établi qui est déjà conçu et optimisé pour ce type de recherche.

Comme Sphinx ou Lucene .

svidgen
la source
Je viens de chercher floue sur le manuel de référence de la version 2.2.11 de Sphinx et il semble qu'il correspond au mot exact alors que je dois faire correspondre les mots partiellement. Corrigez-moi si je me trompe.
bjan
@bjan Ouais. En regardant les documents plus loin, je ne suis pas sûr que la recherche floue de Sphinx soit exactement ce que vous recherchez. Il peut utiliser une morphologie soundex . Mais, en fonction de votre modification récente, vous souhaiterez peut -être lancer votre propre recherche ngram + distance de chaîne. Et comme je l'ai dit ci-dessus, il peut prendre un certain temps pour modifier l'algorithme et les seuils pour obtenir le bon résultat; mais ce n'est pas impossible. Et, si vous avez besoin de ce niveau de flexibilité ...
svidgen
@bjan Oh, j'ai aussi totalement oublié Lucene . Je ne suis pas sûr qu'il fasse ce dont vous avez besoin non plus; mais, il est très populaire et mérite d'être examiné avant de lancer le vôtre. Les documents de Lucene mentionnent des recherches floues et des classements utilisant la distance de chaîne Levenshtein.
svidgen