Skip to content

SimHash Fingerprinting

SimHash (Charikar's similarity hash) produces a fixed-size fingerprint where the Hamming distance between two fingerprints approximates the cosine distance between their feature vectors. Unlike MinHash which measures set similarity, SimHash captures weighted token frequency similarity, making it well suited for near-duplicate text detection.

How It Works

  1. The document is tokenized into features (words or character n-grams).
  2. Each feature is weighted by its frequency (TF).
  3. Each feature is hashed to a fixed-width bit string.
  4. For each bit position, weights are summed: positive if the bit is 1, negative if 0.
  5. The final fingerprint sets bit i to 1 if the accumulated sum at position i is positive.

Quick Start

from primestamp.fingerprint.simhash import SimHashGenerator

gen = SimHashGenerator(hash_bits=64)

fp1 = gen.generate(b"The quick brown fox jumps over the lazy dog")
fp2 = gen.generate(b"The quick brown fox leaps over the lazy dog")

print(f"Hamming distance: {fp1.hamming_distance(fp2)}")
print(f"Similarity: {fp1.similarity(fp2):.4f}")
print(f"Near duplicate: {gen.is_near_duplicate(fp1, fp2, max_distance=3)}")

Near-Duplicate Index

Use SimHashIndex for efficient near-duplicate search over large collections.

from primestamp.fingerprint.simhash import SimHashGenerator, SimHashIndex

gen = SimHashGenerator(hash_bits=64)
index = SimHashIndex(hash_bits=64, num_segments=4)

# Index documents
for doc_id, content in documents.items():
    fp = gen.generate(content)
    index.insert(doc_id, fp)

# Find near-duplicates
query_fp = gen.generate(b"Search document text here...")
duplicates = index.find_near_duplicates(query_fp, max_distance=3)
for doc_id, distance in duplicates:
    print(f"{doc_id}: distance={distance}")

Configuration

Parameter Type Default Description
hash_bits int 64 Fingerprint width. Supported: 64, 128, 256.
token_mode TokenMode WORD WORD for word tokens, NGRAM for character n-grams.
ngram_size int 3 Character n-gram size (only used when token_mode=NGRAM).

Hash Bit Width

Width Use Case Storage
64 bits General near-duplicate detection, web-scale deduplication 8 bytes
128 bits Higher precision for large corpora 16 bytes
256 bits Maximum discrimination, archival fingerprinting 32 bytes

Token Modes

from primestamp.fingerprint.simhash import SimHashGenerator, TokenMode

# Word tokenization (default) - splits on word boundaries
gen_word = SimHashGenerator(token_mode=TokenMode.WORD)

# N-gram tokenization - character-level sliding window
gen_ngram = SimHashGenerator(token_mode=TokenMode.NGRAM, ngram_size=4)

Choosing a Distance Threshold

For 64-bit SimHash, a Hamming distance of 3 or fewer typically indicates near-duplicate content. Adjust based on your tolerance for false positives/negatives.

Serialization

# Serialize to dict
data = fp1.to_dict()
print(data["value_hex"])  # hex-encoded fingerprint

# Restore from dict
from primestamp.fingerprint.simhash import SimHashFingerprint
fp_restored = SimHashFingerprint.from_dict(data)

Factory Function

from primestamp.fingerprint.simhash import create_simhash_generator

gen = create_simhash_generator(hash_bits=128, mode="ngram", ngram_size=4)

SimHash vs MinHash

  • SimHash measures cosine similarity via Hamming distance -- best for weighted text comparison.
  • MinHash measures Jaccard set similarity -- best for unweighted shingle overlap. See MinHash for the alternative approach.