MinHash for Near-Duplicate Detection

Background

MinHash estimates Jaccard similarity between two sets in constant time using a fixed number of hash functions. Production data-quality pipelines use it to find near-duplicate documents in massive corpora before training — preventing the model from memorising repeated content.

Problem statement

Implement two functions:

• minhash_signature(tokens, num_hashes=64, k=3, seed=0) — convert tokens to k-shingles; for each of num_hashes distinct hash families, return the minimum hash value across shingles. Output length = num_hashes.
• estimate_jaccard(sig_a, sig_b) — fraction of positions at which the two signatures agree.

Input

• tokens — list[str], the document tokens.
• num_hashes — int, signature length (default 64).
• k — int, shingle size (default 3).
• seed — int, hash-family seed.
• sig_a, sig_b — length-matching signature lists.

Output

• minhash_signature returns a length-num_hashes list of integers.
• estimate_jaccard returns a Python float in $[0, 1]$.

Examples

Example 1 — identical docs → Jaccard = 1

Input:  tokens = list("hello world"); compare to itself
Output: 1.0

Example 2 — disjoint docs → low Jaccard

Input:  ["a","b","c","d"] vs ["x","y","z","w"]
Output: < 0.2

Example 3 — partial overlap → intermediate

Input:  ["the","quick","brown","fox","jumps"] vs ["the","quick","brown","cat","sleeps"]
Output: in [0.0, 1.0]

Constraints

• len(tokens) < k falls back to a single-shingle signature.
• estimate_jaccard raises ValueError if signatures are different lengths.
• Returns Python float.

Notes

• Why k-shingles, not single tokens. A document is the set of its $k$-shingles, not the bag of tokens. $k = 3$ captures local word order; smaller $k$ blurs the boundary between "same words, different order" and "actually similar".
• LSH banding. To find near-duplicates in $O(\sqrt n)$, partition the signature into bands and hash each band — documents sharing any band are candidates for comparison. Out of scope here.