從 30 分鐘無盡頭到 5 秒：SPV Pipeline 大規模文件相似度偵測

整理 Obsidian 筆記庫時，需要把 60 個新匯入的筆記跟現有 4,836 個檔案做相似度比對——找出內容相近（≥ 90%）但可能檔名不同的筆記。

Claude 暴力做法：60 × 4,836 = 290,160 次 SequenceMatcher，每次都是 O(n²) 字元運算。實際跑起來風扇狂轉，等超過 30 分鐘還沒結果。

最後用三層過濾架構，把實際執行的 SequenceMatcher 降到 103 次，5 秒跑完。

為什麼不用排序演算法？

找完全相同（exact duplicate）的文件，按檔案大小排序就夠了：

• 大小相同的相鄰比對，O(n log n) 搞定
• 連 hash 都不需要

但這次要找的是內容相近，不是完全相同。相近文件的特徵：

• 不同檔名，但內容幾乎一樣
• 加了 YAML frontmatter 或標題略有改動
• 排版差異、空白行不同

這類情況兩個檔案大小可能差了幾十 bytes，排序演算法和 hash 都抓不到，卻有 95% 的內容相同。這才是需要特別處理的模糊地帶。

SPV Pipeline：三層過濾架構

命名為 SPV Pipeline，三個字母各對應一層：

資料流向：

flowchart TD
    A["所有候選對\n290,160"] -->|Layer 1 大小過濾| B["17,205\n跳過 272,955"]
    B -->|Layer 2 指紋過濾| C["103\n跳過 17,102"]
    C -->|Layer 3 SequenceMatcher| D["39 對相似\n效能節省 99.96%"]

Layer 1：大小過濾

內容相似的文件，清洗後的字元數應在彼此 ±20% 以內。一篇 100 字、另一篇 500 字，相似度不可能 90%。

設 $|q|$、$|d|$ 為清洗後字元數，定義大小差異比：

$$\delta_S(q, d) = \frac{\bigl||q| - |d|\bigr|}{\max(|q|, |d|)}$$

過濾條件（跳過）：

$$\delta_S(q, d) > \alpha_S \quad (\alpha_S = 0.20)$$

這一層直接跳過了 272,955 對，跳過率 94%。

Layer 2：固定位置指紋

對清洗後文字 $t$，以固定步長 $k=10$ 取樣，得指紋序列：

$$F(t) = \bigl(t[0],\ t[k],\ t[2k],\ \ldots\bigr)$$

fingerprint = cleaned_text[::10]  # 每 10 個字取 1 個，位置固定

兩份指紋的逐位相似度：

$$\sigma_P(q, d) = \frac{\displaystyle\sum_{i} \mathbf{1}\bigl[F_q[i] = F_d[i]\bigr]}{\max(|F_q|,\ |F_d|)}$$

若 $\sigma_P < 0.80$ 則跳過。

為什麼固定位置而非隨機取樣？ 隨機每次結果不同，無法預先建 index。固定步長 $k$ 確保同一文件永遠產生相同指紋，可快取、可 hash。

這層又跳過 17,042 對，通過 Layer 1 的部分跳過率 99%。

Layer 3：SequenceMatcher 精確比對

找兩段文字所有最長公共子序列（LCS）區塊，累加匹配字元數 $M(q,d)$：

$$\text{sim}(q, d) = \frac{2 \cdot M(q, d)}{|q| + |d|}$$

判斷條件：

$$\text{sim}(q, d) \geq \theta \quad (\theta = 0.90)$$

90% 意味兩篇文章有 9 成的字元序列互相對應。

前處理先去掉 frontmatter 和多餘空白，避免排版差異影響判斷：

def clean(text):
    lines = text.splitlines()
    if lines and lines[0].strip() == "---":
        try:
            end = lines.index("---", 1)
            lines = lines[end+1:]
        except ValueError:
            pass
    return " ".join(" ".join(lines).split()).lower()

實際執行：103 次（從 290,160 降至 103）。

整體公式

對候選對 $(q, d)$，定義判斷函數：

$$\text{SPV}(q, d) = \begin{cases} \text{similar} & \text{if } \delta_S \leq \alpha_S \ \wedge \ \sigma_P \geq \alpha_P \ \wedge \ \text{sim} \geq \theta \ \text{pass} & \text{otherwise} \end{cases}$$

每層為前一層的前置條件，候選集單調收縮：

$$|C_0| \geq |C_1| \geq |C_2| \geq |C_3|$$

$$290{,}160 \geq 17{,}205 \geq 103 \geq 39$$

實驗結果

39 個新檔被標記為相似（不同檔名、相同內容），全數移除。

相似度閾值是可調整的

$\theta$ 不是固定值，依需求調整：

閾值越低找到的對越多，但誤判率也越高。

實作重點

# 一次性把所有文件讀入記憶體
vault = [(path, len(cleaned), cleaned, fingerprint(cleaned)) for ...]

for new_file in new_files:
    for v_path, v_sz, v_clean, v_fp in vault:
        # Layer 1
        if size_diff > 0.20: continue
        # Layer 2
        if fp_similarity(fp_new, v_fp) < 0.80: continue
        # Layer 3
        s = SequenceMatcher(None, c_new, v_clean).ratio()
        if s >= 0.90: report_similar()

記憶體策略：全部讀入、一次掃描。現代機器記憶體充裕，避免反覆 I/O 是正確取捨。

Layer 2 的邊界：段落位移問題

固定位置指紋有一個前提假設：兩篇文件的內容從同一個位置開始對齊。

一旦出現段落位移——例如其中一篇多了引言、匯入時加了標題、或兩個版本的開頭段落不同——整個指紋就整體錯位。zip 配對到的字元完全不相關，fp_similarity 偏低，Layer 2 直接跳過，即使後面 90% 內容完全一樣也偵測不到。

clean() 已經去掉 YAML frontmatter，這塊處理正確。但正文開頭的差異無法靠 clean() 解決。

三種修法

方案一：Sliding window（最快改）

試幾個不同的起點偏移（0、50、100、200 字元），取最高的 fp_similarity。偏移幾段的情況通常 200 字以內能涵蓋：

def fp_similarity_shifted(a, b, offsets=(0, 50, 100, 200)):
    max_len = max(len(a), len(b))
    if max_len == 0:
        return 0.0
    best = 0.0
    for off in offsets:
        a2, b2 = a[off:], b[off:]
        matches = sum(x == y for x, y in zip(a2, b2))
        best = max(best, matches / max_len)
    return best

方案二：段落集合交集（推薦）

把文件切成段落，每個段落取 hash，做 Jaccard 相似度。不管段落順序和位置，對位移完全免疫：

def para_similarity(a, b, min_len=20):
    pa = {hash(p.strip()) for p in a.split("\n\n") if len(p.strip()) >= min_len}
    pb = {hash(p.strip()) for p in b.split("\n\n") if len(p.strip()) >= min_len}
    if not pa or not pb:
        return 0.0
    return len(pa & pb) / len(pa | pb)  # Jaccard

用這個取代原本的 fp_similarity，幾行改動，位移問題直接消失，也不需要額外套件。

方案三：MinHash / LSH（完整方案）

學術標準做法（Broder 2000），用 shingle（連續 k 個詞的 n-gram）建 MinHash 簽章，近似 Jaccard 相似度。對位移、順序重排、插入刪除全部免疫。datasketch 套件有現成實作，適合 vault 規模到十萬筆以上的場景。

對 Obsidian 筆記整理來說，方案二是最划算的升級：成本低、效果直接，能補上固定位置指紋的主要漏洞。

核心原則

最快的計算，是根本不做那次計算。

越早、越便宜的過濾放越前面；SequenceMatcher 是最貴的，放最後、用最少。排序演算法處理完全相同；SPV Pipeline 處理內容相近——兩者解決不同層級的問題。

相關文獻

SPV Pipeline 與學術界的 Filter-and-Verify 正規化一致：

• Broder (2000). Identifying and Filtering Near-Duplicate Documents. 提出 shingling 指紋演算法，近似文件偵測的奠基之作。PDF
• Manku et al. (2007). Detecting Near-Duplicates for Web Crawling. Google Research，Web 規模的實際系統。PDF
• Manning, Raghavan & Schütze. Near-Duplicates and Shingling. Stanford IR Book 教科書。連結
• Christophides et al. (2019). A Survey of Blocking and Filtering Techniques for Entity Resolution. ArXiv。PDF
• Khan et al. (2025). LSHBloom: Internet-Scale Text Deduplication. 現代大規模管線，速度提升 12×。ArXiv