Détecteur de duplication SimHash

Le SimHash, décrit par Moses Charikar en 2002, résume un texte en une empreinte de 64 bits telle que deux textes proches donnent des empreintes proches. Contrairement à un hachage classique, où une virgule change tout, la ressemblance des empreintes reflète celle des textes.

1. Le texte est découpé en éléments : ici des shingles, suites de trois mots consécutifs (minuscules, sans accents ni ponctuation).
2. Chaque élément est haché sur 64 bits (les 64 derniers bits de son MD5).
3. Pour chacun des 64 bits, on compte les éléments qui le mettent à 1 et ceux qui le mettent à 0 ; la majorité l’emporte.
4. On compare deux empreintes par leur distance de Hamming : le nombre de bits qui diffèrent, de 0 (textes équivalents) à 64.

Google a décrit en 2007 l’usage de cette technique pour repérer les quasi-doublons pendant le crawl, avec des empreintes de 64 bits et un seuil de 3 bits (Manku, Jain et Das Sarma). Le calcul reproduit celui du paquet Python simhash utilisé dans mon article sur le sujet ; la distance obtenue avec le découpage de l’article (mots isolés) figure dans les détails techniques.

Pourquoi deux verdicts ? Le SimHash résume chaque page entière : si une page reprend l’autre et y ajoute la moitié de texte en plus, ou n’en garde que le début, les empreintes s’éloignent alors que le passage commun est identique. La part de contenu repris détecte ce cas, que la distance seule laisserait passer.

Les seuils ont été calibrés sur les articles de ce site : 325 paires d’articles différents donnent toutes une distance d’au moins 20 (médiane 32), alors qu’un article dont on remplace 2 % des mots reste vers 7. La part de contenu commun (similarité de Jaccard sur les shingles) complète la distance : c’est la proportion de suites de trois mots partagées par les deux pages. « Part de A dans B » indique quelle fraction du texte de A se retrouve dans B, utile quand une page reprend une autre en l’allongeant.

Un doublon n’est pas une pénalité : un moteur regroupe les pages trop proches et n’en montre qu’une, pas forcément celle que vous préférez. Entre deux pages d’un même site, la réponse est en général une balise canonique, une redirection ou un vrai travail de différenciation.

• Il ne cherche pas qui vous copie sur le web : il compare deux pages que vous connaissez déjà.
• Il ne lit que le HTML renvoyé par le serveur ; un contenu injecté en JavaScript n’est pas vu. Dans ce cas, collez le texte.
• L’extraction du contenu principal est approximative (balises main et article, retrait des menus, en-têtes, pieds de page et barres latérales). Vérifiez le texte retenu, et cochez « Inclure menus et pied de page » pour comparer les pages entières.
• Sous une cinquantaine de mots, le SimHash devient instable : l’outil le signale.
• Il ne reproduit pas le calcul d’un moteur en particulier, dont les éléments, pondérations et seuils ne sont pas publics.

• Moses S. Charikar, Similarity estimation techniques from rounding algorithms, STOC 2002.
• Gurmeet Singh Manku, Arvind Jain, Anish Das Sarma, Detecting near-duplicates for web crawling, WWW 2007 (Google).
• Andrei Z. Broder, On the resemblance and containment of documents, 1997 (shingles, similarité de Jaccard).
• Paquet Python simhash (1e0ng), dont l’outil reproduit le calcul.
• Google Search Central, Consolider les URL en double.