Détection/hachage de texte en double

Question

J'ai des ensembles de chaînes dans une base de données. Chaque ensemble aura moins de 500 membres, il y aura des dizaines de milliers d'ensembles, et les cordes sont en langage naturel. Je voudrais détecter les chaînes en double dans chaque ensemble. Les nouvelles chaînes seront comparées à un ensemble existant et ajoutées à la base de données si elles sont uniques. Y at-il des algorithmes de hachage qui seraient efficaces pour trouver des chaînes (très) similaires? Par exemple, les chaînes auraient probablement le même nombre de mots, mais le codage pourrait être légèrement différent (UTF-8 vs Latin-1).

Answer 1

Pour commencer, vous devriez probablement faire une sorte de normalisation. Vous devriez probablement convertir tout votre texte en un seul encodage (ex: UTF-8). Vous pouvez également faire le cas-pliage, autre Unicode normalizations et peut-être aussi trier chaque ensemble (selon la façon dont vous les stockez).

Je ne sais pas d'après votre question si vous voulez trouver des correspondances exactes ou juste des ensembles de chaînes qui sont "similaires". Si vous vous souciez seulement des correspondances exactes une fois la normalisation prise en compte, alors vous avez à peu près terminé. Ayez juste un index sur les formes normalisées de vos ensembles de chaînes et vous pouvez rapidement rechercher de nouveaux ensembles en les normalisant aussi.

Si vous voulez trouver des correspondances proches, alors vous voudrez probablement faire une sorte de hachage de similarité. L'article Wikipedia sur Locality Sensitive Hashing décrit un certain nombre de techniques.

L'idée de base d'un certain nombre de ces techniques est de calculer une poignée de hachages très à perte sur chaque chaîne, h [0] à h [n]. Pour rechercher un nouvel ensemble de chaînes, vous devez calculer ses hachages et rechercher chacune d'entre elles. Tout ce qui obtient au moins une correspondance est "similaire", et plus il y a de correspondances, plus elle est similaire (et vous pouvez choisir le seuil à partir duquel couper).

Answer 2

S'il n'y a que 500 chaînes dans la base de données, vous pouvez peut-être comparer directement chacune d'entre elles. D'abord convertir en une représentation standard (disons UTF-16). Le Levenshtein distance peut être un bon moyen de comparer la similarité de deux chaînes.

Answer 3

La réponse courte est juste de deviner à quel bon paramètre de hachage correspond votre idée de "similaire".

Probablement juste quelque chose comme la somme de toutes les lettres (A) et la somme des différences entre les lettres adjacentes (B), pourrait fonctionner. Pour chaque nouvelle chaîne, utilisez ses valeurs A et B pour rechercher rapidement un ensemble de chaînes similaires maintenant beaucoup plus petit, puis faites une comparaison plus précise entre celles-ci.

Ce n'est probablement pas la solution la plus pure, mais en pratique, beaucoup de problèmes sont résolus de cette façon. Au-delà, je pense qu'il y a actuellement beaucoup de travail pour résoudre des problèmes similaires en génétique (c'est-à-dire trouver des séquences de gènes similaires dans d'énormes bases de données), mais je ne pense pas qu'il existe une solution générique à ce problème.

Answer 4

Cela peut être exagéré, mais vous pouvez essayer NLTK (Natural Language Toolkit), qui est basé sur Python. Une caractéristique qui pourrait être utile est de analyze sentence structure. Bien sûr, cela pourrait conduire à ce que certaines chaînes soient marquées comme doublon parce qu'elles ont la même structure grammaticale, mais des mots et une signification différents.

Vous pourriez également utiliser les fonctions de probabilité et de classification.

Answer 5

vous pourriez devenir fou et essayer l'analyse sémantique latente/cartographie et la décomposition de valeurs singulières: latent semantic mapping

avec SVDLIBC, ce qui est assez facile d'y aller avec.

Answer 6

This post sur mon blog peut être d'intérêt.

Une description de l'algorithme et un lien vers le code sont fournis. En bref, il s'agit d'une approche basée sur n-grammes qui ne fait aucune hypothèse sur le contenu ou la structure de l'entrée, et génère des signatures de longueur constante pour tous les documents d'entrée.