Algorithme pour trouver le pourcentage de l'identique de deux textes

Question

Quel algorithme suggéreriez-vous pour identifier combien de 0 à 1 (float) deux textes sont identiques? Notez que je ne veux pas dire similaire (ie, ils disent la même chose mais d'une manière différente), je veux dire exactement les mêmes mots, mais l'un des deux textes pourrait avoir des mots supplémentaires ou des mots légèrement différents ou extra nouveaux des lignes et des trucs comme ça.

Un bon exemple de l'algorithme que je veux est celui que Google utilise pour identifier le contenu dupliqué dans les sites Web (X résultats de recherche très similaires à ceux qui ont été omis, cliquez ici pour les voir).

La raison pour laquelle j'en ai besoin est que mon site Web permet aux utilisateurs de poster des commentaires; Des pages similaires mais différentes ont actuellement leurs propres commentaires, donc beaucoup d'utilisateurs ont fini par copier & en collant leurs commentaires sur toutes les pages similaires. Maintenant, je veux les fusionner (toutes les pages similaires "partageront" les commentaires, et si vous les publiez sur la page A, ils apparaîtront sur la même page B), et je voudrais effacer par programme tous ces commentaires copiés de la même utilisateur.

J'ai quelques millions de commentaires mais la vitesse ne devrait pas être un problème car c'est une chose qui se déroulera en arrière-plan.

Le langage de programmation n'a pas vraiment d'importance (tant qu'il peut s'interfacer avec une base de données MySQL), mais je pensais le faire en C++.

Answer 1

Est-ce que l'algorithme Longest Common Subsequence remplirait la facture? C'est essentiellement ce que diff utilise. Il existe un algorithme de programmation dynamique qui vous permet de résoudre de tels problèmes efficacement. La page Wikipédia à laquelle je suis connecté contient toutes les informations dont vous avez besoin.

Pour l'expérimenter de manière agréable et conviviale, vous pouvez utiliser le module Python difflib qui l'implémente. Il contient une classe difflib.SequenceMatcher qui possède une méthode ratio, qui:

retour une mesure de similarité de séquences comme un flotteur dans l'intervalle [0, 1].

où T est le nombre total d'éléments dans les deux séquences, et M est le nombre de correspondances, ceci est 2,0 * M/ T. On notera que ceci est de 1,0 si les séquences sont identiques , et si 0,0 ils n'ont rien en commun.

Answer 2

Des comparaisons de similarité robustes, par ex. Levenshtein distance sont généralement coûteux. Avec de nombreux textes différents à comparer, vous rencontrez également le problème d'un nombre immense de comparaisons potentielles par paires.

Une technique plus pratique pour votre cas serait probablement l'empreinte digitale de Karb-Rabin.

Answer 3

Cosine Similarity

Dans le cas de la recherche d'information, la similitude cosinus de deux documents variera de 0 à 1, étant donné que le terme fréquences (poids de TF-IDF) ne peuvent pas être négatif. L'angle entre deux vecteurs de fréquence ne peut pas être supérieur à qu'à 90 °.- Wikipédia

EDIT:

pages similaires mais différentes ont actuellement leurs propres commentaires, tant d'utilisateurs ont fini par copier et coller leurs commentaires sur toutes les pages similaires.

Cette similitude peut être exploitée.

1. Rechercher des fichiers similaires.
2. Trouver des utilisateurs COMMUN aux messages, ignorez simplement les autres.

Ce regroupement devrait permettre de réduire votre tâche :)

Answer 4

Cosinus similarité est une bonne mesure. Voir les chapitres 6-7 de Introduction à la recherche d'information au http://nlp.stanford.edu/IR-book/information-retrieval-book.html