SimHash
En informatique, SimHash est une technique permettant d'estimer rapidement la similarité entre deux ensembles de données. L'algorithme est utilisé par le rob…
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
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
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
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
- ↑ (en) Bennett Cyphers, « Google’s FLoC Is a Terrible Idea », sur Electronic Frontier Foundation, (consulté le )
- ↑ (en-US) « Wait, WTF happened with Google FLoC? We explain », sur The Drum (consulté le )
- « simhash » [archive du ], sur matpalm.com (consulté le )
- (en) Gurmeet Singh Manku, Arvind Jain et Anish Das Sarma, « Detecting near-duplicates for web crawling », CrossRef, ACM, , p. 141–150 (ISBN 978-1-59593-654-7, DOI 10.1145/1242572.1242592, lire en ligne, consulté le )
- ↑ (en) Sadhan Sood et Dmitri Loguinov, « Probabilistic near-duplicate detection using simhash », CrossRef, ACM, , p. 1117–1126 (ISBN 978-1-4503-0717-8, DOI 10.1145/2063576.2063737, lire en ligne, consulté le )
- ↑ (en) « What is SimHash? », sur DEV Community, (consulté le )
- (en) Monika Henzinger, « Finding near-duplicate web pages: a large-scale evaluation of algorithms », CrossRef, ACM, , p. 284–291 (ISBN 978-1-59593-369-0, DOI 10.1145/1148170.1148222, lire en ligne, consulté le )
- ↑ (en) Abhinandan S. Das, Mayur Datar, Ashutosh Garg et Shyam Rajaram, « Google news personalization: scalable online collaborative filtering », CrossRef, ACM, , p. 271–280 (ISBN 978-1-59593-654-7, DOI 10.1145/1242572.1242610, lire en ligne, consulté le )
Voir aussi
Articles connexes
Liens externes
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.