SimHash

Deep dive

How it works

In: document text, shingle width w, a weight per feature, threshold k · Out: 64-bit fingerprint; for lookup, all stored fingerprints within k bits · State: none for the fingerprint; the index keeps k+1 tables of block value to ids · Cost: O(64) per feature; k+1 table probes per lookup

1. Clean the text: strip boilerplate first (HTML text extraction), lowercase, split on non-alphanumerics.
2. Features: every window of w consecutive tokens (w = 3 is a common start; w = 1 is a bag of words and ignores order).
3. Weight each feature (term frequency by repeating it; or tf x idf from a corpus table).
4. Hash each feature to 64 well-mixed bits.
5. Keep 64 signed counters: for each feature and each bit b, add the weight if bit b is 1, subtract it if 0.
6. Fingerprint bit b = 1 if counter b > 0.
7. Compare two fingerprints with popcount(a ^ b); "near-duplicate" means distance <= k.
8. To search a collection: split the 64 bits into k+1 blocks. If two fingerprints differ in at most k bits, at least one block is identical (pigeonhole). Index each block exactly, probe the k+1 blocks of the query, verify candidates by Hamming distance.

Why it works: each bit is the sign of a random projection (Charikar's hyperplane rounding), so P(bit differs) = angle/pi and E[distance] = 64 x angle/pi. Identical features cancel, a few changed features flip only bits whose sum was near zero.

Code

use std::collections::HashMap;

fn fnv1a(b: &[u8]) -> u64 {
    let mut h = 0xcbf29ce484222325u64;
    for &x in b { h = (h ^ x as u64).wrapping_mul(0x100000001b3); }
    // splitmix64 finalizer: FNV's high bits mix poorly, and every bit is a vote here
    h = (h ^ (h >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    h = (h ^ (h >> 27)).wrapping_mul(0x94d049bb133111eb);
    h ^ (h >> 31)
}

/// Lowercase alphanumeric tokens.
pub fn tokens(text: &str) -> Vec<String> {
    text.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty()).map(|w| w.to_lowercase()).collect()
}

/// 64-bit simhash of the w-word shingles; `weight` maps a shingle hash to its weight (1 = plain tf).
pub fn simhash(text: &str, w: usize, weight: impl Fn(u64) -> i32) -> u64 {
    let toks = tokens(text);
    let mut v = [0i64; 64];
    let n = toks.len();
    let windows = if n >= w { n - w + 1 } else { usize::from(n > 0) }; // short text: one shingle
    for i in 0..windows {
        let h = fnv1a(toks[i..(i + w).min(n)].join(" ").as_bytes());
        let wt = weight(h) as i64;
        for (b, vb) in v.iter_mut().enumerate() {
            *vb += if h >> b & 1 == 1 { wt } else { -wt };
        }
    }
    v.iter().enumerate().fold(0u64, |fp, (b, &x)| fp | ((x > 0) as u64) << b)
}

pub fn hamming(a: u64, b: u64) -> u32 { (a ^ b).count_ones() }

/// Finds all stored fingerprints within `k` bits. Pigeonhole: with k+1 blocks, two fingerprints
/// within k bits agree exactly on at least one block, so k+1 exact-match tables suffice.
pub struct Index {
    k: u32,
    tables: Vec<HashMap<u64, Vec<u32>>>, // block value -> ids
    fps: Vec<u64>,
}

impl Index {
    pub fn new(k: u32) -> Self { Index { k, tables: vec![HashMap::new(); k as usize + 1], fps: vec![] } }
    fn block(&self, fp: u64, i: usize) -> u64 {
        let (lo, hi) = (i * 64 / self.tables.len(), (i + 1) * 64 / self.tables.len());
        (fp >> lo) & ((1u64 << (hi - lo)) - 1)
    }
    pub fn insert(&mut self, fp: u64) -> u32 {
        let id = self.fps.len() as u32;
        for i in 0..self.tables.len() { let b = self.block(fp, i); self.tables[i].entry(b).or_default().push(id); }
        self.fps.push(fp);
        id
    }
    /// Returns (id, distance) for every stored fingerprint within k bits of `fp`.
    pub fn query(&self, fp: u64) -> Vec<(u32, u32)> {
        let mut out: Vec<(u32, u32)> = vec![];
        for i in 0..self.tables.len() {
            for &id in self.tables[i].get(&self.block(fp, i)).into_iter().flatten() {
                let d = hamming(fp, self.fps[id as usize]);
                if d <= self.k && !out.iter().any(|o| o.0 == id) { out.push((id, d)); }
            }
        }
        out
    }
}

fn main() {
    let mut rng = 0x9e3779b97f4a7c15u64; // xorshift64: synthetic text, 5000-word vocabulary
    let mut doc = |n: usize| -> String {
        (0..n).map(|_| { rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17; format!("w{} ", rng % 5000) }).collect()
    };
    let (a, c) = (doc(400), doc(400));
    let b = a.replacen("w", "x", 1); // light edit: first token changed
    let sh = |t: &str| simhash(t, 3, |_| 1);
    println!("d(a,a)={} d(a,b)={} d(a,c)={}", hamming(sh(&a), sh(&a)), hamming(sh(&a), sh(&b)), hamming(sh(&a), sh(&c)));
    assert_eq!(sh("The quick brown fox"), sh("the  QUICK, brown fox!"));
    assert_eq!(hamming(sh(&a), sh(&a)), 0);
    assert!(hamming(sh(&a), sh(&b)) <= 8 && hamming(sh(&a), sh(&c)) >= 20);
    let mut idx = Index::new(7);
    let (ia, ic) = (idx.insert(sh(&a)), idx.insert(sh(&c)));
    let hits = idx.query(sh(&b));
    assert!(hits.iter().any(|h| h.0 == ia) && hits.iter().all(|h| h.0 != ic));
}

Complexity and constants

• Fingerprint: O(L x 64) for L features; the 64 counters stay in L1 and the inner loop vectorizes.
• Lookup: k+1 probes plus candidates. Candidates per table are about n/2^(block bits): with k = 3 (16-bit blocks) and a million stored fingerprints that is about 15 per table; with 8 billion it is far too many, so use longer exact prefixes (next bullet).
• Memory: 8 B per fingerprint per table. Pigeonhole alone needs k+1 tables; Manku et al. trade more tables for longer exact prefixes, e.g. 5 blocks and 10 tables for k = 3 at 8B fingerprints: 256 to 512 candidates per probe (their Example 3.1).
• Brute force over all fingerprints is O(n) per query; enumerating every fingerprint within 3 bits needs C(64,3) = 41,664 probes (Manku et al.).

Efficiency

• Cost: fingerprinting is hash-bound: measured on an Apple M4 Pro, one thread, release build, 3-word shingles of 300-word synthetic documents (naively allocating a String per shingle): about 30,000 documents/s (about 53 MB/s). Lookup, k = 3, 1M random fingerprints in four HashMap tables: about 1.2M lookups/s (measured, same machine). Lookup is memory-latency bound, the fingerprint is compute bound.
• Levers:
  • hash token ids once and combine them rolling, instead of re-hashing joined strings — removes the per-shingle allocation (gain not measured) — when documents are long.
  • sorted arrays or one sorted table per block permutation instead of hash maps — 8 B/fingerprint/table, binary or interpolation search (Manku et al.) — when n is in the hundreds of millions.
  • delta-compress sorted tables — about half the size (Manku et al.) — when memory-bound.
  • batch lookups against sorted files — 1M query fingerprints in about 100 s with MapReduce (Manku et al.) — for offline sweeps.
• Naive → standard → state of the art:
  • all-pairs popcount · O(n) per query
  • k+1 block tables with verification · O(k) probes + candidates
  • permuted, compressed, sorted tables across machines (Manku et al.) · milliseconds per query on 8B fingerprints

Implementation notes

• Hash quality matters: every bit is a vote, so a weak hash makes the bits correlated. FNV-1a alone mixes poorly into its high bits; the code adds a splitmix64 finalizer. Use a keyed or fixed seed so fingerprints stay comparable across runs and versions; store the pipeline version with each fingerprint.
• w = 3 suits articles; use 1 to 2 for short texts (one edited token changes w shingles).
• Weights: give stopwords idf near 0; use integer or fixed-point weights so the counters stay exact.
• Threshold k: label document pairs and plot precision/recall per distance, as Manku et al. did, instead of copying k = 3. Measured here (synthetic 400-word texts, Apple M4 Pro): 1 edit moved 2.5 bits on average, 4 edits 5.1, 20 edits 11.1, so k = 3 tolerates about one edit and a copy with a changed byline, date or trailer line can land above it.
• Normalise before hashing, and index near-exact duplicates first by a plain content hash or GUID; simhash is the second tier.

Pitfalls

• Boilerplate (navigation, comment sections, footers, license text) dominates short articles: two unrelated pages from one site land near each other. Extract the article body first.
• Short texts: 20 words with one edit moved 10.5 bits on average (measured here), so distances are noisy; do not compare below a minimum length.
• Distance is not a metric on meaning: negation, a changed number or a changed name barely moves it. It finds copies, not equivalent claims.
• Fingerprints cluster (similar documents get similar prints), so block values are not uniform and some buckets are huge; cap bucket size or verify with a second signal.
• Changing tokenizer, w, hash or weights invalidates every stored fingerprint.

Variants and alternatives

In production

• Google's web crawler, per Manku et al. (2007): 8 billion pages, online lookups in milliseconds and a batch mode of 1M queries in about 100 s.
• The libraries below (corpus dedupe, near-duplicate indexes).

Implementations

Sources

• Moses S. Charikar, Similarity estimation techniques from rounding algorithms, STOC 2002, pp. 380-388. doi
• Gurmeet Singh Manku, Arvind Jain, Anish Das Sarma, Detecting near-duplicates for web crawling, WWW 2007, pp. 141-150. doi · pdf