如何使用Simhash算法比较文档相似度？大规模文本近重复检测

Nice work getting those Simhash fingerprints generated already—comparing their similarity is exactly what Simhash was built for, so let’s break this down clearly.

The core idea behind Simhash is that the Hamming distance between two fingerprints directly correlates to how similar the original texts are. Here's how to implement this:

1. Calculate the Hamming Distance Between Two Simhashes #

The Hamming distance is simply the number of positions where the binary digits of the two hashes differ. You can compute this in two common ways:

Option 1: String-Based Comparison (Simple for Raw Binary Strings) #

If your hashes are stored as binary strings (like the 00100110... value you shared), iterate through each character to count differences:

def calculate_hamming_distance(simhash_a: str, simhash_b: str) -> int:
    if len(simhash_a) != len(simhash_b):
        raise ValueError("Simhash values must be the same length")
    # Count number of positions where bits differ
    return sum(bit_a != bit_b for bit_a, bit_b in zip(simhash_a, simhash_b))

Example Usage:

# Replace with your actual hash values
hash_1 = "00100110101110100011111000100010010101011001000001110000111001011100110101001101111010100010001011001011000110000100110101100110"
hash_2 = "<your second document's simhash>"
hash_3 = "<your third document's simhash>"

distance_1_2 = calculate_hamming_distance(hash_1, hash_2)
distance_1_3 = calculate_hamming_distance(hash_1, hash_3)

print(f"Distance between doc 1 and 2: {distance_1_2}")
print(f"Distance between doc 1 and 3: {distance_1_3}")

Option 2: Integer-Based XOR (Faster for Large Datasets) #

For better performance (especially with 5000+ documents), convert the binary string hashes to integers first. Use XOR to find differing bits, then count the number of 1s in the result (each 1 represents a differing bit):

def calculate_hamming_distance_int(simhash_int_a: int, simhash_int_b: int) -> int:
    # XOR gives a number where bits are 1 only where the two inputs differ
    xor_result = simhash_int_a ^ simhash_int_b
    # Count the number of 1 bits in the XOR result
    return bin(xor_result).count('1')

Convert String to Integer:

hash_str = "00100110..."
hash_int = int(hash_str, 2)

2. Interpret the Hamming Distance #

Simhash is tuned so that smaller distances mean higher similarity. A common rule of thumb for thresholds (adjust based on your use case):

• Distance ≤ 3: Near-duplicate documents (almost identical content)
• Distance 4-5: Highly similar documents (significant overlap in content)
• Distance > 5: Low similarity (unlikely to be near duplicates)

For your test data, documents 1, 2, and 3 all reference "simhash" and "test/ testing", so their Hamming distances should fall in the ≤3 range, marking them as near duplicates.

3. Optimize for 5000+ Documents #

A naive pairwise comparison would be O(n²), which gets slow with 5000 docs. Use a bucketing strategy to reduce unnecessary comparisons:

• Split your Simhash into equal segments (e.g., split a 128-bit hash into 4 segments of 32 bits each)
• Group hashes into buckets where at least one segment matches
• Only compare hashes within the same bucket (since hashes with a small Hamming distance must share at least one segment if you split correctly)

This cuts down the number of comparisons drastically, making the process feasible for large corpora.

内容的提问来源于stack exchange，提问作者Dany M