前言

中文分詞算法是指將一個漢字序列切分成一個一個單獨的詞，與英文以空格作為天然的分隔符不同，中文字符在語義識別時，需要把數(shù)個字符組合成詞，才能表達出真正的含義。分詞算法是文本挖掘的基礎，通常應用于自然語言處理、搜索引擎、智能推薦等領域。

一、 分詞算法分類

中文分詞算法大概分為三大類，第一類是基于字符串匹配，即掃描字符串，如果發(fā)現(xiàn)字符串的子串和詞典中的詞相同，就算匹配，比如機械分詞方法。這類分詞通常會加入一些啟發(fā)式規(guī)則，比如“正向/反向最大匹配”，“長詞優(yōu)先”等。第二類是基于統(tǒng)計以及機器學習的分詞方法，它們基于人工標注的詞性和統(tǒng)計特征，對中文進行建模，即根據(jù)觀測到的數(shù)據(jù)(標注好的語料)對模型參數(shù)進行訓練，在分詞階段再通過模型計算各種分詞出現(xiàn)的概率，將概率最大的分詞結果作為最終結果。常見的序列標注模型有HMM和CRF。這類分詞算法能很好處理歧義和未登錄詞問題，效果比前一類效果好，但是需要大量的人工標注數(shù)據(jù)，以及較慢的分詞速度。第三類是通過讓計算機模擬人對句子的理解，達到識別詞的效果，由于漢語語義的復雜性，難以將各種語言信息組織成機器能夠識別的形式，目前這種分詞系統(tǒng)還處于試驗階段。

二、 機械分詞算法

機械分詞方法又叫基于字符串匹配的分詞方法，它是按照一定的策略將待分析的字符串與一個“充分大的”機器詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功(識別出一個詞)。這是最簡單的分詞方法，但非常高效和常見。

(1) 匹配方法

機械分詞方法按照掃描方向的不同，可以分為正向匹配和逆向匹配;按照不同長度優(yōu)先匹配的情況，可以分為最大(最長)匹配和最小(最短)匹配;常用的幾種機械分詞方法如下：

l 正向最大匹配法(由左到右的方向);如以例句“達觀數(shù)據(jù)是一家大數(shù)據(jù)公司”，使用正向最大匹配法分詞的結果為“達觀/數(shù)據(jù)/是一/家/大數(shù)據(jù)/公司”

l 逆向最大匹配法(由右到左的方向);同樣以例句“達觀數(shù)據(jù)是一家大數(shù)據(jù)公司”，使用逆向最大匹配法分詞的結果為“達觀/數(shù)據(jù)/是/一家/大數(shù)據(jù)/公司”

l 最少切分(使每一句中切出的詞數(shù)最小)。例句“達觀數(shù)據(jù)是一家大數(shù)據(jù)公司”被分為“達觀數(shù)據(jù)/是/一家/大數(shù)據(jù)公司”。

(2) 消除歧義

因為同一個句子，在機械分詞中經(jīng)常會出現(xiàn)多種分詞的組合，因此需要進行歧義消除，來得到最優(yōu)的分詞結果。

以很常見的MMSEG機械分詞算法為例，MMSEG在搜索引擎Solr中經(jīng)常使用到，是一種非常可靠高效的分詞算法。MMSEG消除歧義的規(guī)則有四個，它在使用中依次用這四個規(guī)則進行過濾，直到只有一種結果或者第四個規(guī)則使用完畢。這個四個規(guī)則分別是：

l 最大匹配，選擇“詞組長度最大的”那個詞組，然后選擇這個詞組的第一個詞，作為切分出的第一個詞，如對于“中國人民萬歲”，匹配結果分別為：

中/國/人

中國/人/民

中國/人民/萬歲

中國人/民/萬歲

在這個例子“詞組長度最長的”詞組為后兩個，因此選擇了“中國人/民/萬歲”中的“中國人”，或者“中國/人民/萬歲”中的“中國”。

l 最大平均詞語長度。經(jīng)過規(guī)則1過濾后，如果剩余的詞組超過1個，那就選擇平均詞語長度最大的那個(平均詞長=詞組總字數(shù)/詞語數(shù)量)。比如“生活水平”，可能得到如下詞組：

生/活水/平 (4/3=1.33)

生活/水/平 (4/3=1.33)

生活/水平 (4/2=2)

根據(jù)此規(guī)則，就可以確定選擇“生活/水平”這個詞組

l 詞語長度的最小變化率，這個變化率一般可以由標準差來決定。比如對于“中國人民萬歲”這個短語，可以計算：

中國/人民/萬歲(標準差=sqrt(((2-2)^2+(2-2)^2+(2-2^2))/3)=0)

中國人/民/萬歲(標準差=sqrt(((2-3)^2+(2-1)^2+(2-2)^2)/3)=0.8165)

于是選擇“中國/人民/萬歲”這個詞組。

l 計算詞組中的所有單字詞詞頻的自然對數(shù)，然后將得到的值相加，取總和最大的詞組。比如：

設施/和服/務

設施/和/服務

這兩個詞組中分別有“務”和“和”這兩個單字詞，假設“務”作為單字詞時候的頻率是5，“和”作為單字詞時候的頻率是10，對5和10取自然對數(shù)，然后取最大值者，所以取“和”字所在的詞組，即“設施/和/服務”。

(3) 機械分詞的缺陷

機械分詞方法是一種很簡單高效的分詞方法，它的速度很快，都是O(n)的時間復雜度，效果也可以。但缺點是對歧義和新詞的處理不是很好，對詞典中未出現(xiàn)的詞沒法進行處理，因此經(jīng)常需要其他分詞方法進行協(xié)作。

三、 基于n元語法的分詞算法

(1) 概念

基于詞的n元語法模型是一個典型的生成式模型，早期很多統(tǒng)計分詞均以它為基本模型，然后配合其他未登錄詞識別模塊進行擴展。其基本思想是：首先根據(jù)詞典(可以是從訓練語料中抽取出來的詞典，也可以是外部詞典)對句子進行簡單匹配，找出所有可能的詞典詞，然后，將它們和所有單個字作為結點，構造的n元切分詞圖，圖中的結點表示可能的詞候選，邊表示路徑，邊上的n元概率表示代價，最后利用相關搜索算法(動態(tài)規(guī)劃)從圖中找到代價最小的路徑作為最后的分詞結果。

圖1：n元語法分詞算法圖解

(2) 求解方法

假設隨機變量S為一個漢字序列，W是S上所有可能切分出來的詞序列，分詞過程應該是求解使條件概率P(W|S)最大的切分出來的詞序列W*，即：

根據(jù)貝葉斯公式，可以改寫為：

由于分母為歸一化因子，P(S|W)為固定的值，因此求解的公式變?yōu)椋?/p>

如果使用一元模型，則公式變?yōu)榍蠼猓?/p>

使用二元模型，公式變?yōu)榍蠼?/p>

以二元模型為例，在例圖中求解短語“結合成分子”時，分詞序列為“結合/成分/子”、“結合/成/分子”的概率分別為：

這里的P(結合|start)、P(成分|結合)、P(子|成分)、P(end|子) 都是通過大量的語料統(tǒng)計得出，因此可以通過概率相乘來判斷哪一個分詞序列更好。在例圖中，可以通過動態(tài)歸劃的算法算出最后最優(yōu)的分詞序列。

n元語法的分詞方法是基于統(tǒng)計的分詞算法，它比簡單的機械分詞算法精度更高，但算法基于現(xiàn)有的詞典，因此很難進行新詞發(fā)現(xiàn)處理。

四、 基于隱馬爾可夫模型的分詞算法

(1) 隱馬爾可夫模型

隱馬爾可夫模型(Hidden Markov Model，簡稱HMM)是結構最簡單的動態(tài)貝葉斯網(wǎng)絡(dynamic Bayesian network)，這是一種尤其著名的有向圖模型，主要用于時序數(shù)據(jù)建模，在語音識別、自然語言處理等領域有廣泛應用。在分詞算法中，隱馬爾可夫經(jīng)常用作能夠發(fā)現(xiàn)新詞的算法，通過海量的數(shù)據(jù)學習，能夠將人名、地名、互聯(lián)網(wǎng)上的新詞等一一識別出來，具有廣泛的應用場景。(達觀數(shù)據(jù) 江永青)

隱馬爾可夫模型是馬爾可夫鏈的一種，它的狀態(tài)不能直接觀察到，但能通過觀測向量序列觀察到，每一個觀測向量是由一個具有相應概率密度分布的狀態(tài)序列產(chǎn)生。如圖所示，隱馬爾可夫模型中的變量可分為兩組。第一組是狀態(tài)變量{y1, y2, …, yn}，其中yi表示第i時刻的系統(tǒng)狀態(tài)。通常假定狀態(tài)變量是隱藏的、不可被觀測的，因此狀態(tài)變量亦稱隱變量。第二組是觀測變量{x1, x2, …, xn}，其中xi表示第i時刻的觀測值。在隱馬爾可夫模型中，系統(tǒng)通常在多個狀態(tài)之間轉換，因此狀態(tài)變量yi的取值范圍通常是有N個可能取值的離散空間。

圖2：隱馬爾可夫模型圖解

圖中的箭頭表示了變量間的依賴關系。在任一時刻，觀測變量的取值僅依賴于狀態(tài)變量，即xi由yi決定，與其他狀態(tài)變量及觀測變量的取值無關。同時，i時刻的狀態(tài)yi僅依賴于i-1時刻的狀態(tài)yi-1，與其余n-2個狀態(tài)無關。這就是所謂的“馬爾可夫鏈”，即：系統(tǒng)下一時刻的狀態(tài)僅由當前狀態(tài)決定，不依賴于以往的任何狀態(tài)。

(2) 隱馬爾可夫的求解

一般的，一個HMM可以記作一個五元組u=(S, K, A, B, π), 其中S是狀態(tài)集合，K是輸出符號也就是觀察集合，A是狀態(tài)轉移概率，B是符號發(fā)射概率，π是初始狀態(tài)的概率分布。HMM主要解決三個基本問題：

l 估計問題，給定一個觀察序列O=O1,O2,O3,... ,Ot和模型u=(A,B,π)，計算觀察序列的概率;

l 序列問題，給定一個觀察序列O=O1,O2,O3... Ot和模型μ=(A, B, π)，計算最優(yōu)的狀態(tài)序列Q=q1,q2,q3...qt;

l 參數(shù)估計問題，給定一個觀察序列O=O1,O2,O3... Ot，如何調節(jié)模型μ=(A,B, π)的參數(shù)，使得P(O|μ)最大。

隱馬爾可夫的估計問題可以通過前向/后向的動態(tài)規(guī)劃算法來求解;序列問題可以通過viterbi算法求解;參數(shù)估計問題可以通過EM算法求解。通過海量的語料數(shù)據(jù)，可以方便快速地學習出HMM圖模型。

(3) HMM分詞方法

隱馬爾可夫的三大問題分別對應了分詞中的幾個步驟。參數(shù)估計問題即是分詞的學習階段，通過海量的語料數(shù)據(jù)來學習歸納出分詞模型的各個參數(shù)。狀態(tài)序列問題是分詞的執(zhí)行階段，通過觀察變量(即待分詞句子的序列)來預測出最優(yōu)的狀態(tài)序列(分詞結構)。

我們設定狀態(tài)值集合S =(B, M, E, S)，分別代表每個狀態(tài)代表的是該字在詞語中的位置，B代表該字是詞語中的起始字，M代表是詞語中的中間字，E代表是詞語中的結束字，S則代表是單字成詞;觀察值集合K =(所有的漢字);則中文分詞的問題就是通過觀察序列來預測出最優(yōu)的狀態(tài)序列。

比如觀察序列為：

O = 小紅就職于達觀數(shù)據(jù)

預測的狀態(tài)序列為：

Q = BEBESBMME

根據(jù)這個狀態(tài)序列我們可以進行切詞：

BE/BE/S/BMME/

所以切詞結果如下：

小紅/就職/于/達觀數(shù)據(jù)/

因為HMM分詞算法是基于字的狀態(tài)(BEMS)來進行分詞的，因此很適合用于新詞發(fā)現(xiàn)，某一個新詞只要標記為如“BMME”，就算它沒有在歷史詞典中出現(xiàn)過，HMM分詞算法也能將它識別出來。

五、 基于條件隨機場的分詞算法

(1) 條件隨機場模型

條件隨機場(Conditional Random Field，簡稱CRF)是一種判別式無向圖模型，它是隨機場的一種，常用于標注或分析序列語料，如自然語言文字或是生物序列。跟隱馬爾可夫模型通過聯(lián)合分布進行建模不同，條件隨機場試圖對多個變量在給定觀測值后的條件概率進行建模。(達觀數(shù)據(jù) 江永青)

具體來說，若令x = {x1, x2, …, xn}為觀測序列，y = {y1, y2, …, yn}為與之對應的標記序列，則條件隨機場的目標是構建條件概率模型P(y | x)。令圖G = 表示結點與標記變量y中元素一一對應的無向圖，yv表示與結點v對應的標記變量，n(v)表示結點v的鄰接結點，如果圖G的每個變量yv都滿足馬爾可夫性，即：

則(y, x)構成一個條件隨機場。也就是說， 條件概率只與x和y的鄰接結點有關，與其他的y結點沒有關系。

圖3：條件隨機場模型圖解

理論上來說，圖G可具有任意結構，只要能表示標記變量之間的條件獨立性關系即可。但在現(xiàn)實應用中，尤其是對標記序列建模時，最常用的仍然是上圖所示的鏈式結構，即“鏈式條件隨機場”。

(2) 條件隨機場的求解方法

條件隨機場使用勢函數(shù)和圖結構上的團來定義條件概率P(y | x)。給定觀測序列x，鏈式條件隨機場主要包含兩種關于標記變量的團，即單個標記變量{yi}以及相鄰的標記變量{yi-1，yi}。在條件隨機場中，通過選用合適的勢函數(shù)，并引入特征函數(shù)，可以得到條件概率的定義：

其中：

其中tk(yi - 1, yi, x, i)是定義在觀測序列的兩個相鄰標記位置上的轉移特征函數(shù)，用于刻畫相鄰標記變量之間的相關關系以及觀測序列對它們的影響， (yi, x, i)是定義在觀測序列的標記位置i上的狀態(tài)特征函數(shù)，用于刻畫觀測序列對標記變量的影響，λk和 為參數(shù)，Z為規(guī)范化因子。

可以將tk(yi - 1, yi, x, i)和sl(yi, x, i)兩個特征函數(shù)統(tǒng)一為：fk(yi-1, yi, x, i)，則有：

其中：

已知訓練數(shù)據(jù)集，由此可知經(jīng)驗概率分布 ，可以通過極大化訓練數(shù)據(jù)的對數(shù)似然函數(shù)來求模型參數(shù)。加入懲罰項后，訓練數(shù)據(jù)的對數(shù)似然函數(shù)為：

其中的σ是可以調節(jié)的懲罰權重。對似然函數(shù)L(w)中的w求偏導，令：

可以依次求出wi。

(3) 條件隨機場分詞方法

條件隨機場和隱馬爾可夫一樣，也是使用BMES四個狀態(tài)位來進行分詞。以如下句子為例：

中 國 是 泱 泱 大 國

B B B B B B B

M M M M M M M

E E E E E E E

S S S S S S S

條件隨機場解碼就是在以上由標記組成的數(shù)組中搜索一條最優(yōu)的路徑。

我們要把每一個字(即觀察變量)對應的每一個狀態(tài)BMES(即標記變量)的概率都求出來。例如對于觀察變量“國”，當前標記變量為E，前一個觀察變量為“中”，前一個標記變量為B，則：

t(B, E, ‘國’) 對應到條件隨機場里相鄰標記變量{yi-1, yi}的勢函數(shù)：

s(E, ‘國’) 對應到條件隨機場里單個標記變量{yi}對應的勢函數(shù)sl(yi, x, i)：

t(B, E, ‘國’), s(E, ‘國’)相應的權值λk， 都是由條件隨機場用大量的標注語料訓練出來。因此分詞的標記識別就是求對于各個觀察變量，它們的標記變量(BMES)狀態(tài)序列的概率最大值，即求：

的概率組合最大值。這個解法與隱馬爾可夫類似，都是可以用viterbi算法求解。

(4) 條件隨機場分詞的優(yōu)缺點

條件隨機場分詞是一種精度很高的分詞方法，它比隱馬爾可夫的精度要高，是因為隱馬爾可夫假設觀察變量xi只與當前狀態(tài)yi有關，而與其它狀態(tài)yi-1，yi+1無關;而條件隨機場假設了當前觀察變量xi與上下文相關，如 ，就是考慮到上一個字標記狀態(tài)為B時，當前標記狀態(tài)為E并且輸出“國”字的概率。因此通過上下文的分析，條件隨機場分詞會提升到更高的精度。但因為復雜度比較高，條件隨機場一般訓練代價都比較大。

六、 達觀數(shù)據(jù)分詞算法應用

達觀數(shù)據(jù)是一家新興高科技大數(shù)據(jù)公司，創(chuàng)始人來自騰訊、百度、盛大、搜狗等知名企業(yè)，具有非常深厚的技術實力。在分詞技術領域，達觀數(shù)據(jù)借鑒國內外優(yōu)秀的項目，升級了不少分詞算法，并積累了大量的分詞詞典。此外，達觀文本挖掘融合了全套自然語言處理技術和機器學習技術，在分詞基礎文字處理功能上集成了詞性標注、句法分析、命名實體識別、文本標簽提取等功能模塊，基于此再結合SVM、GBRT、logistic regression等機器學習算法，實現(xiàn)認知層次上的文本自動分類、涉黃涉政分析、垃圾評論識別等功能。

總結

本文介紹了常見的幾種分詞算法及其原理，分析了它們對應的優(yōu)缺點。應用在文本挖掘、搜索引擎等領域，需要根據(jù)不同場景，使用不同的分詞算法及詞典，才能最有效地達到準確分詞的效果。

作者簡介：

江永青，浙江大學軟件工程專業(yè)碩士，曾在盛大創(chuàng)新院負責搜索引擎的索引和檢索模塊，在盛大文學數(shù)據(jù)中心負責大數(shù)據(jù)分布式系統(tǒng)、搜索引擎架構、搜索行為分析。現(xiàn)任達觀數(shù)據(jù)聯(lián)合創(chuàng)始人，對搜索引擎、數(shù)據(jù)挖掘和大數(shù)據(jù)技術有豐富的經(jīng)驗和較深入的理解。

注：本文由達觀數(shù)據(jù)投稿數(shù)據(jù)猿發(fā)布

來源：數(shù)據(jù)猿