好久沒更新，這是一篇長(zhǎng)文。也是一篇比較硬的文章，比較燒腦。在硬長(zhǎng)文里，可能很難找到這么有趣的。在有趣的文章里，可能很難找到這么硬的。這就是大半夜在寫文章的價(jià)值，不是么？嗯，大概就是這樣吧。

在自然語(yǔ)言處理領(lǐng)域，分詞是最基本的任務(wù)。不管是傳統(tǒng)的基于詞典的分詞算法還是現(xiàn)代的基于統(tǒng)計(jì)語(yǔ)言模型的分詞算法，都需要詞典作為輸入。本文介紹 Trie 算法，用來(lái)存儲(chǔ)詞典，并提供高效的搜索功能。

詞典的格式

這里的詞典比你書架上的現(xiàn)代漢語(yǔ)詞典要簡(jiǎn)單很多，因?yàn)闆]有釋義，只有光溜溜的一個(gè)詞在那。這也好理解，釋義是給人看的，而計(jì)算機(jī)根本就看不懂釋義。計(jì)算機(jī)頂多只會(huì)“算”，但它算的真的很快很快，快到讓人感覺它真的有智能。比如下面就是一個(gè)分詞時(shí)用到的詞典：

阿
阿巴丹
阿爸
...
...
...
做賊心虛
做主
做作

當(dāng)然，基于現(xiàn)代的統(tǒng)計(jì)語(yǔ)言模型的分詞算法，還需要存儲(chǔ)詞的常用程度。所以需要對(duì)詞典里的詞做一些標(biāo)注，比如：

反   1205
作戰(zhàn)股 1
先人后己    1
傳媒者 1

由此可見，詞典的數(shù)據(jù)其實(shí)是很簡(jiǎn)單的，就是一個(gè)詞加上與這個(gè)詞對(duì)應(yīng)的一個(gè)整形數(shù)值。在實(shí)際應(yīng)用中，需要非常頻繁地查找詞典，比如在分詞算法里，我們找到兩個(gè)字后，需要判斷這兩個(gè)字是否在詞典里，如果在，就說明這是一個(gè)整體的詞，如果不在，那么就不能組成一個(gè)詞。所以詞典的格式應(yīng)該要滿足快速查找的要求。那么怎么樣保存詞典以便查找速度最快呢？直接把詞典按照線性放在數(shù)組里顯然是不行的。

Trie 數(shù)據(jù)結(jié)構(gòu)

Trie 的讀音和 Tree 相同，也有人讀作 Try ，是為了和 Tree 區(qū)分開。因?yàn)樵?Tree 也是數(shù)據(jù)結(jié)構(gòu)的一種，容易讓人誤解。

話說，怎么樣存儲(chǔ)詞典呢？科學(xué)家們發(fā)明了一種叫做叫 Trie 的數(shù)據(jù)結(jié)構(gòu)來(lái)保存詞典：

Trie

圖一：圖片來(lái)自 wikipedia

上圖展示了 "A", "t", "to", "tea", "ted", "ten", "i", "in", "inn"。在這樣的數(shù)據(jù)結(jié)構(gòu)里，要查找某個(gè)詞時(shí)，基本上和詞典的大小無(wú)關(guān)，而只與要查找的詞的大小有關(guān)。查找的速度基本上達(dá)到 O(1)。比如，我們要找 "tea" 這個(gè)詞，從開始狀態(tài)起步，我們的第一個(gè)字母是 "t" 則沿著根節(jié)點(diǎn)最左邊的子樹上前進(jìn)到達(dá)其對(duì)應(yīng)的子節(jié)點(diǎn)，接著是字母 "e" ，找到對(duì)應(yīng)的子節(jié)點(diǎn)，再接著字母 "a" 找到 "tea" 這個(gè)單詞。再如，我們要找 "too" 這個(gè)單詞，在到達(dá) "to" 這個(gè)節(jié)點(diǎn)時(shí)，還剩下一個(gè) "o" 沒有消化掉。所以 "too" 這個(gè)單詞就不在上圖表示的詞典里。

從另外一個(gè)角度看這個(gè)圖，實(shí)際上這也是個(gè)確定有限狀態(tài)機(jī)(DFA - Deterministic Finite Automaton)。實(shí)際上針對(duì) Trie 算法的實(shí)現(xiàn)，就是基于 DFA 的的原理進(jìn)行的，所以要理解 Trie 算法，本質(zhì)上需要先理解 DFA。

確定有限狀態(tài)機(jī)

有限狀態(tài)機(jī)的定義是非常嚴(yán)謹(jǐn)?shù)?，它包含一個(gè)五元組 (Q, Σ, δ, q0, F)，其中：

• Q 是一個(gè)有限的狀態(tài)集合
• Σ 是一個(gè)有限的輸入事件集合
• δ 是一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，當(dāng)某個(gè)狀態(tài)遇到某個(gè)事件時(shí)，會(huì)引起狀態(tài)轉(zhuǎn)換，跳到另外一個(gè)狀態(tài) (δ : Q × Σ → Q)
• q0 是一個(gè)起始狀態(tài) (q0 ∈ Q)
• F 是一組可接受的終止?fàn)顟B(tài) (F ? Q)

不得不說，數(shù)學(xué)家這個(gè)群體還是很令人佩服的。他們把很好理解的概念抽象抽象再抽象，抽象到我等智商平平的人看不懂的程度。當(dāng)然，數(shù)學(xué)家的本意并非讓我等看不懂，而是為了計(jì)算方便。另外一些人和數(shù)學(xué)家干的事正好相反，他們把很復(fù)雜的數(shù)學(xué)原理和算法，解釋得通俗易懂，讓大部分資質(zhì)平平，沒經(jīng)過專業(yè)訓(xùn)練的人也能感受到數(shù)學(xué)之美。比如吳軍老師的《數(shù)學(xué)之美》就是這類的典范。

跑題結(jié)束，我們說回 DFA。上文講過，我們可以把 Trie 數(shù)據(jù)結(jié)構(gòu)看成是一個(gè) DFA 。那么詞典和數(shù)學(xué)家定義的 DFA 有什么關(guān)系呢？

還是以圖一為例，我們看一下對(duì)應(yīng)關(guān)系：

• Q 是有限狀態(tài)集合。上圖所有的圓圈構(gòu)成了一個(gè)有限狀態(tài)集合
• Σ 是有限的輸入事件集合。上圖中，引起狀態(tài)轉(zhuǎn)移，標(biāo)注在狀態(tài)轉(zhuǎn)移線段上的字母就是輸入事件集合，t, o, e, a, d, n, A, i, n 構(gòu)成輸入事件集合
• q0 是一個(gè)起始狀態(tài)。上圖中，根節(jié)點(diǎn)就是起始狀態(tài)。
• F 是一組可接受的終止?fàn)顟B(tài)。上圖中，有標(biāo)注數(shù)字的圓圈就代表一個(gè)可接受的終止?fàn)顟B(tài)，to, tea, ted, ten, A, i, in, inn。從詞典的角度考慮，所有構(gòu)成合法單詞的狀態(tài)就是可接受的終止?fàn)顟B(tài)。

上述對(duì)應(yīng)關(guān)系里，我們漏了狀態(tài)轉(zhuǎn)移函數(shù)。確定有限狀態(tài)機(jī)的關(guān)鍵點(diǎn)在狀態(tài)轉(zhuǎn)移上，如果當(dāng)前狀態(tài)遇到一個(gè)確定的事件時(shí)，最多只能轉(zhuǎn)移到一個(gè)確定的狀態(tài)上，那么這就是一個(gè)確定有限狀態(tài)機(jī)，簡(jiǎn)稱 DFA。為什么有最多一個(gè)確定狀態(tài)這一說法？因?yàn)榭赡軟]有下一個(gè)狀態(tài)，對(duì)詞典的例子來(lái)說，如果沒有下一個(gè)狀態(tài)，就說明要查找的詞不在詞典里。比如我們要查找 "too" 這個(gè)單詞，當(dāng)消耗完 "t", "o" 兩個(gè)字母后，還剩下一個(gè) "o" ，這個(gè)時(shí)候應(yīng)該還要有下一個(gè)由 "o" 觸發(fā)的確定的狀態(tài)才對(duì)，但在上圖中找不到，說明 "too" 這個(gè)單詞不在上圖表示的詞典里。

聰明的你可能會(huì)問，如果一個(gè)輸入事件，導(dǎo)致可能轉(zhuǎn)移到不同的狀態(tài)去，每種狀態(tài)有不同的概率，這是什么？答案是不確定有限狀態(tài)機(jī)。感興趣的搜索一下馬爾可夫鏈。等你研究完馬爾可夫鏈會(huì)發(fā)現(xiàn)，下一步要看隱馬爾可夫模型了?？瓤?，這段文字純屬裝逼，我們還是就此打住，繼續(xù)今天的課題吧。

狀態(tài)轉(zhuǎn)移表

我們終于把 Trie 和 DFA 聯(lián)系起來(lái)了。在 DFA 里，狀態(tài)轉(zhuǎn)移函數(shù)一般使用狀態(tài)轉(zhuǎn)移表來(lái)描述。這是個(gè)二維的表格，行用來(lái)表示所有的狀態(tài)集合，列用來(lái)表示輸入事件集合。

我們來(lái)看一個(gè)最簡(jiǎn)單的使用 Trie 描述的詞典：

           t        o
begin(0) ---> t(1) ---> to(2:F)
                   |
                   | e          a
                   ----> te(3) ---> tea(4:F)
                               |
                               | d
                               ---> ted(5:F)
                               |
                               | n
                               ---> ten(6:F)

這是本文示例圖片的一小部分，這個(gè)詞典只包含四個(gè)單詞，分別是 to, tea, ted, ten。從 DFA 的角度來(lái)看，它總共有 7 個(gè)狀態(tài)，包含一個(gè)狀態(tài)為 0 的起始狀態(tài)。輸入事件集合是 [t, o, e, a, d, n]?？山邮艿慕K止?fàn)顟B(tài)集合就是上圖中標(biāo)注著 ":F" 字樣的狀態(tài)，就是四個(gè)有效的單詞。那么上述詞典所代表的 DFA 的的狀態(tài)轉(zhuǎn)移表長(zhǎng)什么樣呢？

表一：狀態(tài)轉(zhuǎn)移表

這就是上述 DFA 的狀態(tài)轉(zhuǎn)移表。從表中，我們可以清晰地看到。[0, 1, 2, 3, 4, 5, 6] 表示我們的 DFA 中的 7 個(gè)狀態(tài)。而 [t, o, e, a, d, n] 表示我們的輸入事件。表格中的數(shù)字表示當(dāng)前狀態(tài)遇到輸入事件后能正確轉(zhuǎn)移的下一個(gè)狀態(tài)，其中 x 表示出錯(cuò)，即無(wú)法轉(zhuǎn)移到下一個(gè)有效狀態(tài)。比如當(dāng)狀態(tài)為 0 時(shí)，遇到 t 即可轉(zhuǎn)移到狀態(tài) 1，而遇到其他的輸入事件，則無(wú)法轉(zhuǎn)移到有效狀態(tài)。聰明如你，試著畫一下圖一的狀態(tài)轉(zhuǎn)移表吧。

雙數(shù)組 Trie

狀態(tài)轉(zhuǎn)移表很好很強(qiáng)大，可以實(shí)現(xiàn) O(1) 的搜索速度。但其不足非常明顯，如表一所示，表中 x 非常多。即針對(duì)詞典來(lái)說，其 DFA 的狀態(tài)轉(zhuǎn)移表中，有效的狀態(tài)轉(zhuǎn)移只占少數(shù)，大部分都是無(wú)效的狀態(tài)轉(zhuǎn)移。聰明的科學(xué)家們哪能放過這個(gè)揚(yáng)名立萬(wàn)的機(jī)會(huì)？特別是在計(jì)算機(jī)的早期，內(nèi)存非常寶貴，往往以字節(jié)計(jì)算價(jià)格，哪像現(xiàn)在，各位的手機(jī)動(dòng)不動(dòng)就有幾個(gè) G 的內(nèi)存。

在 1985 年科學(xué)家發(fā)明了一個(gè)壓縮算法，可以用三個(gè)數(shù)組即可表達(dá)狀態(tài)轉(zhuǎn)移表。1989 年更進(jìn)一步壓縮到只用兩個(gè)數(shù)組即可表達(dá)狀態(tài)轉(zhuǎn)移表。詳細(xì)信息可以閱讀 An Implementation of Double-Array Trie。這個(gè)頁(yè)面里包含兩個(gè)實(shí)現(xiàn)，一個(gè)是早期的使用 C++ 模板類的實(shí)現(xiàn)，稱為 midatrie ，網(wǎng)上比較著名的開源分詞算法庫(kù) LibMMSeg 就使用這一實(shí)現(xiàn)。另外一個(gè)實(shí)現(xiàn)是使用 C 語(yǔ)言重寫的，稱為 libdatrie，它更通用，可讀性也比較強(qiáng)。

要使用兩個(gè)數(shù)組實(shí)現(xiàn) Tire 并非簡(jiǎn)單的事情，要理解這一過程沒有燒些腦細(xì)胞估計(jì)很難做到，除非你是個(gè)天才。除此之外，還有一些細(xì)節(jié)需要了解，對(duì)理解代碼不無(wú)益處：

• 上文討論中，我們都使用英文作為詞典保存對(duì)象。輸入事件集合就是一個(gè)個(gè)字母。實(shí)際上，中文的處理方法類似，如果是 utf-8 編碼，中文會(huì)把一個(gè)字拆成三個(gè)字節(jié)，然后以字節(jié)為單位，作為輸入事件集合中的一個(gè)元素。比如“中文”這兩個(gè)字的 utf-8 編碼是 E4 B8 AD E6 96 87，其實(shí)際上被解讀為 6 個(gè)輸入事件。由此可見，對(duì)任何語(yǔ)言，輸入事件總數(shù)不會(huì)超過 255 個(gè)?？梢允褂靡粋€(gè)字節(jié)來(lái)表示。
• 輸入事件并非連續(xù)的，所以在實(shí)現(xiàn) Tire 時(shí)，一般會(huì)有個(gè)映射關(guān)系，比如把 a 映射到 1，把 b 映射到 2 等。這是為了更進(jìn)一步節(jié)省空調(diào)。

應(yīng)用場(chǎng)景

Trie 構(gòu)造的詞典除了在分詞算法里使用外，在自動(dòng)完成 Auto Complete，拼寫糾正等領(lǐng)域都有非常廣泛的應(yīng)用。