J'ai une table contenant 3 millions de personnes enregistrements sur lesquelles je veux effectuer une correspondance floue à l'aide de q-grammes (sur le nom de famille par exemple). J'ai créé une table de 2 grammes de liaison à cela, mais la performance de recherche n'est pas géniale sur ce volume de données (environ 5 minutes).
J'ai essentiellement deux questions: (1) Pouvez-vous suggérer des moyens d'améliorer les performances pour éviter une analyse de table (c'est-à-dire avoir à compter compter des q-grammes communs entre la chaîne de recherche et 3 millions de noms de famille) (2) avec q-grammes, si A est similaire à B et C est similaire à B, cela implique-t-il C est similaire à un?
genre considère
Peter
4 Réponses :
Je l'ai cherchée en correspondance de chaîne floue ces derniers temps, même au risque de répondre à une question abandonnée, voilà. Espérons que vous trouverez ce utile.
Je suppose que vous n'êtes intéressé que par les chaînes pour lesquelles la distance d'édition est inférieure à une valeur donnée. Et vos q-grammes (ou n-grammes) se présentent comme suit p>
2-gram "fo" exists in with position from 1 to 3 or 2-gram "oo" exists in with position from 2 to 4 or ... and so on
papier intéressant sur l'indexation de l'ADN q-grammes afin que vous n'ayez pas à numériser toute la table:
www.comp.nus.edu.sg/~atung/publication/qgram_edit.pdf
Vous avez certainement vu les recherches de texte floue partout. Par exemple, vous tapez "stck" mais vous voulez dire "pile"! Vous êtes-vous déjà demandé comment cela fonctionne-t-il?
Il y a beaucoup d'algorithmes pour faire une correspondance de texte floue, chacune avec son propre pro et ses inconvénients. Les plus célèbres sont la distance d'édition et le qgram. Je tiens à vous concentrer sur QGrams aujourd'hui et à mettre en place un échantillon. P>
essentiellement qgrams est l'algorithme de chaîne floue la plus approprié pour des bases de données relationnelles. C'est assez simple. "Q" dans QGram sera remplacé par un numéro comme 2 grammes ou 3 grammes ou même 4 grammes. P>
2 gram signifie que chaque mot est cassé en un ensemble de deux grammes de caractères. "Stack" sera cassé en un ensemble de {"ST", "Ta", "CK", "CK"} ou "Base de données" sera cassé en {"Da", "AT", "TA", "AB "," Ba "," comme "," SE "}. p>
Une fois que les mots sont cassés en 2 grammes, nous pouvons rechercher la base de données pour un ensemble de valeurs au lieu d'une chaîne. Par exemple, si l'utilisateur malypéd "STCK", toute recherche "STCK" ne correspondra pas "Stack" car "A" est manquant, mais le jeu de 2 grammes {"st", "tc", "ck"} a 2 rangées en commun avec l'ensemble de pile de 2 grammes! Bingo Nous avons trouvé un match assez étroit. Il n'a rien de commun avec l'ensemble de données de 2 grammes de base de données et seulement 1 en commun avec l'ensemble de 2 grammes de "statistique" afin que nous puissions facilement suggérer l'utilisateur qu'il voulait taper: première "pile" ou second ", star ". P>
Maintenant, activons-le à l'aide de SQL Server: supposons un jeu de données de mots hypothétiques. Vous devez avoir beaucoup de relations entre 2 grammes et mots. P>
DECLARE @word TABLE(twog char(2)) -- 'stack'
INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')
select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
GROUP BY wordId
J'ai une simple amélioration qui n'éliminera pas le scan, mais accélérerez-le si vous utilisez 2 grammes ou 3 grammes uniquement: remplacez les lettres par chiffres. La plupart des moteurs SQL travaillent beaucoup plus vite lors de la comparaison de numéros.
Exemple: Notre tableau source contient des entrées de texte dans une colonne.
Nous créons une table Temp où nous avons divisé les noms en 2 grammes à l'aide d'un ceci doit fonctionner dans une boucle où i = 0 et j = la taille maximale d'une source Entrée. Ensuite, nous préparons une table de mappage contenant toutes les grammes de 2 lettres possibles et incluent une colonne Identité (1,1) appelée gram_id. Nous pouvons trier les grammes par fréquence dans le dictionnaire anglais et éliminer les grammes les plus rares (comme 'kk' ou «WQ») - ce tri peut prendre un certain temps et de rechercher, mais il attribuera les plus petits nombres aux grammes les plus fréquents, qui Va ensuite améliorer les performances si nous pouvons limiter le nombre de grammes à 255 car nous pouvons utiliser une colonne Tinyint pour le gram_id. Ensuite, nous reconstruisons une autre table Temp du premier, où nous utilisons le gram_id au lieu de la gramme. Cela devient la table principale. Nous créons un index sur la colonne Gram_id et sur la colonne Position. Ensuite, lorsque nous devons comparer une chaîne de texte à la table principale, nous avons d'abord divisé la chaîne de texte divisée en 2 grammes, puis remplacez les 2 grammes par leur gram_id (à l'aide de la table de mappage), et comparez-les à celui de la table principale qui fait beaucoup de comparaisons, mais la plupart d'entre eux sont des entiers à 2 chiffres, ce qui est très rapide.