SimHash
SimHash ist der von Charikar vorgeschlagene lokalitätssensitive Hash (LSH): Er bildet Text auf eine Bitfolge fester Länge ab, wobei ähnliche Texte kleine Hamming-Abstände haben.
Zweck
Fast-Duplikate mit O(1)-Vergleichen über große Textbestände finden und so Deduplizierung und Clustering unterstützen.
Mechanismus
Jedes Textmerkmal (z. B. ein N-Gramm) wird unabhängig gehasht; Merkmalsgewichte werden je Hash-Bit entsprechend 0/1 addiert oder subtrahiert, und die finalen Vorzeichenbits bilden den SimHash-Fingerabdruck. Höhere Ähnlichkeit bedeutet kleineren Hamming-Abstand.
Anwendungsfälle
- Massive Webseiten-Deduplizierung
- Clustering von Fast-Duplikaten
- Plagiatserkennung