← 回首頁

文本演算法（Myers Diff + BPE Tokenization）

你在 GitHub 上看程式碼改動時，系統會用紅綠底色標出「這次到底改了哪幾行」——電腦怎麼認出哪裡是新增、哪裡是 刪掉？這就是 Myers Diff 在做的事：它像核對兩份行程表，只圈出不一樣的地方，用最少的增刪把舊版變成 新版。BPE 則管另一件事：AI 讀你的句子前，得先把文字切成一塊塊小單位，它的做法是把最常一起出現的 字母黏成「零件」（像把 e、s 黏成 es），這樣常見詞用幾塊就拼得出、罕見詞也拆得開。下面你會看到這兩件事 各自一步步發生。

兩者都是把「文本」變成演算法可操作的結構化資料的基礎工具，但服務的問題不同：Myers Diff 在兩份文本間 找出最短編輯腳本（Shortest Edit Script）——在「編輯圖」（edit graph）上逐輪推進差異量 d，沿每條對角線 貪婪 snake 前進，找出從 A 轉換為 B 所需的最少插入/刪除步驟，是 git diff、多數版本控制與 IDE 比對工具 背後的核心演算法；BPE（Byte Pair Encoding）則是把文本切成「子詞」（subword）單元——逐輪統計相鄰 token pair 的加權頻次、合併頻次最高者、詞彙表隨之成長，在「詞級別」與「字元級別」間取得平衡，是幾乎 所有現代 LLM tokenizer（GPT 系列、RoBERTa 等）的基礎。

為什麼 AI 時代重要

Coding agent 產生程式碼變更時，diff/merge 是核心子程序：呈現「改了什麼」給人審閱、把多個分支的變更 自動合併，背後計算最短編輯腳本的標準演算法正是 Myers Diff；而任何 LLM 在能夠處理文字之前，第一步永遠 是把原始字串切成 token —— BPE 正是這一步最主流的做法，決定了模型看到的最小語意單元是什麼、詞彙表多大、 罕見詞與新詞如何被拆解成已知子詞的組合。

它是 LCS 與 Huffman 貪婪思路的延伸

Myers Diff 的最短編輯距離 d 與最長公共子序列（LCS）長度可互相換算（d = |A|+|B| − 2×LCS），兩者本質是 同一問題的不同視角：LCS 求最長保留子序列、Myers 求最短編輯路徑，血緣直通樸素 LCS DP 表 → 動態規劃基礎；BPE 逐輪貪婪取「目前頻次最高」的 合併對、不回頭修正，與 Huffman 編碼逐輪合併頻次最低的兩個節點方向相反，但同屬「逐輪貪婪取局部最優」的 構造式演算法骨架，詳見下方與貪心頁的交叉連結。

1. Myers Diff（編輯圖 furthest-reaching V 陣列 + snake + LCS 互證）

逐輪推進差異量 d（d=0,1,2,...）：第 d 輪窮舉所有與 d 同奇偶的對角線 k（k = x−y，範圍 −d..d，step 2）， 每條對角線先比較上一輪鄰居 V[k−1]+1（刪除 A 一字元）與 V[k+1]（插入 B 一字元）何者較大，取較大者為本輪 furthest-reaching 起點 x（k=−d 或 k=d 邊界時僅一種來源），再沿對角線貪婪 snake 前進（連續相同字元可 「白吃」，不計入編輯距離）。一旦某條對角線走到終點（x=|A|、y=|B|），該輪 d 即為最短編輯腳本長度； 本輪其餘對角線仍算完（不提前中止），隨後由終點沿 V 陣列逐輪回溯，重建出由前往後排列的編輯腳本。

固定資料：Myers 1986 論文經典例 A='ABCABBA'、B='CBABAC'（與 Java 實測值逐字相同）； 預期最短編輯距離 d=5、LCS=4。
已計算格數（steps）：0 階段：fill
列 = 差異量 d（0..5，由上而下遞增）；欄 = 對角線 k（映射為欄 index = k + 5，故欄 0..10 依序對應 k = −5..5）。空格代表該格「本輪尚未計算」（候選比較幀，格暫不填值）或「該輪 k 值本來就無效」 （|k| > d，或 k 與 d 不同奇偶——d 每輪只窮舉與自己同奇偶的 k，其餘欄位對該輪而言不存在），兩者 在畫面上皆顯示空白，需配合下方敘述判斷；格值一旦填入即為該輪該對角線 furthest-reaching 的 x 座標 （非機率、非距離，是「目前這條對角線最遠能走到哪個 x」）。藍色外框（active）= 當前計算格； 粉紅（pivot）= 找到終點（x=|A| 且 y=|B|）的那一格。 為何優於樸素 LCS DP：樸素 DP 需要填滿整張 |A|×|B| 的表格，時間複雜度 O(N·M)；Myers 每輪只 窮舉 O(d) 條對角線、每條對角線的 snake 前進均攤 O((N+M)/D)，總計 O((N+M)·D) —— 當實際差異量 D 遠小於文本長度 N+M 時（多數程式碼變更正是如此：改幾行、其餘大量相同），效率明顯優於與差異量無關、 恆為 O(N·M) 的樸素 DP。

最短編輯距離（d）

（尚未確定）

LCS 互證（lcs）

（尚未確定）

編輯腳本（script）

已執行操作紀錄（opLog）

（空）

2. BPE（Byte Pair Encoding，配對頻次統計 + 子詞合併 + 詞彙成長）

每個詞先依字元切分、尾端附加詞尾標記 </w>（Sennrich et al. 2016 論文慣例，用來區分 「詞尾」與「詞中」出現的相同子詞），得到初始 token 化與初始詞彙表。逐輪：(1) 統計全語料所有詞、所有 相鄰 token pair 的加權頻次（加權 = 該詞的語料出現頻次，而非詞種數——出現 5 次的詞，其 pair 貢獻頻次即為 5）；(2) 取頻次最高的 pair 合併為單一新 token（若並列最高，取字典序較小者：先比 pair 的 left token 字串，相同再比 right token 字串）；(3) 將該 pair 在所有詞的 token 序列中由左到右不重疊 掃描式合併，詞彙表新增合併後的 token。固定跑 6 輪。

固定資料：Sennrich 論文風格小語料 {low:5, lower:2, newest:6, widest:3}；合併 6 輪 （與 Java 實測值逐字相同：合併序 (e,s)→(es,t)→(est,</w>)→(l,o)→(lo,w)→(e,w)）。
已合併次數（merges）：0 階段：init 輪次：—
列 = 語料中的 4 個詞（依字典序：low/lower/newest/widest）；欄 = 該詞目前的 token 序列位置 （最多 7 欄，詞較短則右側補空白，不代表任何 token）。每輪合併後此表立即更新，反映該詞當下的 切分方式；</w> 為詞尾標記，本身也是可被合併的 token（如 round 3 合併出 est</w>）。藍色外框（active）= 本輪操作影響的格；粉紅（pivot）本頁未使用 （BPE 每輪為全語料批次合併，不是單一格的比較/確認，故以 active 標示本輪新生成的 token 位置更貼切）。 tie-break 誠實揭露：round 1/2/4/6 頻次並列最高，取字典序較小者勝出，並非「隨機」或「先出現者」； round 3/5 無並列。與 LLM tokenizer 的關聯：GPT 系列、RoBERTa 等現代 LLM 的 tokenizer 皆以此 演算法（或其變體）離線訓練固定大小的子詞詞彙表，推論時用相同規則把輸入文字切成 token。

本輪頻次 top3（topPairs）

本輪合併（mergedPair）

（尚未合併）

合併史（mergeHistory）

詞彙表（vocab）

（空）

已執行操作紀錄（opLog）

（空）
BPE 逐輪貪婪取「目前頻次最高」的合併對、不回頭修正 —— 與 Huffman 編碼逐輪合併頻次最低的兩個節點方向 相反，但同屬「逐輪貪婪取局部最優」的構造式演算法骨架 → 貪心 活動選擇/分數背包