簡介
NLP的底層任務(wù)由易到難大致可以分為詞法分析、句法分析和語義分析。分詞是詞法分析（還包括詞性標注和命名實體識別）中最基本的任務(wù)，可以說既簡單又復雜。說簡單是因為分詞的算法研究已經(jīng)很成熟了，大部分的準確率都可以達到95%以上，說復雜是因為剩下的5%很難有突破，主要因為三點：
粒度，不同應(yīng)用對粒度的要求不一樣，比如“蘋果手機”可以是一個詞也可以是兩個詞
歧義，比如“下雨天留人天留我不留”
未登錄詞，比如“skrrr”、“打call”等新興詞語
然而，在真實的應(yīng)用中往往會因為以上的難點造成分詞效果欠佳，進而影響之后的任務(wù)。對于追求算法表現(xiàn)的童鞋來說，不僅要會調(diào)分詞包，也要對這些基礎(chǔ)技術(shù)有一定的了解，在做真正的工業(yè)級應(yīng)用時有能力對分詞器進行調(diào)整。這篇文章不是著重介紹某個SOTA成果，而是對常用的分詞算法（不僅是機器學習或神經(jīng)網(wǎng)絡(luò)，還包括動態(tài)規(guī)劃等）以及其核心思想進行介紹。
分詞算法
我認為分詞算法根據(jù)其核心思想主要分為兩種，第一種是基于詞典的分詞，先把句子按照字典切分成詞，再尋找詞的最佳組合方式；第二種是基于字的分詞，即由字構(gòu)詞，先把句子分成一個個字，再將字組合成詞，尋找最優(yōu)的切分策略，同時也可以轉(zhuǎn)化成序列標注問題。歸根結(jié)底，上述兩種方法都可以歸結(jié)為在圖或者概率圖上尋找最短路徑的問題。接下來將以“他說的確實在理”這句話為例，講解各個不同的分詞算法核心思想。
1.基于詞典的分詞
最大匹配分詞算法
最大匹配分詞尋找最優(yōu)組合的方式是將匹配到的最長詞組合在一起。主要的思路是先將詞典構(gòu)造成一棵Trie樹，也稱為字典樹，如下圖：
Trie樹由詞的公共前綴構(gòu)成節(jié)點，降低了存儲空間的同時提升查找效率。最大匹配分詞將句子與Trie樹進行匹配，在匹配到根結(jié)點時由下一個字重新開始進行查找。比如正向（從左至右）匹配“他說的確實在理”，得出的結(jié)果為“他／說／的確／實在／理”。如果進行反向最大匹配，則為“他／說／的／確實／在理”。
可見，詞典分詞雖然可以在O(n)時間對句子進行分詞，但是效果很差，在實際情況中基本不使用此種方法。
最短路徑分詞算法
最短路徑分詞算法首先將一句話中的所有詞匹配出來，構(gòu)成詞圖（有向無環(huán)圖DAG），之后尋找從起始點到終點的最短路徑作為最佳組合方式，引用《統(tǒng)計自然語言處理》中的圖：
我們認為圖中每個詞的權(quán)重都是相等的，因此每條邊的權(quán)重都為1。
在求解DAG圖的最短路徑問題時，總是要利用到一種性質(zhì)：即兩點之間的最短路徑也包含了路徑上其他頂點間的最短路徑。比如S->A->B->E為S到E到最短路徑，那S->A->B一定是S到B到最短路徑，否則會存在一點C使得d(S->C->B)<d(S->A->B)，那S到E的最短路徑也會變?yōu)镾->C->B->E，這就與假設(shè)矛盾了。利用上述的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以利用貪心算法或動態(tài)規(guī)劃兩種求解算法：
1. 最短路徑分詞算法
基于Dijkstra算法求解最短路徑。該算法適用于所有帶權(quán)有向圖，求解源節(jié)點到其他所有節(jié)點的最短路徑，并可以求得全局最優(yōu)解。Dijkstra本質(zhì)為貪心算法，在每一步走到當前路徑最短的節(jié)點，遞推地更新原節(jié)點到其他節(jié)點的距離。針對當前問題，Dijkstra算法的計算結(jié)果為：“他／說／的／確實／在理“。可見最短路徑分詞算法可以滿足部分分詞要求。但當存在多條距離相同的最短路徑時，Dijkstra只保存一條，對其他路徑不公平，也缺乏理論依據(jù)。
2. N-最短路徑分詞算法
N-最短路徑分詞是對Dijkstra算法的擴展，在每一步保存最短的N條路徑，并記錄這些路徑上當前節(jié)點的前驅(qū)，在最后求得最優(yōu)解時回溯得到最短路徑。該方法的準確率優(yōu)于Dijkstra算法，但在時間和空間復雜度上都更大。
基于n-gram model的分詞算法
在前文的詞圖中，邊的權(quán)重都為1。而現(xiàn)實中卻不一樣，常用詞的出現(xiàn)頻率／概率肯定比罕見詞要大。因此可以將求解詞圖最短路徑的問題轉(zhuǎn)化為求解最大概率路徑的問題，即分詞結(jié)果為“最有可能的詞的組合“。計算詞出現(xiàn)的概率，僅有詞典是不夠的，還需要有充足的語料。因此分詞任務(wù)已經(jīng)從單純的“算法”上升到了“建?！?，即利用統(tǒng)計學方法結(jié)合大數(shù)據(jù)挖掘，對“語言”進行建模。
語言模型的目的是構(gòu)建一句話出現(xiàn)的概率p(s)，根據(jù)條件概率公式我們知道：
而要真正計算“他說的確實在理”出現(xiàn)的概率，就必須計算出上述的概率，計算量太過龐大，因此我們近似地認為：
其中
為字或單詞。我們將上述模型稱為二元語言模型(2-gram model)。類似的，如果只對詞頻進行統(tǒng)計，則為一元語言模型。由于計算量的限制，在實際應(yīng)用中n一般取3。
我們將基于詞的語言模型所統(tǒng)計出的概率分布應(yīng)用到詞圖中，可以得到詞的概率圖：
對該詞圖用最短路徑的算法求解最大概率的路徑，即可得到分詞結(jié)果。
2.基于字的分詞
與基于詞典的分詞不同的是，基于字的分詞事先不對句子進行詞的匹配，而是將分詞看成序列標注問題，把一個字標記成B(Begin), I(Inside), O(Outside), E(End), S(Single)。因此也可以看成是每個字的分類問題，輸入為每個字及其前后字所構(gòu)成的特征，輸出為分類標記。對于分類問題，可以用統(tǒng)計機器學習或神經(jīng)網(wǎng)絡(luò)的方法求解。
統(tǒng)計機器學習方法通過一系列算法對問題進行抽象，進而得到模型，再用得到的模型去解決相似的問題。也可以將模型看成一個函數(shù)，輸入X，得到f(X)=Y。另外，機器學習中一般將模型分為兩類：生成式模型和判別式模型，兩者的本質(zhì)區(qū)別在于X和Y的生成關(guān)系。生成式模型以“輸出Y按照一定的規(guī)律生成輸入X”為假設(shè)對P(X,Y)聯(lián)合概率進行建模；判別式模型認為Y由X決定，直接對后驗概率P(Y|X)進行建模。兩者各有利弊，生成模型對變量的關(guān)系描述更加清晰，而判別式模型容易建立和學習。下面對幾種序列標注方法做簡要介紹。
生成式模型分詞算法
生成式模型主要有n-gram模型、HMM隱馬爾可夫模型、樸素貝葉斯分類等。在分詞中應(yīng)用比較多的是n-gram模型和HMM模型。如果將2.1.3中的節(jié)點由詞改成字，則可基于字的n-gram模型進行分詞，不過這種方法的效果沒有基于詞的效果要好。
HMM模型認為在解決序列標注問題時存在兩種序列，一種是觀測序列，即人們顯性觀察到的句子，而序列標簽是隱狀態(tài)序列，即觀測序列為X，隱狀態(tài)序列是Y，因果關(guān)系為Y->X。因此要得到標注結(jié)果Y，必須對X的概率、Y的概率、P(X|Y)進行計算，即建立P(X,Y)的概率分布模型。例句的隱馬爾科夫序列如下圖：
HMM模型是常用的分詞模型，基于Python的jieba分詞器和基于Java的HanLP分詞器都使用了HMM。要注意的是，該模型創(chuàng)建的概率圖與上文中的DAG圖并不同，因為節(jié)點具有觀測概率，所以不能再用上文中的算法求解，而應(yīng)該使用Viterbi算法求解最大概率的路徑。
判別式模型分詞算法
判別式模型主要有感知機、SVM支持向量機、CRF條件隨機場、最大熵模型等。在分詞中常用的有感知機模型和CRF模型：
- 平均感知機分詞算法
感知機是一種簡單的二分類線性模型，通過構(gòu)造超平面，將特征空間（輸入空間）中的樣本分為正負兩類。通過組合，感知機也可以處理多分類問題。但由于每次迭代都會更新模型的所有權(quán)重，被誤分類的樣本會造成很大影響，因此采用平均的方法，在處理完一部分樣本后對更新的權(quán)重進行平均。
- CRF分詞算法
CRF可以看作一個無向圖模型，對于給定的標注序列Y和觀測序列X，對條件概率P(Y|X)進行定義，而不是對聯(lián)合概率建模。CRF可以說是目前最常用的分詞、詞性標注和實體識別算法，它對未登陸詞有很好的識別能力，但開銷較大。
神經(jīng)網(wǎng)絡(luò)分詞算法
在NLP中，最常用的神經(jīng)網(wǎng)絡(luò)為循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN，Recurrent Neural Network），它在處理變長輸入和序列輸入問題中有著巨大的優(yōu)勢。LSTM為RNN變種的一種，在一定程度上解決了RNN在訓練過程中梯度消失和梯度爆炸的問題。雙向（Bidirectional）循環(huán)神經(jīng)網(wǎng)絡(luò)分別從句子的開頭和結(jié)尾開始對輸入進行處理，將上下文信息進行編碼，提升預測效果。
目前對于序列標注任務(wù)，公認效果最好的模型是BiLSTM+CRF。結(jié)構(gòu)如圖：
利用雙向循環(huán)神經(jīng)網(wǎng)絡(luò)BiLSTM，相比于上述其它模型，可以更好的編碼當前字等上下文信息，并在最終增加CRF層，核心是用Viterbi算法進行解碼，以得到全局最優(yōu)解，避免B,S,E這種標記結(jié)果的出現(xiàn)。
3.分詞算法中的數(shù)據(jù)結(jié)構(gòu)
前文主要講了分詞任務(wù)中所用到的算法和模型，但在實際的工業(yè)級應(yīng)用中，僅僅有算法是不夠的，還需要高效的數(shù)據(jù)結(jié)構(gòu)進行輔助。
詞典
中文有7000多個常用字，56000多個常用詞，要將這些數(shù)據(jù)加載到內(nèi)存雖然容易，但進行高并發(fā)毫秒級運算是困難的，這就需要設(shè)計巧妙的數(shù)據(jù)結(jié)構(gòu)和存儲方式。前文提到的Trie樹只可以在O(n)時間完成單模式匹配，識別出“的確”后到達Trie樹對也節(jié)點，句子指針接著指向“實”，再識別“實在”，而無法識別“確實”這個詞。如果要在O(n)時間完成多模式匹配，構(gòu)建詞圖，就需要用到Aho-Corasick算法將模式串預處理為有限狀態(tài)自動機，如模式串是he/she/his/hers，文本為“ushers”。構(gòu)建的自動機如圖：
這樣，在第一次到葉節(jié)點5時，下一步的匹配可以直接從節(jié)點2開始，一次遍歷就可以識別出所有的模式串。
對于數(shù)據(jù)結(jié)構(gòu)的存儲，一般可以用鏈表或者數(shù)組，兩者在查找、插入和刪除操作的復雜度上各有千秋。在基于Java的高性能分詞器HanLP中，作者使用雙數(shù)組完成了Trie樹和自動機的存儲。
詞圖
圖作為一種常見的數(shù)據(jù)結(jié)構(gòu)，其存儲方式一般有兩種：
- 鄰接矩陣
鄰接矩陣用數(shù)組下標代表節(jié)點，值代表邊的權(quán)重，即d[i][j]=v代表節(jié)點i和節(jié)點j間的邊權(quán)重為v。如下圖：
用矩陣存儲圖的空間復雜度較高，在存儲稀疏圖時不建議使用。
- 鄰接表
鄰接表對圖中的每個節(jié)點建立一個單鏈表，對于稀疏圖可以極大地節(jié)省存儲空間。第i個單鏈表中的節(jié)點表示依附于頂點i的邊，如下圖：
在實際應(yīng)用中，尤其是用Viterbi算法求解最優(yōu)路徑時，由于是按照廣度優(yōu)先的策略對圖進行遍歷，最好是使用鄰接表對圖進行存儲，便于訪問某個節(jié)點下的所有節(jié)點。
總結(jié)
分詞作為NLP底層任務(wù)之一，既簡單又重要，很多時候上層算法的錯誤都是由分詞結(jié)果導致的。因此，對于底層實現(xiàn)的算法工程師，不僅需要深入理解分詞算法，更需要懂得如何高效地實現(xiàn)。而對于上層應(yīng)用的算法工程師，在實際分詞時，需要根據(jù)業(yè)務(wù)場景有選擇地應(yīng)用上述算法，比如在搜索引擎對大規(guī)模網(wǎng)頁進行內(nèi)容解析時，對分詞對速度要求大于精度，而在智能問答中由于句子較短，對分詞的精度要求大于速度。
參考：https://zhuanlan.zhihu.com/p/50444885
答疑
tire樹：https://zhuanlan.zhihu.com/p/52419343
序列標注：https://zhuanlan.zhihu.com/p/50184092
