Finding duplicate documents is easy until the collection becomes large. With one million documents, an all-pairs comparison needs roughly 500 billion checks. The important idea is therefore not a faster comparison. It is avoiding almost all comparisons.
Step 1: preserve local order with shingles
A k-shingle is a sequence of k tokens. The string abcab has the 2-shingle set {ab, bc, ca}. Unlike a bag of words, shingles retain some local order. Represent each document as a set and compare two sets with Jaccard similarity:
J(A, B) = |A intersection B| / |A union B|Small k creates accidental matches; very large k misses lightly edited copies. The right value depends on document length and the kind of edits that matter.
Step 2: replace a large set with a signature
For a random permutation of the universe, MinHash records the first member belonging to a set. The key property is:
P[minhash(A) = minhash(B)] = J(A, B)Repeat this with many hash functions. The fraction of matching signature rows estimates Jaccard similarity. More rows reduce variance but consume more memory and computation.
Step 3: use LSH as a candidate generator
Even short signatures still produce quadratic work if every pair is compared. LSH divides a signature into bands and hashes each band. Two documents become candidates when at least one band matches. More rows per band make matching stricter; more bands improve recall but admit more false positives.
In plain terms: MinHash makes each document small. LSH decides which small representations are worth checking. An exact comparison can verify the final candidates.
This is a reusable system pattern: cheap approximation first, expensive truth check second. Measure candidate reduction, recall on known duplicate pairs, and false-positive cost together; optimizing only one can make the pipeline useless.
Review card
- Shingling converts sequence similarity into set similarity.
- Jaccard compares shared elements with the union.
- MinHash preserves Jaccard similarity in expectation.
- LSH reduces search, not final verification.
- Banding trades recall against candidate volume.
找重複文件不難，難的是 collection 變大後仍做得完。一百萬份文件若兩兩比較，大約要檢查五千億組。真正重要的不是把 comparison 再加速一點，而是不要比較其中絕大多數。
第一步：用 shingle 保留局部順序
k-shingle 是連續 k 個 token。字串 abcab 的 2-shingle set 是 {ab, bc, ca}。它比 bag of words 多保留一些局部順序。把文件表示成 set 後，以 Jaccard similarity 比較：
J(A, B) = |A 交集 B| / |A 聯集 B|k 太小會有大量偶然重合；太大則會漏掉稍微編輯過的 copy。選擇要看文件長度，以及產品認定哪些修改仍算相似。
第二步：用 signature 取代巨大 set
對 universe 做 random permutation，MinHash 記錄某個 set 最先出現的 member。核心性質是：
P[minhash(A) = minhash(B)] = J(A, B)用多個 hash function 重複，signature 相同 row 的比例就能估計 Jaccard similarity。Row 越多 variance 越小，但 memory 與 computation 也越高。
第三步：LSH 只產生值得驗證的 candidates
即使 signature 很短，全部兩兩比較仍是 quadratic。LSH 把 signature 分成 bands，各自 hash；至少一個 band 相同才成為 candidate。每 band 的 rows 越多，條件越嚴；bands 越多，recall 越高，但 false positives 也會增加。
白話來說： MinHash 把每份文件縮小；LSH 決定哪些縮小版值得真正比較；最後仍可用 exact comparison 驗證。
這是一個很通用的 system pattern：先用便宜 approximation 篩選，再用昂貴 truth check 收尾。實作時要一起量 candidate reduction、已知 duplicate recall 與 false-positive cost，不能只最佳化單一數字。
複習卡
- Shingling 把 sequence similarity 轉成 set similarity。
- Jaccard 比較交集相對於聯集的比例。
- MinHash 在 expectation 上保留 Jaccard similarity。
- LSH 負責縮小搜尋，不負責最終判定。
- Banding 是 recall 與 candidate volume 的交換。