隨機分詞與tokenizer(BPE-＞BBPE-＞Wordpiece-＞Unigram-＞sentencepiece-＞bytepiece)

0 tokenizer綜述

根據不同的切分粒度可以把tokenizer分為: 基于詞的切分，基于字的切分和基于subword的切分。基于subword的切分是目前的主流切分方式。
subword的切分包括: BPE(/BBPE), WordPiece 和 Unigram三種分詞模型。其中WordPiece可以認為是一種特殊的BPE。
完整的分詞流程包括：文本歸一化，預切分，基于分詞模型的切分，后處理。
SentencePiece是一個分詞工具，內置BEP等多種分詞方法，基于Unicode編碼并且將空格視為特殊的token。這是當前大模型的主流分詞方案。

BPE：GPT, GPT-2, GPT-J, GPT-Neo, RoBERTa, BART, LLaMA, ChatGLM-6B, Baichuan
WordPiece：BERT, DistilBERT，MobileBERT
Unigram：AlBERT, T5, mBART, XLNet

中文分詞&新詞發現

1 基于subword的切分

基于詞和字的切分都會存在一定的問題，直接應用的效果比較差。
基于詞的切分，會造成:

詞表規模過大
一定會存在UNK，造成信息丟失
不能學習到詞綴之間的關系，例如：dog與dogs，happy與unhappy

基于字的切分，會造成:

每個token的信息密度低
序列過長，解碼效率很低

所以基于詞和基于字的切分方式是兩個極端，其優缺點也是互補的。而折中的subword就是一種相對平衡的方案。

基于subword的切分能很好平衡基于詞切分和基于字切分的優缺點，也是目前主流最主流的切分方式。
subword的基本切分原則是：

高頻詞依舊切分成完整的整詞
低頻詞被切分成有意義的子詞，例如 dogs => [dog, ##s]

基于subword的切分可以實現：

詞表規模適中，解碼效率較高
不存在UNK，信息不丟失
能學習到詞綴之間的關系

基于subword的切分包括：BPE，WordPiece 和 Unigram 三種分詞模型。

1.1 處理流程概述

歸一化:最基礎的文本清洗，包括刪除多余的換行和空格，轉小寫，移除音調等。
HuggingFace tokenizer的實現： https://huggingface.co/docs/tokenizers/api/normalizers
預分詞:把句子切分成更小的“詞”單元。可以基于空格或者標點進行切分。不同的tokenizer的實現細節不一樣。例如:
pre-tokenize:
[BERT]: [(‘Hello’, (0, 5)), (‘,’, (5, 6)), (‘how’, (7, 10)), (‘are’, (11, 14)), (‘you’, (16, 19)), (‘?’, (19, 20))]
[GPT2]: [(‘Hello’, (0, 5)), (‘,’, (5, 6)), (‘?how’, (6, 10)), (‘?are’, (10, 14)), (‘?’, (14, 15)), (‘?you’, (15, 19)), (‘?’, (19, 20))]
[t5]: [(‘▁Hello,’, (0, 6)), (‘▁how’, (7, 10)), (‘▁are’, (11, 14)), (‘▁you?’, (16, 20))]
可以看到BERT的tokenizer就是直接基于空格和標點進行切分。
GPT2也是基于空格和標簽，但是空格會保留成特殊字符“?”。
T5則只基于空格進行切分，標點不會切分。并且空格會保留成特殊字符"▁"，并且句子開頭也會添加特殊字符"▁"。
預分詞的實現： https://huggingface.co/docs/tokenizers/api/pre-tokenizers
基于分詞模型的切分:不同分詞模型具體的切分方式。分詞模型包括：BPE，WordPiece 和 Unigram 三種分詞模型。
分詞模型的實現： https://huggingface.co/docs/tokenizers/api/models
后處理:后處理階段會包括一些特殊的分詞邏輯，例如添加sepcial token：[CLS],[SEP]等。
后處理的實現： https://huggingface.co/docs/tok

1.2 BPE

Byte-Pair Encoding(BPE)是最廣泛采用的subword分詞器。

訓練方法：從字符級的小詞表出發，訓練產生合并規則以及一個詞表
編碼方法：將文本切分成字符，再應用訓練階段獲得的合并規則
經典模型：GPT, GPT-2, RoBERTa, BART, LLaMA, ChatGLM等

因為BPE是從字符級別的小詞表，逐步合并成大詞表，所以需要先獲得字符級別的小詞表。
基于word2splits統計vocabs中相鄰兩個pair的詞頻pair2count
經過統計，當前頻率最高的pair為: (‘?’, ‘t’)，頻率為7次。將(‘?’, ‘t’)合并成一個詞并添加到詞表中。同時在合并規則中添加(‘?’, ‘t’)這條合并規則。
根據更新后的vocab重新對word2count進行切分。具體實現上，可以直接在舊的word2split上應用新的合并規則(‘?’, ‘t’)
從而獲得新的word2split
重復上述循環直到整個詞表的大小達到預先設定的詞表大小。

在推理階段，給定一個句子，我們需要將其切分成一個token的序列。具體實現上需要先對句子進行預分詞并切分成字符級別的序列，然后根據合并規則進行合并。

BPE 的適用范圍
BPE 一般適用在歐美語言拉丁語系中，因為歐美語言大多是字符形式，涉及前綴、后綴的單詞比較多。而中文的漢字一般不用 BPE 進行編碼，因為中文是字無法進行拆分。對中文的處理通常只有分詞和分字兩種。理論上分詞效果更好，更好的區別語義。分字效率高、簡潔，因為常用的字不過 3000 字，詞表更加簡短。

1.3 BBPE

2019年提出的Byte-level BPE (BBPE)算法是上面BPE算法的進一步升級。具體參見：Neural Machine Translation with Byte-Level Subwords。核心思想是用byte來構建最基礎的詞表而不是字符。首先將文本按照UTF-8進行編碼，每個字符在UTF-8的表示中占據1-4個byte。在byte序列上再使用BPE算法，進行byte level的相鄰合并。編碼形式如下圖所示：

通過這種方式可以更好的處理跨語言和不常見字符的特殊問題(例如，顏文字)，相比傳統的BPE更節省詞表空間（同等詞表大小效果更好），每個token也能獲得更充分的訓練。

但是在解碼階段，一個byte序列可能解碼后不是一個合法的字符序列，這里需要采用動態規劃的算法進行解碼，使其能解碼出盡可能多的合法字符。具體算法如下：假定f(k)表示字符序列B(1,k)最大能解碼的合法字符數量，f(k)有最優的子結構：

1.4 WordPiece

WordPiece分詞與BPE非常類似，只是在訓練階段合并pair的策略不是pair的頻率而是互信息。
這里的動機是一個pair的頻率很高，但是其中pair的一部分的頻率更高，這時候不一定需要進行該pair的合并。而如果一個pair的頻率很高，并且這個pair的兩個部分都是只出現在這個pair中，就說明這個pair很值得合并。

訓練方法：從字符級的小詞表出發，訓練產生合并規則以及一個詞表
編碼方法：將文本切分成詞，對每個詞在詞表中進行最大前向匹配
經典模型：BERT及其系列DistilBERT，MobileBERT等

在訓練環節，給定語料，通過訓練算法，生成最終的詞表。 WordPiece算法也是從一個字符級別的詞表為基礎，逐步擴充成大詞表。合并規則為選擇相鄰pair互信息最大的進行合并。

def _compute_pair2score(word2splits, word2count):"""計算每個pair的分數score=(freq_of_pair)/(freq_of_first_element×freq_of_second_element):return:"""vocab2count = defaultdict(int)pair2count = defaultdict(int)for word, word_count in word2count.items():splits = word2splits[word]if len(splits) == 1:vocab2count[splits[0]] += word_countcontinuefor i in range(len(splits) - 1):pair = (splits[i], splits[i + 1])vocab2count[splits[i]] += word_countpair2count[pair] += word_countvocab2count[splits[-1]] += word_countscores = {pair: freq / (vocab2count[pair[0]] * vocab2count[pair[1]])for pair, freq in pair2count.items()}return scores

1.5 Unigram

Unigram分詞與BPE和WordPiece不同，是基于一個大詞表逐步裁剪成一個小詞表。
通過Unigram語言模型計算刪除不同subword造成的損失來衡量subword的重要性，保留重要性較高的子詞。

訓練方法：從包含字符和全部子詞的大詞表出發，逐步裁剪出一個小詞表，并且每個詞都有自己的分數。
編碼方法：將文本切分成詞，對每個詞基于Viterbi算法求解出最佳解碼路徑。
經典模型：AlBERT, T5, mBART, Big Bird, XLNet

在訓練環節，目標是給定語料，通過訓練算法，生成最終的詞表，并且每個詞有自己的概率值。 Unigram算法是從大詞表為基礎，逐步裁剪成小詞表。裁剪規則是根據Unigram語言模型的打分依次裁剪重要度相對較低的詞。
首先進行預切分處理。這里采用xlnet的預切分邏輯。具體會按照空格進行切分，標點不會切分。并且空格會保留成特殊字符"▁"，句子開頭也會添加特殊字符"▁"。
獲得的pre_tokenized_corpus如下，每個單元分別為[word, (start_index, end_index)]
統計詞表的全部子詞和詞頻，取前300個詞，構成最初的大詞表。為了避免OOV，char級別的詞均需要保留。
進一步統計每個子詞的概率，并轉換成Unigram里的loss貢獻
基于每個子詞的loss以及Viterbi算法就可以求解出，輸入的一個詞的最佳分詞路徑。即整體語言模型的loss最小。詞的長度為N，解碼的時間復雜度為O(N^2)。
嘗試移除model中的一個子詞，并計算移除后新的model在全部語料上的loss，從而獲得這個子詞的score，即刪除這個子詞使得loss新增的量。
為了提升迭代效率，批量刪除前10%的結果，即讓整體loss增量最小的前10%的詞。(刪除這些詞對整體loss的影響不大。)
獲得新的詞表后，重新計算每個詞的概率，獲得新的模型。并重復以上步驟，直到裁剪到詞表大小符合要求。

初始時，建立一個足夠大的詞表。一般，可用語料中的所有字符加上常見的子字符串初始化詞表，也可以通過BPE算法初始化。
針對當前詞表，用EM算法求解每個子詞在語料上的概率。
對于每個子詞，計算當該子詞被從詞表中移除時，總的loss降低了多少，記為該子詞的loss。
將子詞按照loss大小進行排序，丟棄一定比例loss最小的子詞(比如20%)，保留下來的子詞生成新的詞表。這里需要注意的是，單字符不能被丟棄，這是為了避免OOV情況。
重復步驟2到4，直到詞表大小減少到設定范圍。
可以看出，ULM會保留那些以較高頻率出現在很多句子的分詞結果中的子詞，因為這些子詞如果被丟棄，其損失會很大。

1.6 SentencePiece

SentencePiece是Google出的一個分詞工具:
內置BPE，Unigram，char和word的分詞方法無需預分詞，以unicode方式直接編碼整個句子，空格會被特殊編碼為▁
相比傳統實現進行優化，分詞速度速度更快

當前主流的大模型都是基于sentencepiece實現，例如ChatGLM的tokenizer。

byte回退
當SentencePiece在訓練BPE的時開啟–byte_fallback, 在效果上類似BBPE，遇到UNK會繼續按照byte進行進一步的切分。參見：https://github.com/google/sentencepiece/issues/621 具體實現上是將<0x00> … <0xFF>這256個token添加到詞表中。
分析ChatGLM的模型，可以發現ChatGLM就是開啟了–byte_fallback
同樣的方法，可以驗證LLaMA, ChatGLM-6B, Baichuan這些大模型都是基于sentencepiece實現的BPE的分詞算法，并且采用byte回退。

參考鏈接：https://zhuanlan.zhihu.com/p/651430181

1.7 bytepiece

一個理想的Tokenizer應該是怎樣的，這樣才能判斷最終是否達到了預期。照筆者看來，Tokenizer至少應該具備如下基本特性：
1、無損重構：分詞結果應該可以無損還原為輸入；
2、高壓縮率：詞表大小相同時，同一批數據的tokens數應該盡可能少；
3、語言無關：基于統計，訓練和分詞過程都不應引入語言特性；
4、數據驅動：可以直接基于原始語料進行無監督訓練；
5、訓練友好：能夠在合理的時間和配置上完成訓練過程。
最后，還有一些加分項，比如分詞速度快、代碼易讀、方便二次拓展等，這些滿足自然最好，但筆者認為可以不列入基本特性里邊。

對于筆者來說，SentencePiece最大的槽點就是“無損重構”和“訓練友好”。
首先，SentencePiece默認會進行NFKC normalization，這會導致“全角逗號轉半角逗號”等不可逆變化，所以默認情況下它連“無損重構”都不滿足，所以很長時間里它都不在筆者的候選名單中，直到后來發現，在訓練時添加參數–normalization_rule_name=identity就可以讓它不做任何轉換。所以SentencePiece算是支持無損重構，只不過要特別設置。
至于訓練方面，就更讓人抓狂了。SentencePiece支持BPE和Unigram兩種主流算法，Unigram訓練速度尚可，但壓縮率會稍低一些，BPE的壓縮率更高，但是訓練速度要比Unigram慢上一個數量級！而且不管是BPE還是Unigram，訓練過程都極費內存。總而言之，用較大的語料去訓練一個SentencePiece模型真不是一種好的體驗。

1.7.1 byte-based

我們知道，Python3的默認字符串類型是Unicode，如果以Unicode為基本單位，我們稱之為Char-based。Char-based很直觀方便，漢字表現為長度為1的單個字符，但不同語言的Char實在太多，即便只是覆蓋單字都需要消耗非常大的vocab_size，更不用說引入Word。所以BytePiece跟主流的Tokenizer一樣，以Byte為基本單位。

回到Byte之后，很多問題都“豁然開朗”了。因為不同的單Byte只有256個，所以只要詞表里包含了這256個單Byte，那么就可以杜絕OOV（Out of Vocabulary），這是它顯而易見的好處。
此外，我們知道漢字的平均信息熵要比英文字母的平均信息熵要大，如果我們選擇Char-based，那么雖然每個Char表面看起來長度都是1，但“內在”的顆粒度不一樣，這會導致統計結果有所偏置。相比之下，每個Byte的信息熵則更加均勻【比如，大部分漢字的UTF-8編碼對應3個Byte，而漢字的平均信息熵正好是英文字母（對應一個Byte）的2～3倍左右】，因此用Byte的統計結果會更加無偏，這將會使得模型更加“語言無關”。

在Byte-based方面，BytePiece比SentencePiece更徹底，SentencePiece是先以Char-based進行處理，然后遇到OOV再以Byte-based處理，BytePiece則是在一開始就將文本通過text.encode()轉為Bytes，然后才進行后續操作，相比之下更加純粹。

1.7.2 分詞算法

基于詞典進行分詞的算法無非就那幾種，比如最大匹配、最短路徑、最大概率路徑等，

跟jieba等中文分詞工具一樣，BytePiece選擇的是最大概率路徑分詞，也稱“一元文法模型”，即Unigram。

選擇Unigram有三方面的考慮：
第一，Unigram的最大概率換言之就是最大似然，而LLM的訓練目標也是最大似然，兩者更加一致；
第二，從壓縮的角度看，最大概率實際上就是最短編碼長度（也叫最小描述長度），是壓縮率最大化的體現，這也跟“壓縮就是智能”的信仰一致；
第三，Unigram求最優分詞方案可以通過Viterbi算法在線性復雜度內完成，這是理論最優的復雜度了。

當然，既然有“一元文法模型”，自然也有更復雜的“二元文法模型”、“三元文法模型”等，但它們的復雜度增加遠大于它能帶來的收益，所以我們通常不考慮這些高階模型。

1.7.3 訓練算法

Tokenizer的訓練本質上就是以往的“新詞發現”，而筆者之前也提了好幾種新詞發現算法。現在看來，跟Unigram分詞算法最契合、最有潛力的，應該是《基于語言模型的無監督分詞》，
BytePiece的訓練就是基于它實現的，這里稱之為Byte-based N-gram Language Model（BNLM）。

具體來說，對于Unigram分詞，如果一個長度為l的字節串c1,c2,…,cl，最優分詞結果為w1,w2,…,wm，那么概率乘積p(w1)p(w2)…p(wm)應該是所有切分中最大的。
設w1,w2,?,wm的長度分別為l1,l2,?,lm，那么根據條件分解公式
∏i=1mp(wi)=∏i=1m∏j=Li?1+1j=Li?1+lip(cj|cLi?1+1,?,cj?1) (1)
這里Li=l1+l2+?+li。只考慮n-gram模型，將j>Li?1+n的p(cj|cLi?1+1,?,cj?1)統一用p(cj|cj?n+1,?,cj?1)近似，
那么Unigram分詞就轉化為一個字（節）標注問題，而Tokenizer的訓練則轉化為n-gram語言模型的訓練（推薦n=6），可以直接無監督完成。

（注意：n=6只是說BytePiece的統計信息最多到6-gram，但并非最大只能生成長度為6的piece，因為大于6的n-gram條件概率我們會用6-gram的近似，所以它是可以做到任意階的，即理論上可以生成任意長度piece。）

1.7.4 代碼實現&效果

Github：https://github.com/bojone/bytepiece
代碼很簡單，單文件，里邊就Trainer和Tokenizer兩個類，分別對應分詞兩部分。分詞借助pyahocorasick來構建AC自動機來稍微提了一下速，能湊合用，但還是會比SentencePiece慢不少，畢竟速度方面純Python跟C++確實沒法比。

訓練則分為四個主要步驟：
1、n-gram計數；
2、n-gram剪枝；
3、預分詞；
4、預分詞結果剪枝。
其中1、3、4都是計算密集型，并且都是可并行的，所以編寫了相應的多進程實現。在開足夠多的進程（筆者開了64進程，每個進程的使用率基本上都是滿的）下，訓練速度能媲美SentencePiece的Unigram訓練速度。

這里特別要提一下結果剪枝方面。剪枝最基本的依據自然是頻數和vocab_size，但這還不夠，因為有時候會出現p(w1)p(w2)>p(w1°w2)（w1°w2指兩個詞拼接）且w1,w2,w1°w2三個詞都在詞表中，這種情況下w1°w2這個詞永遠不會切分出來，所以將它放在詞表中是純粹浪費空間的，因此剪枝過程也包含了這類結果的排除。

首先做個小規模的測試，從悟道之前開源的數據集里邊隨機采樣10萬條作為訓練集（導出來的文件大概330MB），然后另外采樣1千作為測試集，訓練一個vocab_size=50k的詞表，結果對比如下：

接下來進行一個更大規模的測試。從中英比例大致為3:5的混合語料庫中，抽取出10萬條樣本訓練vocab_size=100k的Tokenizer。這個語料庫的文本都比較長，所以這時候10萬條導出來的文件已經13GB了，測試集包含兩部分，一部分是同樣的語料庫中采樣出1000條（即同源），另一部分是剛才采樣出來的1000條悟道數據集（代表不同源）。結果如下：