MinHash & LSH：素描的藝術

演算法背後的故事：畫像師與人群

想像妳正在 1000 萬人的茫茫人海中尋找一個特定的人。妳沒有時間去檢查每個人的眼睛顏色、耳朵形狀或指紋。

相反，妳僱了一位 速寫畫像師。對於每一個人，畫像師都會迅速畫出三個特徵：身高、帽子的顏色、眼鏡的形狀。這三個數字就是這個人的 「簽名」 (Signature)。

如果兩個人的簽名完全相同，她們極有可能是同一個人（或者至少非常相似）。

1997 年，Andrei Broder 開發了 MinHash 演算法，幫助當時的搜尋引擎 Altavista 識別重複的網頁。隨後，局部敏感雜湊 (LSH) 被發明出來，用於將這些「簽名」進行分組，使得相似的物品能落入同一個「桶」中。這是大規模相似性搜尋的開端。

為什麼需要它？

在大數據時代，精確的全文比對是不可能的。

• 搜尋引擎： 檢測「近乎重複」的內容。如果兩篇新聞報導有 95% 的內容相同，Google 只想展示其中一篇。
• 版權監測： 識別一段音樂或一張圖片是否是原版的輕微修改版。
• 推薦系統： 「買了 X 的使用者也買了 Y」。在數百萬使用者中尋找品味相似的「同類」。

演算法是如何「思考」的

這個演算法是一個聰明的戰略家，它利用 機率 來避免繁重的體力勞動。

1. 簽名 (MinHash)： 它拿出一篇巨大的文檔，將其切成一個個短語（Shingles）。它不再儲存整個短語集合，而是應用幾十個隨機雜湊函式。對於每個函式，它只保留計算出的 最小值。 這組最小值的列表就是 MinHash 簽名——它是文檔的一張「極簡素描」。

2. 投影 (LSH)： 即使有了簽名，兩兩比對的複雜度依然是 $O(N^2)$。LSH 透過「局部敏感」解決了這個問題。 通常，雜湊函式元建置的目標是避免碰撞。但 LSH 的建置目標是讓相似的物品產生碰撞。它將簽名切成幾段（Bands），每一段都雜湊到一個桶裡。

3. 分桶邏輯： 如果兩個文檔相似，她們的簽名中至少有一段極大概率會落入同一個桶中。我們只需要對比那些在同一個桶裡的文檔，從而跳過了 99.9% 的無關人群。

工程決策：快，但「模糊」

MinHash 和 LSH 屬於 機率演算法。

• 權衡： 她們速度極快且佔用記憶體極低，但她們會有 虛警 (False Positives)（不相關的項落入同桶）或 漏報 (False Negatives)（錯過了相似的項）。
• 精度控制： 工程師透過調整雜湊函式的數量和分段的大小，來在速度與準確率之間尋找平衡點。

實作參考 (Python 素描版)

import random

def get_minhash_signature(content_set, num_hashes=100):
    # content_set: 分詞後的字串集合 (shingles)
    signature = []
    for i in range(num_hashes):
        # 實際工程中會使用不同的雜湊函式
        # 這裡用帶種子的 hash 來模擬多個隨機雜湊函式
        min_hash = min(hash(f"{item}_{i}") for item in content_set)
        signature.append(min_hash)
    return signature

def lsh_bucket(signature, bands=20):
    # 將簽名分為 20 個分段 (bands)
    rows = len(signature) // bands
    buckets = []
    for i in range(0, len(signature), rows):
        band = tuple(signature[i:i+rows])
        # 只要兩個簽名的某一段雜湊相同，她們就會落入同一個桶
        buckets.append(hash(band))
    return buckets

小結

MinHash 和 LSH 教會我們：完美是大規模計算的天敵。透過使用「素描」和「分桶」，我們可以輕鬆駕馭數十億級的數據海洋。它提醒我們，要理解這個世界的宏大，不需要看清每一個細節，只需要知道哪些細節最關鍵。