快速WordPiece分詞：一種適用於BERT及以後模型嘅線性時間算法

1. 引言

分詞係幾乎所有自然語言處理（NLP）任務嘅基礎預處理步驟，從情感分析到機器翻譯都係咁。現代模型如BERT、GPT-3同XLNet都依賴子詞分詞，特別係WordPiece呢類算法，將文本分解成有意義嘅單元，同時處理詞彙表外嘅詞語。本文解決咗一個關鍵瓶頸：WordPiece分詞算法本身嘅效率問題。

作者指出，WordPiece中使用嘅標準貪心最長匹配優先（MaxMatch）策略具有次優嘅時間複雜度——$O(n^2)$ 或 $O(nk)$，其中 $n$ 係輸入長度，$k$ 係最大詞元長度。佢哋提出LinMaxMatch，一種新穎嘅算法，為單詞分詞實現嚴格嘅 $O(n)$ 線性時間複雜度，以及一個整合嘅端到端（E2E）WordPiece算法用於一般文本。

2. 背景與相關工作

BERT中使用嘅WordPiece分詞涉及兩個步驟：（1）根據空格同標點符號將文本預先分詞成單詞；（2）對每個單詞應用MaxMatch算法，對照固定詞彙表進行匹配。MaxMatch亦用於中文分詞，迭代地選擇剩餘字符串中最長嘅、匹配詞彙表詞元嘅前綴。

先前嘅高效算法僅限於 $O(n^2)$ 或 $O(nk)$。$k$ 呢個因子係有問題嘅，因為詞彙表可能包含長詞元（例如“supercalifragilisticexpialidocious”）。本文嘅貢獻在於完全消除咗呢個依賴於詞彙表嘅因子。

3. LinMaxMatch算法

3.1 核心思想與啟發

LinMaxMatch嘅靈感來自Aho-Corasick字符串匹配算法。關鍵見解係將詞彙表視為一組模式，將輸入單詞視為文本。通過預先計算詞彙表字典樹上嘅輔助數據結構，算法可以避免匹配過程中嘅回溯，而回溯正係樸素MaxMatch中二次複雜度嘅根源。

3.2 數據結構：字典樹、失敗連結與失敗彈出

該算法使用三個核心數據結構，喺離線預處理階段根據詞彙表構建：

字典樹：一個標準嘅前綴樹，每個節點代表一個字符，從根節點出發嘅路徑代表詞彙表詞元。
失敗連結（類似Aho-Corasick）：對於代表字符串 $s$ 嘅節點，其失敗連結指向代表 $s$ 嘅最長真後綴、同時亦係某個詞彙表詞元前綴嘅節點。呢個設計允許算法高效地“故障轉移”。
失敗彈出：一個新穎嘅補充。當通過失敗連結從一個節點遍歷到另一個節點時，算法可能會“彈出”一個或多個喺該節點結束時已匹配嘅詞元。呢個列表係預先計算並儲存嘅。

3.3 算法流程詳解

對於長度為 $n$ 嘅輸入單詞，算法以單次遍歷方式從左到右處理字符。佢維持字典樹中嘅一個當前節點。對於每個新字符：

嘗試從當前節點跟隨匹配邊。
如果成功，移動到子節點。如果該節點係詞彙表詞元嘅終點，將其記錄為潛在匹配。
如果唔存在匹配邊，則跟隨當前節點嘅失敗連結。收集關聯嘅“失敗彈出”列表中儲存嘅任何詞元。然後，從新節點重新嘗試匹配同一個輸入字符。

呢個過程確保每個字符只被處理一次，保證 $O(n)$ 時間。

4. 端到端（E2E）WordPiece分詞

為咗對完整句子或文檔進行分詞，作者提議將預分詞步驟（基於空格/標點符號分割）與LinMaxMatch整合成一個統一嘅算法。呢個E2E WordPiece算法同樣相對於總文本長度以線性時間運行，避免咗分離階段嘅開銷。佢巧妙地喺同一個字典樹遍歷框架內，交織邊界檢測同子詞匹配。

5. 實驗結果與性能

本文展示咗令人信服嘅基準測試，將其實現與兩個廣泛使用嘅庫進行比較：HuggingFace Tokenizers同TensorFlow Text。

性能比較

平均加速比：

比HuggingFace Tokenizers快8.2倍。
比TensorFlow Text快5.1倍。

測試於一般文本分詞任務。

結果表明，理論上嘅 $O(n)$ 優勢轉化為顯著嘅實際性能提升，尤其對於較長文本或喺對延遲敏感嘅環境中，例如移動設備推理。

6. 關鍵見解與分析

核心見解

本文嘅根本突破唔只係一個更快嘅分詞器；佢係正式將分詞識別為一個可通過經典自動機理論解決嘅字符串匹配問題。通過將WordPiece嘅MaxMatch從樸素貪心搜索重新定義為Aho-Corasick嘅變體，作者彌合咗理論計算機科學與應用NLP工程之間數十年嘅差距。呢個令人聯想起CycleGAN論文如何將圖像翻譯重新定義為一個循環一致性對抗學習問題，創造咗一個新範式。

邏輯流程

論證邏輯嚴密：1）識別瓶頸（$O(n^2)$/$O(nk)$ 複雜度）。2）從一個經過驗證嘅最優算法（Aho-Corasick）中汲取靈感。3）使其適應MaxMatch嘅特定約束（需要輸出所有匹配詞元，而不僅僅係存在性）。4）引入新穎嘅數據結構（失敗彈出）來處理呢啲約束。5）將解決方案擴展到完整流程（E2E）。從問題到靈感，再到適應同泛化嘅流程，係應用研究嘅典範。

優點與不足

優點：$O(n)$ 嘅保證喺理論上優雅且經過實踐驗證。預處理成本係一次性開銷。正如作者指出並得到Google AI等機構設備端AI研究趨勢支持嘅，對移動/邊緣NLP嘅影響可能係巨大嘅。

潛在不足/遺漏：本文輕輕觸及但未深入分析增強字典樹（失敗連結與彈出）嘅記憶體開銷。對於龐大嘅詞彙表（例如多語言模型），呢個開銷可能唔容忽視。此外，基準測試雖然令人印象深刻，但係針對特定實現。與其他優化嘅MaxMatch變體（例如使用後綴數組）進行比較，將加強論點。

可行見解

對於NLP從業者：立即分析你嘅分詞延遲。如果佢佔你總推理時間嘅1-2%以上，特別係對於串流或移動應用，採用像LinMaxMatch咁樣嘅算法係一個高投資回報率嘅優化。對於研究人員：呢項工作打開咗一扇門。類似基於自動機嘅方法可以優化字節對編碼（BPE）或SentencePiece嗎？核心思想——用預先計算嘅狀態轉移替換回溯——廣泛適用於NLP中其他貪心分割算法。

7. 技術細節與數學表述

LinMaxMatch嘅核心可以形式化。設：

$V$ = 詞彙表，一個字符串集合。
$T$ = 由 $V$ 構建嘅字典樹。
對於字典樹節點 $u$，令 $L(u)$ 為從根到 $u$ 嘅字符形成嘅字符串。
失敗函數 $f(u)$： 節點 $v$，使得 $L(v)$ 係 $L(u)$ 嘅最長真後綴，且 $v$ 亦係 $T$ 中嘅節點。
失敗彈出 $P(u)$： 詞彙表詞元 $t \in V$ 嘅集合，其中 $t$ 係 $L(u)$ 嘅後綴，並且存在一個節點 $w$ 喺從根到 $f(u)$（或 $u$ 本身）嘅路徑上，使得 $L(w) = t$。呢個係為所有節點預先計算嘅。

輸入字符串 $S[1..n]$ 嘅分詞過程通過維持一個當前節點 $u$（初始為根）同一個索引 $i$ 來進行。當 $i \leq n$ 時：

如果存在 $u$ 嘅一個子節點 $v$，其邊標籤為 $S[i]$，則設 $u = v$，$i = i+1$。如果 $u$ 標記咗一個詞彙表詞元嘅結尾，記低佢。
否則，輸出 $P(u)$ 中嘅所有詞元。設 $u = f(u)$。唔好增加 $i$。 如果 $u$ 係根節點且冇子節點匹配 $S[i]$，則 $i = i+1$（處理未知字符）。

呢個循環嘅 $O(n)$ 複雜度係清晰嘅，因為 $i$ 要麼增加，要麼 $u$ 跟隨失敗連結，而失敗連結可以攤銷為每步常數。

8. 分析框架：案例研究

場景： 為智能手機上嘅實時語音助手優化分詞。當前流程使用來自流行庫嘅標準WordPiece分詞器。

框架應用：

基線測量： 性能分析顯示分詞每查詢消耗約15毫秒，佔總流程延遲（125毫秒）嘅12%。目標係 <100毫秒。
瓶頸分析： 查詢通常較長（口語句子）。$O(nk)$ 因子顯著，因為詞彙表包含技術複合詞。
解決方案設計： 用LinMaxMatch替換分詞器。構建帶有失敗連結/彈出嘅增強字典樹嘅一次性成本喺模型部署期間係可接受嘅。
預期結果： 基於本文嘅5-8倍加速，分詞時間應降至約2-3毫秒，將總延遲減少至約112毫秒，係邁向目標嘅穩健一步。常數時間保證亦提高咗延遲可預測性。

呢個案例研究說明咗算法嘅理論特性如何直接應對現代AI系統中嘅實際限制。

9. 應用前景與未來方向

高效、線性時間分詞嘅影響超越咗BERT：

設備端與邊緣AI： 隨著像GPT類架構嘅模型被蒸餾用於手機，預處理中節省嘅每一毫秒都會累積。呢項工作係下一代響應迅速、具備離線能力嘅NLP應用嘅基礎。
串流分詞： 對於實時翻譯或實時字幕，$O(n)$ 複雜度確保可預測嘅性能。未來工作可以探索針對無限串流嘅增量分詞。
多語言與大型詞彙表： 擴展到包含100多種語言、超過100萬個詞元嘅詞彙表。需要研究來優化預先計算結構嘅記憶體佔用，或許可以使用壓縮字典樹或近似方法。
與模型架構整合： 分詞可以部分學習或與Transformer嘅第一層合併嗎？基於上下文嘅“動態分詞”仍然係一個開放挑戰，但像呢種高效基礎算法係進行此類探索嘅先決條件。

10. 參考文獻

Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2019). BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. NAACL-HLT.
Aho, A. V., & Corasick, M. J. (1975). Efficient string matching: an aid to bibliographic search. Communications of the ACM.
Kudo, T. (2018). Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates. ACL.
Wolf, T., et al. (2020). HuggingFace's Transformers: State-of-the-art Natural Language Processing. arXiv preprint arXiv:1910.03771.
Google. (2020). TensorFlow Text. https://www.tensorflow.org/text
Brown, T. B., et al. (2020). Language Models are Few-Shot Learners. NeurIPS.
Zhu, J.-Y., Park, T., Isola, P., & Efros, A. A. (2017). Unpaired Image-to-Image Translation using Cycle-Consistent Adversarial Networks. ICCV. （作為範式轉移重新定義嘅例子引用）。

目錄