N-gram Hash
N-gram hashing turns a text's set of N-grams (runs of N characters or words) into a fixed-length fingerprint for fast approximate text comparison.
Purpose
It quickly judges text similarity when exact matching is unnecessary, as in deduplication, spelling correction, and fuzzy search.
Mechanism
The text is slid into a set of N-grams; each N-gram is hashed and the results aggregated (union, bitmap, or counts) into a fixed-length fingerprint. The Jaccard similarity of two texts can be estimated from their fingerprints.
Use cases
- Approximate text deduplication
- Candidate retrieval for spelling correction
- Fuzzy matching in search engines