← 回首頁
相似度雜湊（MinHash + LSH / SimHash）
網路上有幾十億篇文章，想抓出哪些互相抄來抄去、幾乎重複，若每兩篇都逐字比對，慢到永遠比不完。相似度雜湊的點子是先幫每篇文件蓋一個很短的「指紋」，之後只比指紋像不像，就能猜出原文像不像——就像認人不必比對全身，對一下指紋就八九不離十。MinHash 取一堆隨機最小值湊成簽名，SimHash 讓每個字對指紋每一位投票。下面你會看到這兩種指紋怎麼一步步算出來，並誠實對照它們跟真實相似度差了多少。
兩者都把文件壓縮成固定長度的摘要，以摘要間的距離近似原始相似度，用精確度換取規模：MinHash 對每個固定雜湊函式取
文件 token 雜湊值的最小值組成簽名，簽名逐列相同比例估計 Jaccard 相似度，再以 LSH(Locality-Sensitive Hashing,區域敏感雜湊)
的 banding 手法把簽名切段分桶,只有落入
同桶的文件對才需要進一步比對，省去全體 O(n²) 暴力配對；SimHash 則對每個位元用固定線性雜湊對文件內每個 token 投票，
累計值二值化成指紋，兩指紋的漢明距離越小代表原始相似度越高。本頁兩個 section 皆同時揭露「估計/近似值」與
「精確 Jaccard 真值」（獨立暴力交併比計算），誠實對照兩者差距。
為什麼 AI 時代重要
RAG 語料庫上線前需要去除重複或近似重複的文件，避免同一內容反覆污染檢索結果；向量檢索前也常先用這類摘要做粗篩，
縮小候選範圍再做精細比對。當文件規模達到十億級，逐對暴力比較 Jaccard 相似度是 O(n²) 且要存下完整 token
集合，實務上不可行——只能像本頁這樣，用固定長度的簽名/指紋換取「近似但可規模化」的答案。
它是雜湊表與 Bloom Filter 的延伸
MinHash 與 SimHash 一樣仰賴固定參數的雜湊函式族，但用途從「決定桶位置」（雜湊表）、「決定位元是否置位」
（Bloom Filter）進一步延伸為「取最小值組成簽名」與「逐位元投票組成指紋」，同屬「以雜湊換取空間或速度、
犧牲部分精確度」的機率性資料結構家族 →
雜湊 Hash Table / Bloom Filter
1. MinHash + LSH（簽名矩陣 + banding 候選對）
computeSignature：對每個雜湊函式 h_i(x) = (a_i·x + b_i) mod 17（i=0..7，a_i 皆為奇數，固定參數表），
取文件內所有 token 雜湊值的最小值組成簽名 sig[i]；簽名矩陣填滿後，估計 Jaccard（簽名逐列相同比例）與
精確 Jaccard（交併比，獨立真值）同幀對照。LSH banding：簽名切成 4 個 band、每 band 取 2 列串接成桶鍵，
同鍵即為同桶；候選相似對＝同 band 同桶內任兩文件。
固定資料（token 宇宙 0..15）：d0=[0,1,2,3,4,5]、d1=[0,1,2,3,4,6]（與 d0 exactJ=5/7）、
d2=[2,3,7,8,9,10]、d3=[11,12,13,14,15,7]。k=8 個固定雜湊函式（a_i 奇、mod 17）；LSH：4 band × 2 row。
已計算雜湊次數：0
階段：signature
列＝雜湊函式 h0..h7（NUM_HASHES=8）、欄＝文件 d0..d3；格值＝該雜湊函式對該文件的最小雜湊值（簽名），
空白代表尚未填入。藍色外框（active）＝當前計算格；LSH 階段粉紅（pivot）標示當前 band 的起始格，
該 band 涵蓋的整個列範圍（兩列 × 全部文件欄）以 active 呈現。k=8 誤差界較寬：估計 Jaccard 與精確
Jaccard 可能有明顯差距，這是簽名長度較短時的正常教學可視現象，並非估計失準。
2. SimHash（加權位元投票指紋 + 漢明距離）
computeVotes：對文件內每個 token，逐位元 p 用固定線性雜湊 bitValue(t,p) = ((C[p]·t + D[p]) mod 17) mod 2
累計投票（C[p]=2p+3、D[p]=p+1，token 權重全為 1，教學簡化）：bitValue=1 記 +1，否則記 -1；文件全部 token
處理完後二值化（累計值 > 0 記 1，否則含 0 平局記 0）成 16-bit 指紋。全部文件指紋完成後，計算兩兩漢明距離
並列精確 Jaccard 對照：漢明距離越小，代表原始相似度越高（方向一致，非數值等價）。
固定資料同 MinHash 一節（共用 DOCS/DOC_NAMES）。16-bit 指紋，per-bit 固定雜湊 mod 17，token 權重全為 1。
已知限制：p=7 時 C[7]=17≡0（mod 17），bit_7 對任何 token 恆為固定值，是「死位元」，不攜帶區分資訊
（與 Java javadoc 揭露一致，固定參數表為跨語言一致性保留原樣）。
累計投票次數：0
列＝文件 d0..d3、欄＝位元 bit0..bit15（BITS=16）；格值於投票過程中為累計值（可正可負），該文件全部
token 處理完後覆寫為二值化的 0/1 指紋。藍色外框（active）＝當前 token 影響的全部 16 個位元格
（每個 token 影響整列）。bit7 為已知死位元：無論哪個文件，該欄二值化後恆為同一固定值，
不代表任何區分力，教學上照實呈現、不隱藏。
RAG 混合檢索的關鍵字路 BM25 同樣建立在倒排索引與固定規則統計量之上，與本頁的雜湊摘要手法同屬「先用
固定規則壓縮/分桶、再排序或比對」家族，BM25 排名再與向量檢索排名以 RRF 融合
→
混合檢索 BM25/RRF