Comment trouver la meilleure correspondance floue pour une chaîne dans une base de données de grandes chaînes
j'ai une base de données de chaînes (longueur arbitraire) qui contient plus d'un million d'articles (potentiellement plus).
j'ai besoin de comparer une chaîne fournie par l'utilisateur avec l'ensemble de la base de données et de récupérer une chaîne identique si elle existe ou autrement retourner les correspondances floues les plus proches(60% de similarité ou mieux). Le temps de recherche devrait idéalement être inférieur à une seconde.
mon idée est d'utiliser la distance d'édition pour comparer chaque chaîne de db à la recherche chaîne après rétrécissement des candidats de la db en fonction de leur longueur.
cependant, comme je vais devoir effectuer cette opération très souvent, je pense à construire un index des chaînes de base de données pour garder en mémoire et interroger l'index, pas la base de données directement.
des idées sur la façon d'aborder ce problème différemment ou comment construire l'index en mémoire?
7 réponses
Ce papier semble décrire exactement ce que vous voulez.
Lucène ( http://lucene.apache.org / ) implémente également la distance D'édition de Levenshtein.
vous n'avez pas mentionné votre système de base de données, mais pour PostrgreSQL vous pouvez utiliser le module contrib suivant: trgm-trgram matching for PostgreSQL 151930920"
le module pg_trgm contrib fournit des fonctions et des classes d'index pour déterminer la similarité du texte basé sur la correspondance trigramme.
si votre base de données le supporte, Vous devriez utiliser la recherche en texte intégral. Sinon, vous pouvez utiliser un indexeur comme lucene et ses différentes implémentations.
calcule le hachage SOUNDEX (qui est construit dans de nombreux moteurs de base de données SQL) et l'index par lui.
SOUNDEX est un hachage basé sur le son des mots, de sorte que les fautes d'orthographe du même mot sont susceptibles d'avoir le même hachage SOUNDEX.
puis trouvez le hachage SOUNDEX de la chaîne de recherche, et faites correspondre.
étant donné que la quantité de données est importante, lors de l'insertion d'un enregistrement, Je calculerais et stockerais la valeur de l'algorithme phonétique dans une colonne indexée, puis je limiterais (clause WHERE) mes requêtes select à l'intérieur d'une plage sur cette colonne.
le livre Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology de Dan Gusfield fournit une explication très détaillée des algorithmes pertinents .
https://en.wikipedia.org/wiki/Levenshtein_distance
l'algorithme de Levenshtein a été implémenté dans certains SGBD
(E. G. PostgreSql: http://www.postgresql.org/docs/9.1/static/fuzzystrmatch.html )