SimHash
SimHash est le hachage sensible à la localité (LSH) proposé par Charikar : il applique le texte sur une chaîne de bits de longueur fixe où des textes similaires ont de petites distances de Hamming.
Objectif
Trouver des documents quasi dupliqués par comparaisons en O(1) sur de grandes collections de textes, pour la déduplication et le regroupement.
Mécanisme
Chaque caractéristique du texte (p. ex. un N-gramme) est hachée indépendamment ; les poids des caractéristiques sont additionnés ou soustraits par bit de hachage selon sa valeur 0/1, et les bits de signe finaux forment l'empreinte SimHash. Plus la similarité est grande, plus la distance de Hamming est petite.
Cas d’usage
- Déduplication massive de pages web
- Regroupement de documents quasi dupliqués
- Détection de plagiat