轉(zhuǎn)載請注明：終小南 ? 中文分詞算法總結(jié)

什么是中文分詞
眾所周知，英文是以 詞為單位的，詞和詞之間是靠空格隔開，而中文是以字為單位，句子中所有的字連起來才能描述一個意思。例如，英文句子I am a student，用中文則為：“我是一個學(xué)生”。計(jì)算機(jī)可以很簡單通過空格知道student是一個單詞，但是不能很容易明白“學(xué)”、“生”兩個字合起來 才表示一個詞。把中文的漢字序列切分成有意義的詞，就是中文分詞，有些人也稱為切詞。我是一個學(xué)生，分詞的結(jié)果是：我 是 一個 學(xué)生。

中文分詞和搜索引擎
中文分詞到底對搜索引擎有多大影響？對于搜索引擎來說，最重要的并不是找到所有結(jié)果，因?yàn)樵谏习賰|的網(wǎng)頁中找到所有結(jié)果沒有太多的意義，沒有人能看得完，最重要的是把最相關(guān)的結(jié)果排在最前面，這也稱為相關(guān)度排序。中文分詞的準(zhǔn)確與否，常常直接影響到對搜索結(jié)果的相關(guān)度排序。筆者最近替朋友找一些關(guān)于日本和服的資料，在搜索引擎上輸入“和服”，得到的結(jié)果就發(fā)現(xiàn)了很多問題。下面就以這個例子來說明分詞對搜索結(jié)果的影響，在現(xiàn)有三個中文搜索引擎上做測試，測試方法是直接在Google（http://www.google.com）、百度（http://www.baidu.com）上以“和服”為關(guān)鍵詞進(jìn)行搜索：

在Google上輸入“和服”搜索所有中文簡體網(wǎng)頁，總共結(jié)果507,000條，前20條結(jié)果中有14條與和服一點(diǎn)關(guān)系都沒有。

在百度上輸入“和服”搜索網(wǎng)頁，總共結(jié)果為287,000條，前20條結(jié)果中有6條與和服一點(diǎn)關(guān)系都沒有。

在中搜上輸入“和服”搜索網(wǎng)頁，總共結(jié)果為26,917條，前20條結(jié)果都是與和服相關(guān)的網(wǎng)頁。

這次搜索引擎結(jié)果中的錯誤，就是由于分詞的不準(zhǔn)確所造成的。通過筆者的了解，Google的中文分詞技術(shù)采用的是美國一家名叫Basis Technology（http://www.basistech.com）的公司提供的中文分詞技術(shù)，百度使用的是自己公司開發(fā)的分詞技術(shù)，中搜使用的是國內(nèi)海量科技（http://www.hylanda.com）提供的分詞技術(shù)。由此可見，中文分詞的準(zhǔn)確度，對搜索引擎結(jié)果相關(guān)性和準(zhǔn)確性有相當(dāng)大的關(guān)系。

中文分詞技術(shù)
中文分詞技術(shù)屬于自然語言處理技術(shù)范疇，對于一句話，人可以通過自己的知識來明白哪些是詞，哪些不是詞，但如何讓計(jì)算機(jī)也能理解？其處理過程就是分詞算法。

現(xiàn)有的分詞算法可分為三大類：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計(jì)的分詞方法。

1、基于字符串匹配的分詞方法
這種方法又叫做機(jī)械分詞方法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機(jī)器詞典中的詞條進(jìn)行配，若在詞典中找到某個字符串，則匹配成功 （識別出一個詞）。按照掃描方向的不同，串匹配分詞方法可以分為正向匹配和逆向匹配；按照不同長度優(yōu)先匹配的情況，可以分為最大（最長）匹配和最?。ㄗ?短）匹配；按照是否與詞性標(biāo)注過程相結(jié)合，又可以分為單純分詞方法和分詞與標(biāo)注相結(jié)合的一體化方法。常用的幾種機(jī)械分詞方法如下：

正向最大匹配法（由左到右的方向）；
逆向最大匹配法（由右到左的方向）；
最少切分（使每一句中切出的詞數(shù)最小）。
還可以將上述各種方法相互組合，例如，可以將正向最大匹配方法和逆向最大匹配方法結(jié)合起來構(gòu)成雙向匹配法。由于漢語單字成詞的特點(diǎn)，正向最小匹配和逆向 最小匹配一般很少使用。一般說來，逆向匹配的切分精度略高于正向匹配，遇到的歧義現(xiàn)象也較少。統(tǒng)計(jì)結(jié)果表明，單純使用正向最大匹配的錯誤率為1/169， 單純使用逆向最大匹配的錯誤率為1/245。但這種精度還遠(yuǎn)遠(yuǎn)不能滿足實(shí)際的需要。實(shí)際使用的分詞系統(tǒng)，都是把機(jī)械分詞作為一種初分手段，還需通過利用各 種其它的語言信息來進(jìn)一步提高切分的準(zhǔn)確率。

一種方法是改進(jìn)掃描方式，稱為特征掃描或標(biāo)志切分，優(yōu)先在待分析字符串中識別和切分出一些 帶有明顯特征的詞，以這些詞作為斷點(diǎn)，可將原字符串分為較小的串再來進(jìn)機(jī)械分詞，從而減少匹配的錯誤率。另一種方法是將分詞和詞類標(biāo)注結(jié)合起來，利用豐富 的詞類信息對分詞決策提供幫助，并且在標(biāo)注過程中又反過來對分詞結(jié)果進(jìn)行檢驗(yàn)、調(diào)整，從而極大地提高切分的準(zhǔn)確率。

對于機(jī)械分詞方法，可以建立一個一般的模型，在這方面有專業(yè)的學(xué)術(shù)論文，這里不做詳細(xì)論述。

2、基于理解的分詞方法
這種分詞方法是通過讓計(jì)算機(jī)模擬人對句子的理解，達(dá)到識別詞的效果。其基本思想就是在分詞的同時進(jìn)行句法、語義分析，利用句法信息和語義信息來處理歧義 現(xiàn)象。它通常包括三個部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義 進(jìn)行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機(jī)器可 直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗(yàn)階段。

3、基于統(tǒng)計(jì)的分詞方法
從形式上看，詞是穩(wěn)定的字的組 合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反映成詞的可信度?？梢詫φZ料中相鄰 共現(xiàn)的各個字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們的互現(xiàn)信息。定義兩個字的互現(xiàn)信息，計(jì)算兩個漢字X、Y的相鄰共現(xiàn)概率?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊 密程度。當(dāng)緊密程度高于某一個閾值時，便可認(rèn)為此字組可能構(gòu)成了一個詞。這種方法只需對語料中的字組頻度進(jìn)行統(tǒng)計(jì)，不需要切分詞典，因而又叫做無詞典分詞 法或統(tǒng)計(jì)取詞方法。但這種方法也有一定的局限性，會經(jīng)常抽出一些共現(xiàn)頻度高、但并不是詞的常用字組，例如“這一”、“之一”、“有的”、“我的”、“許多 的”等，并且對常用詞的識別精度差，時空開銷大。實(shí)際應(yīng)用的統(tǒng)計(jì)分詞系統(tǒng)都要使用一部基本的分詞詞典（常用詞詞典）進(jìn)行串匹配分詞，同時使用統(tǒng)計(jì)方法識別 一些新的詞，即將串頻統(tǒng)計(jì)和串匹配結(jié)合起來，既發(fā)揮匹配分詞切分速度快、效率高的特點(diǎn)，又利用了無詞典分詞結(jié)合上下文識別生詞、自動消除歧義的優(yōu)點(diǎn)。

到底哪種分詞算法的準(zhǔn)確度更高，目前并無定論。對于任何一個成熟的分詞系統(tǒng)來說，不可能單獨(dú)依靠某一種算法來實(shí)現(xiàn)，都需要綜合不同的算法。筆者了解，海 量科技的分詞算法就采用“復(fù)方分詞法”，所謂復(fù)方，相當(dāng)于用中藥中的復(fù)方概念，即用不同的藥才綜合起來去醫(yī)治疾病，同樣，對于中文詞的識別，需要多種算法 來處理不同的問題。

4、基于規(guī)則的分詞方法
基于規(guī)則的分詞方法，這種方法又叫做機(jī)械分詞方法,它是按照一定的策略將待分析的漢字串與一個“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配,若在詞典中找到某個字 符串,則匹配成功(識別出一個詞) 。常用的方法：最小匹配算法(Minimum Matching)，正向（逆向）最大匹配法(Maximum Matching)，逐字匹配算法,神經(jīng)網(wǎng)絡(luò)法、聯(lián)想一回溯法，基于N-最短路徑分詞算法,以及可以相互組合，例如,可以將正向最大匹配方法和逆向最大匹 配方法結(jié)合起來構(gòu)成雙向匹配法等。目前機(jī)械式分詞占主流地位的是正向最大匹配法和逆向最大匹配法。

最小匹配算法
在所有的分詞算法中，最早研究的是最小匹配算法(Minimum Matching)，該算法從待比較字符串左邊開始比較，先取前兩個字符組成的字段與詞典中的詞進(jìn)行比較，如果詞典中有該詞，則分出此詞，繼續(xù)從第三個字 符開始取兩個字符組成的字段進(jìn)行比較，如果沒有匹配到，則取前3個字符串組成的字段進(jìn)行比較，依次類推，直到取的字符串的長度等于預(yù)先設(shè)定的閾值，如果還 沒有匹配成功，則從待處理字串的第二個字符開始比較，如此循環(huán)。

例如，“如果還沒有匹配成功”，取出左邊兩個字 組成的字段與詞典進(jìn)行比較，分出“如果”；再從“還”開始，取“還沒”，字典中沒有此詞，繼續(xù)取“還沒有”，依次取到字段“還沒有匹配”(假設(shè)閾值為 5)，然后從“沒”開始，取“沒有”，如此循環(huán)直到字符串末尾為止。這種方法的優(yōu)點(diǎn)是速度快，但是準(zhǔn)確率卻不是很高，比如待處理字符串為“中華人民共和 國”，此匹配算法分出的結(jié)果為：中華、人民、共和國，因此該方法基本上已經(jīng)不被采用 。

最大匹配算法
基于字符串的最大匹配，這種方法現(xiàn)在仍比較常用。最大匹配(Maximum Matching)分為正向和逆向兩種最大匹配，正向匹配的基本思想是：假設(shè)詞典中最大詞條所含的漢字個數(shù)為n個，取待處理字符串的前n個字作為匹配字 段，查找分詞詞典。若詞典中含有該詞，則匹配成功，分出該詞，然后從被比較字符串的n+1處開始再取n個字組成的字段重新在詞典中匹配；如果沒有匹配成 功，則將這n個字組成的字段的最后一位剔除，用剩下的n一1個字組成的字段在詞典中進(jìn)行匹配，如此進(jìn)行下去，直到切分成功為止。

例 如，待處理字符串為“漢字多為表意文字”，取字符串“漢語多為表”(假設(shè)比較的步長為5，本文步長step都取5)與詞典進(jìn)行比較，沒有與之對應(yīng)的詞，去 除“表”字，用字段“漢語多為”進(jìn)行匹配，直至匹配到“漢語”為至，再取字符串“多為表意”，循環(huán)到切分出“文字”一詞。目前，正向最大匹配方法作為一種 基本的方法已被肯定下來，但是由于錯誤比較大，一般不單獨(dú)使用。如字符串“處理機(jī)器發(fā)生的故障”，在正向最大匹配方法中會出現(xiàn)歧義切分，該字符串被分為： 處理機(jī)、發(fā)生、故障，但是使用逆向匹配就能得到有效的切分。

逆向最大匹配RMM(Reverse Directional Maximum Matching Method)的分詞原理和過程與正向最大匹配相似，區(qū)別在于前者從文章或者句子(字串)的末尾開始切分，若不成功則減去最前面的一個字。比如對于字符串 “處理機(jī)器發(fā)生的故障”，第一步，從字串的右邊取長度以步長為單位的字段“發(fā)生的故障”在詞典中進(jìn)行匹配，匹配不成功，再取字段“生的故障”進(jìn)行匹配，依 次匹配，直到分出“故障”一詞，最終使用RMM方法切分的結(jié)果為：故障、發(fā)生、機(jī)器、處理。該方法要求配備逆序詞典。

一般來說根據(jù)漢語詞匯構(gòu)成的特點(diǎn)，從理論上說明了逆向匹配的精確度高于正向匹配，漢語語句的特點(diǎn)一般中心語偏后。有研究數(shù)據(jù),單純使用正向最大匹配的錯誤 率為1/ 169 ,單純使用逆向最大匹配的錯誤率為1/245。實(shí)際應(yīng)用中可以從下面幾方面改進(jìn)，同時采取幾種分詞算法，來提高正確率;改進(jìn)掃描方式，稱為特征掃描或標(biāo)志 切分,優(yōu)先在待分析字符串中識別和切分出一些帶有明顯特征的詞,以這些詞作為斷點(diǎn),可將原字符串分為較小的串再來進(jìn)機(jī)械分詞，從而減少匹配的錯誤率等。

逐字匹配算法
逐字匹配算法，基于TRIE索引樹（又稱單詞索引樹 http://baike.baidu.com/view/1436495.htm）的逐字匹配算法,是建立在樹型詞典機(jī)制上，匹配的過程是從索引樹的根結(jié)點(diǎn)依次同步匹配待查詞中的每個字，可以看成是對樹 某一分枝的遍歷。因此，采用該算法的分詞速度較快，但樹的構(gòu)造和維護(hù)比較復(fù)雜。一種改進(jìn)的算法是和最大匹配算法相結(jié)合，吸取最大匹配算法詞典結(jié)構(gòu)簡單、 TRIE索引樹算法查詢速度快的優(yōu)點(diǎn)。因此詞典結(jié)構(gòu)和最大匹配詞典構(gòu)造機(jī)制相似，區(qū)別在于詞典正文前增加了多級索引。匹配過程類似TRIE索引樹進(jìn)行逐字 匹配，在性能上和TRIE索引樹相近。

神經(jīng)網(wǎng)絡(luò)分詞算法
神經(jīng)網(wǎng)絡(luò)分詞算法，尹峰等提出了以神經(jīng)網(wǎng)絡(luò)理論(BP模型)為基礎(chǔ)的漢語分詞模型,為漢語分詞研究開辟了新途徑。在實(shí)用中,BP算法存在收斂速度慢、易陷 入局部最小等缺點(diǎn),嚴(yán)重妨礙了分詞速度。一種改進(jìn)算法采用Levenbery2Marquart 算法來加速收斂速度,加快了收斂速度利用神經(jīng)網(wǎng)絡(luò)的基本原理進(jìn)行分詞。

聯(lián)想—回溯法
聯(lián)想—回溯法(Association－Backtracking Method，簡稱 AB 法)。這種方法要求建立三個知識庫——特征詞詞庫、實(shí)詞詞庫和規(guī)則庫。首先將待切分的漢字字符串序列按特征詞詞庫分割為若干子串，子串可以是詞，也可以是 由幾個詞組合而成的詞群；然后，再利用實(shí)詞詞庫和規(guī)則庫將詞群再細(xì)分為詞。切詞時，要利用一定的語法知識，建立聯(lián)想機(jī)制和回溯機(jī)制。聯(lián)想機(jī)制由聯(lián)想網(wǎng)絡(luò)和 聯(lián)想推理構(gòu)成，聯(lián)想網(wǎng)絡(luò)描述每個虛詞的構(gòu)詞能力，聯(lián)想推理利用相應(yīng)的聯(lián)想網(wǎng)絡(luò)來判定所描述的虛詞究竟是單獨(dú)成詞還是作為其他詞中的構(gòu)詞成分?；厮輽C(jī)制主要 用于處理歧義句子的切分。聯(lián)想—回溯法雖然增加了算法的時間復(fù)雜度和空間復(fù)雜度，但這種方法的切詞正確率較高，是一種行之有效的方法。

N-最段路徑分詞算法
基于N-最短路徑分詞算法，其基本思想是根據(jù)詞典，找出字串中所有可能的詞，構(gòu)造詞語切分有向無環(huán)圖。每個詞對應(yīng)圖中的一條有向邊，并賦給相應(yīng)的邊長(權(quán) 值)。然后針對該切分圖，在起點(diǎn)到終點(diǎn)的所有路徑中，求出長度值按嚴(yán)格升序排列(任何兩個不同位置上的值一定不等，下同)依次為第1，第2，…，第 i，…，第N的路徑集合作為相應(yīng)的粗分結(jié)果集。如果兩條或兩條以上路徑長度相等，那么他們的長度并列第 i，都要列入粗分結(jié)果集，而且不影響其他路徑的排列序號，最后的粗分結(jié)果集合大小大于或等于N。N一最短路徑方法實(shí)際上是最短路徑方法和全切分的有機(jī)結(jié) 合。該方法的出發(fā)點(diǎn)是盡量減少切分出來的詞數(shù)，這和最短路徑分詞方法是完全一致的；同時又要盡可能的包含最終結(jié)果，這和全切分的思想是共通的。通過這種綜 合，一方面避免了最短路徑分詞方法大量舍棄正 確結(jié)果的可能，另一方面又大大解決了全切分搜索空間過大，運(yùn)行效率差的弊端。N一最短路徑方法相對的不足就是粗分結(jié)果不唯一 ，后續(xù)過程需要處理多個粗分結(jié)果。 但是 ，對于預(yù)處理過程來講，粗分結(jié)果的高召回率至關(guān)重要。因?yàn)榈驼倩芈示鸵馕吨鴽]有辦法 再作后續(xù)的補(bǔ)救措施。預(yù)處理一旦出錯，后續(xù)處理只能是一錯再錯 ，基本上得不到正確的最終 結(jié)果。而少量的粗分結(jié)果對后續(xù)過程的運(yùn)行效率影響不會太大，后續(xù)處理可以進(jìn)一步優(yōu)選排 錯，如詞性標(biāo)注、句法分析等。

除上面之外，還有基于詞頻統(tǒng)計(jì)的切詞法， 基于期望的切詞法，有窮多級列舉法等。

分詞中的難題
有了成熟的分詞算法，是否就能容易的解決中文分詞的問題呢？事實(shí)遠(yuǎn)非如此。中文是一種十分復(fù)雜的語言，讓計(jì)算機(jī)理解中文語言更是困難。在中文分詞過程中，有兩大難題一直沒有完全突破。

1、歧義識別
歧義是指同樣的一句話，可能有兩種或者更多的切分方法。例如：表面的，因?yàn)椤氨砻妗焙汀懊娴摹倍际窃~，那么這個短語就可以分成“表面 的”和“表 面的”。這種稱為交叉歧義。像這種交叉歧義十分常見，前面舉的“和服”的例子，其實(shí)就是因?yàn)榻徊嫫缌x引起的錯誤?！盎瘖y和服裝”可以分成“化妝 和 服裝”或者“化妝 和服 裝”。由于沒有人的知識去理解，計(jì)算機(jī)很難知道到底哪個方案正確。

交叉歧義相對組合歧義來說是還算比較容易處 理，組合歧義就必需根據(jù)整個句子來判斷了。例如，在句子“這個門把手壞了”中，“把手”是個詞，但在句子“請把手拿開”中，“把手”就不是一個詞；在句子 “將軍任命了一名中將”中，“中將”是個詞，但在句子“產(chǎn)量三年中將增長兩倍”中，“中將”就不再是詞。這些詞計(jì)算機(jī)又如何去識別?

如 果交叉歧義和組合歧義計(jì)算機(jī)都能解決的話，在歧義中還有一個難題，是真歧義。真歧義意思是給出一句話，由人去判斷也不知道哪個應(yīng)該是詞，哪個應(yīng)該不是詞。 例如：“乒乓球拍賣完了”，可以切分成“乒乓 球拍 賣 完 了”、也可切分成“乒乓球 拍賣 完 了”，如果沒有上下文其他的句子，恐怕誰也不知道“拍賣”在這里算不算一個詞。

2、新詞識別
新詞，專業(yè)術(shù)語稱為未登 錄詞。也就是那些在字典中都沒有收錄過，但又確實(shí)能稱為詞的那些詞。最典型的是人名，人可以很容易理解句子“王軍虎去廣州了”中，“王軍虎”是個詞，因?yàn)?是一個人的名字，但要是讓計(jì)算機(jī)去識別就困難了。如果把“王軍虎”做為一個詞收錄到字典中去，全世界有那么多名字，而且每時每刻都有新增的人名，收錄這些 人名本身就是一項(xiàng)巨大的工程。即使這項(xiàng)工作可以完成，還是會存在問題，例如：在句子“王軍虎頭虎腦的”中，“王軍虎”還能不能算詞？

新詞中除了人名以外，還有機(jī)構(gòu)名、地名、產(chǎn)品名、商標(biāo)名、簡稱、省略語等都是很難處理的問題，而且這些又正好是人們經(jīng)常使用的詞，因此對于搜索引擎來說，分詞系統(tǒng)中的新詞識別十分重要。目前新詞識別準(zhǔn)確率已經(jīng)成為評價(jià)一個分詞系統(tǒng)好壞的重要標(biāo)志之一。

中文分詞的應(yīng)用
目前在自然語言處理技術(shù)中，中文處理技術(shù)比西文處理技術(shù)要落后很大一段距離，許多西文的處理方法中文不能直接采用，就是因?yàn)橹形谋匦栌蟹衷~這道工序。中文分詞是其他中文信息處理的基礎(chǔ)，搜索引擎只是中文分詞的一個應(yīng)用。其他的比如機(jī)器翻譯（MT）、語音合成、自動分類、自動摘要、自動校對等等，都需要用到分詞。因?yàn)橹形男枰衷~，可能會影響一些研究，但同時也為一些企業(yè)帶來機(jī)會，因?yàn)閲獾挠?jì)算機(jī)處理技術(shù)要想進(jìn)入中國市場，首先也是要解決中文分詞問題。在中文研究方面，相比外國人來說，中國人有十分明顯的優(yōu)勢。

分詞準(zhǔn)確性對搜索引擎來說十分重要，但如果分詞速度太慢，即使準(zhǔn)確性再高，對于搜索引擎來說也是不可用的，因?yàn)樗阉饕嫘枰幚頂?shù)以億計(jì)的網(wǎng)頁，如果分 詞耗用的時間過長，會嚴(yán)重影響搜索引擎內(nèi)容更新的速度。因此對于搜索引擎來說，分詞的準(zhǔn)確性和速度，二者都需要達(dá)到很高的要求。目前研究中文分詞的大多是科研院校，清華、北大、中科院、北京語言學(xué)院、東北大學(xué)、IBM研究院、微軟中國研究院等都有自己的研究隊(duì)伍，而真正專業(yè)研究中文分詞的商業(yè)公司除了海量科技以外，幾乎沒有了。科研院校研究的技術(shù)，大部分不能很快產(chǎn)品化，而一個專業(yè)公司的力量畢竟有限，看來中文分詞技術(shù)要想更好的服務(wù)于更多的產(chǎn)品，還有很長一段路。

轉(zhuǎn)載請注明：終小南 ? 中文分詞算法總結(jié)