En informatique, SimHash est une technique permettant d'estimer rapidement la similarité entre deux ensembles de données. L'algorithme est utilisé par le robot d'indexation de Google pour identifier les pages quasi-dupliquées. Il a été créé par Moses Charikar[1].
En 2021, Google a annoncé son intention de l'utiliser également dans son système FLoC (Federated Learning of Cohorts), avant d'abandonner ce projet en janvier 2022 au profit de la Topics API, notamment sous la pression des autres navigateurs et en raison de craintes persistantes autour du fingerprinting individuel des utilisateurs[2].
Implémentation#edit
Une fonction de hachage transforme des données de taille quelconque en une sortie de taille fixe. Les mêmes données produisent toujours la même empreinte, mais deux entrées légèrement différentes produisent des empreintes radicalement différentes. La comparaison est donc purement binaire (identique ou non), ce qui la rend efficace pour traiter de grandes quantités de données, mais incapable d'exprimer un degré de similarité.
À l'inverse, SimHash génère des empreintes similaires pour des données similaires, mesurées par leur distance de Hamming, c'est-à-dire le nombre de bits qui diffèrent entre deux empreintes. Cela signifie que deux empreintes SimHash n'indiquent pas seulement si deux entrées sont différentes, mais renseignent aussi sur leur degré de différence.
L'algorithme fonctionne en trois étapes : les données sont d'abord décomposées en features (par exemple les mots d'un texte), chacune est hachée individuellement, puis ces hachages sont agrégés bit par bit. Pour chaque position, on additionne +1 pour chaque feature dont le bit vaut 1, et −1 pour chaque bit à 0. Le signe du résultat détermine le bit final de l'empreinte[3].
| Features | Hash | |||
|---|---|---|---|---|
| bit 0 | bit 1 | bit 2 | bit 3 | |
| "Le" | 0 | 1 | 0 | 0 |
| "chat" | 1 | 1 | 0 | 1 |
| "noir" | 1 | 1 | 0 | 0 |
| Somme | -1+1+1 | 1+1+1 | -1-1-1 | -1+1-1 |
| Valeur | 1≥0 | 3≥0 | -3<0 | -1<0 |
| SimHash | 1 | 1 | 0 | 0 |
En pratique, les features sont extraites via des techniques classiques de traitement de l'information : tokenisation, normalisation de la casse, suppression des mots vides, racinisation et détection de syntagmes. Chaque feature se voit attribuer un poids, qui module sa contribution positive ou négative à chaque position de bit. Pour un dépôt de 8 milliards de pages web, des empreintes de 64 bits avec un seuil de distance de Hamming k = 3 se sont avérées appropriées[4].
Cas d'usage#edit
Une faible distance de Hamming entre deux empreintes SimHash reflète un coefficient de Jaccard élevé entre leurs ensembles de features. Cela rend l'algorithme utile bien au-delà de la simple détection de doublons : il permet de trier efficacement de grandes collections en comparant les empreintes plutôt que les documents entiers, et d'identifier des contenus similaires en ne comparant que des éléments adjacents dans une liste triée, évitant ainsi la complexité quadratique d'une comparaison naïve par paires[3][5].
SimHash est également utilisé pour la détection de spam et le regroupement de contenu à grande échelle[6].
Évaluation et benchmarks#edit
Une évaluation à grande échelle conduite par Google en 2006 sur 1,6 milliard de pages web[7] a comparé SimHash à MinHash, concluant que l'algorithme de Charikar surpasse cette dernière pour la détection de quasi-doublons entre sites différents, que ce soit dans sa précision que pour son empreinte mémoire, occupant seulement 8 octets contre 24 pour MinHash (pour une empreinte de 64 bits)[7]. En 2007, Google a confirmé l'utilisation de SimHash pour la déduplication dans son crawler, en s'appuyant sur l'implémentation C++ originale de Moses Charikar[4]. Parallèlement, MinHash couplé au LSH était utilisé pour la personnalisation de Google News[8].
Références#edit
(en)« SimHash » (voir la liste des auteurs)
- ^ (en) Bennett Cyphers, « Google’s FLoC Is a Terrible Idea », sur Electronic Frontier Foundation, 3 mars 2021 (consulté le 16 mai 2026)
- ^ (en-US) « Wait, WTF happened with Google FLoC? We explain », sur The Drum (consulté le 16 mai 2026)
- ^ a b « simhash » [archive du 15 février 2026], sur matpalm.com (consulté le 16 mai 2026)
- ^ a b (en) Gurmeet Singh Manku, Arvind Jain et Anish Das Sarma, « Detecting near-duplicates for web crawling », CrossRef, ACM, 8 mai 2007, p. 141–150 (ISBN 978-1-59593-654-7, DOI 10.1145/1242572.1242592, lire en ligne, consulté le 16 mai 2026)
- ^ (en) Sadhan Sood et Dmitri Loguinov, « Probabilistic near-duplicate detection using simhash », CrossRef, ACM, 24 octobre 2011, p. 1117–1126 (ISBN 978-1-4503-0717-8, DOI 10.1145/2063576.2063737, lire en ligne, consulté le 16 mai 2026)
- ^ (en) « What is SimHash? », sur DEV Community, 3 novembre 2025 (consulté le 16 mai 2026)
- ^ a b (en) Monika Henzinger, « Finding near-duplicate web pages: a large-scale evaluation of algorithms », CrossRef, ACM, 6 août 2006, p. 284–291 (ISBN 978-1-59593-369-0, DOI 10.1145/1148170.1148222, lire en ligne, consulté le 16 mai 2026)
- ^ (en) Abhinandan S. Das, Mayur Datar, Ashutosh Garg et Shyam Rajaram, « Google news personalization: scalable online collaborative filtering », CrossRef, ACM, 8 mai 2007, p. 271–280 (ISBN 978-1-59593-654-7, DOI 10.1145/1242572.1242610, lire en ligne, consulté le 16 mai 2026)
Voir aussi#edit
This article is mirrored from “SimHash” on Français Wikipedia, revision 236285907, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.
Synced with Wikipedia revision 236285907 · just now