N-gram Hash
Le hachage de N-grammes transforme l'ensemble des N-grammes d'un texte (séquences de N caractères ou mots) en une empreinte de longueur fixe pour des comparaisons approximatives rapides.
Objectif
Juger rapidement la similarité de textes quand la correspondance exacte est inutile, comme en déduplication, correction orthographique et recherche floue.
Mécanisme
Le texte glisse en un ensemble de N-grammes ; chaque N-gramme est haché et les résultats agrégés (union, bitmap ou comptages) en une empreinte de longueur fixe. La similarité de Jaccard de deux textes peut s'estimer à partir de leurs empreintes.
Cas d’usage
- Déduplication approximative de textes
- Récupération de candidats pour la correction orthographique
- Correspondance floue dans les moteurs de recherche