Quels algorithmes puis-je utiliser pour détecter si des articles ou des publications sont des doublons?

17

J'essaie de détecter si un article ou un message sur le forum est une entrée en double dans la base de données. J'y ai réfléchi, en arrivant à la conclusion que quelqu'un qui duplique du contenu le fera en utilisant l'un des trois (en descendant difficile à détecter):

  1. copier simple coller tout le texte
  2. copier et coller des parties de texte en les fusionnant avec les leurs
  3. copier un article d'un site externe et se faire passer pour le mien

Préparation du texte pour l'analyse

Fondamentalement, toute anomalie; le but est de rendre le texte aussi "pur" que possible. Pour des résultats plus précis, le texte est "standardisé" par:

  1. Suppression des espaces blancs en double et découpage en début et en fin.
  2. Les retours à la ligne sont normalisés à \ n.
  3. Les balises HTML sont supprimées.
  4. L'utilisation d'un RegEx appelé Daring Fireball URL est supprimée.
  5. J'utilise du code BB dans mon application, donc ça va.
  6. (ä) les centres et les étrangers (outre l'anglais) sont convertis sous leur forme non étrangère.

Je stocke des informations sur chaque article dans (1) tableau de statistiques et dans (2) tableau de mots-clés.

(1) Tableau des statistiques Les statistiques suivantes sont stockées sur le contenu textuel (un peu comme ce post)

  1. longueur du texte
  2. nombre de lettres
  3. nombre de mots
  4. nombre de phrases
  5. mots moyens par phrase
  6. indice de lisibilité automatisé
  7. score de brouillard

Pour les langues européennes, Coleman-Liau et l'indice de lisibilité automatisé doivent être utilisés car ils n'utilisent pas le comptage des syllabes, ils devraient donc produire un score raisonnablement précis.

(2) Tableau des mots-clés

Les mots clés sont générés en excluant une énorme liste de mots vides (mots courants), par exemple, «le», «a», «de», «à», etc., etc.

Exemples de données

  • text_length, 3963
  • letter_count, 3052
  • word_count, 684
  • phrase_compte, 33
  • word_per_sentence, 21
  • gunning_fog, 11,5
  • auto_read_index, 9.9
  • mot-clé 1, tué
  • mot-clé 2, officiers
  • mot-clé 3, police

Il convient de noter qu'une fois qu'un article est mis à jour, toutes les statistiques ci-dessus sont régénérées et peuvent avoir des valeurs complètement différentes.

Comment puis-je utiliser les informations ci-dessus pour détecter si un article qui est publié pour la première fois existe déjà dans la base de données?


Je suis conscient que tout ce que je vais concevoir ne sera pas parfait, le plus grand risque étant (1) Le contenu qui n'est pas un doublon sera signalé comme dupliqué (2) Le système autorise le contenu en double à passer.

Par conséquent, l'algorithme doit générer un numéro d'évaluation des risques de 0 à aucun risque de double, 5 à double possible et 10 à double. Tout ce qui est supérieur à 5, il y a de fortes chances que le contenu soit en double. Dans ce cas, le contenu pourrait être signalé et lié aux articles qui sont des doublons possibles et un humain pourrait décider de supprimer ou d'autoriser.

Comme je l'ai dit auparavant, je stocke des mots clés pour l'ensemble de l'article, mais je me demande si je pourrais faire la même chose sur la base des paragraphes; cela signifierait également une séparation supplémentaire de mes données dans la base de données, mais cela faciliterait également la détection de (2) dans mon message initial.

Je pense en moyenne pondérée entre les statistiques, mais dans quel ordre et quelles seraient les conséquences ...

Michael
la source
S'il s'agit d'une correspondance exacte, vous pouvez simplement définir un champ comme unique. Sinon, vous devez décider à quel moment un texte peut être considéré comme une copie ou une œuvre étroitement dérivée.
James P.
2
Il existe de nombreuses directions dans lesquelles ce type d'analyse peut aller. Les gens écrivent des livres entiers sur ce genre de sujet. Si votre objectif est de déterminer la "proximité relative", vous n'avez vraiment pas d'autre choix que de creuser dans ce qu'on appelle le traitement du langage naturel et l' apprentissage automatique . C'est ce que les informaticiens appellent cela, mais ce n'est vraiment qu'une analyse statistique avancée. Un bon point de départ pourrait être d'examiner les distances de levenshtein, mais les statistiques "stupides" comme le nombre de mots / phrases vont probablement faire très peu pour vous.
rdlowrey
1
De plus, avant sa migration à partir de SO, cela a été marqué [php], vous pouvez donc vérifier la fonction native de levenshtein de php
rdlowrey
Excellente idée d'avoir une vérification humaine des doublons probables! Vous pouvez être en mesure de décider automatiquement que> 7 est un doublon et <6 est différent et que seuls les humains vérifient les scores de 6 ou 7. Je sais qu'avec l'identification du spam, il existe une machine-ne-sait-pas-ET-humain- ne sait pas non plus; une zone grise entre un quasi-doublon et une œuvre originale où le mieux que vous puissiez faire est de faire un jugement quelque peu arbitraire.
GlenPeterson
@rdlowrey - Les algorithmes de Levenshtein sont ce que j'ai utilisé dans un projet similaire que j'ai fait en C #. Je suis d'accord, c'est un bon point de départ et peut suffire.
jfrankcarr

Réponses:

4

Il existe de nombreux algorithmes qui traitent de la similitude des documents dans la PNL. Voici un article fondamental décrivant divers algorithmes. Aussi wikipedia a une plus grande collection. Je suis favorable à la mesure Jaro Winkler et je l'ai utilisée pour des projets d'écoles supérieures dans les méthodes de regroupement aggloméré.

Candide
la source
6

Jetez un œil à l' alborborithme de Rabin-Karp . Il utilise un hachage roulant un peu comme rsync pour minimiser les octets transmis lors d'une synchronisation. En ajustant la taille de la fenêtre que vous utilisez pour le hachage, vous pouvez la rendre plus ou moins sensible. Le RK est utilisé, entre autres, pour la détection du plagiat, qui recherche essentiellement des sortes de dupes.

Peter Rowell
la source
4
Le problème décrit par l'OP ressemble exactement à la détection du plagiat , et je suggère que ce soit le premier endroit où chercher de l'aide. (Assurez-vous simplement d'identifier vos sources!)
Caleb
4

Un premier pas à cela pourrait être de détecter des phrases (ou tout autre bloc de données raisonnable. Prenez ces blocs et supprimez toutes les données de mete, les espaces blancs aléatoires html, les retours, etc. Prenez un MD5 de résultat et stockez-le dans une table. Vous pourriez match contre ces blocs pour essayer de trouver des correspondances.

Si cela ne fonctionne pas, vous pouvez essayer des n-grammes. Ici, vous avez besoin d'une entrée de chaque mot sur la page, mais il devrait être en mesure de vous donner de très bonnes correspondances.

http://en.wikipedia.org/wiki/N-gram

gam3
la source
Les mesures basées sur les n-grammes sont bien meilleures que les hachages md5, en particulier pour les données semi-structurées telles que html.
Candide
1

Pour un calcul mathématique exact, je stockerais un hachage et le comparerais.

Je pense que les systèmes utilisés pour les examens mesurent des groupes de mots, puis la fréquence des groupes de chaque taille. Par exemple, une chaîne de 30 mots copiés marquerait 5 points de risque et 5 occurrences de 10 chaînes de mots marqueraient 5 points. Vous auriez alors un seuil de 30 points pour 500 mots.

Vraiment, vous avez besoin d'un algorithme sémantique pour que les mots comme «aussi» et «et» soient analysés de la même manière.

Lama inversé
la source