一種組合型中文分詞方法

一種組合型中文分詞方法鄭曉剛;韓立新;白書奎;曾曉勤【摘要】Inthispaper,wedesignandimplementacombination-typewordsegmentationmechanism;thedictionary-basedlargesttwo-waymatching,thewordtagging-basedChinesewordsegmentationmethodandthehiddenMarkovsegmentationapproach.Bycomparingtheexperimentalresults,wefindthatthiscombination-typewordsegmentationmeanscanbettersolvetheChineseambiguityanddiscoverthenewword.%設計一種組合型的分詞機制:基于字典的雙向最大匹配，基于字標注的中文分詞方法和隱馬爾科夫的分詞方式.通過實驗的結果比較,表明該種組合型的分詞方法能夠較好地解決中文歧義并發(fā)現(xiàn)新的登錄詞.【期刊名稱】《計算機應用與軟件》【年(卷)，期】2012(029)007【總頁數(shù)】4頁(P26-28,39)【關鍵詞】中文信息處理;中文自動分詞;組合型分詞【作者】鄭曉剛;韓立新;白書奎;曾曉勤【作者單位】河海大學計算機與信息學院江蘇南京211100;河海大學計算機與信息學院江蘇南京211100;河海大學計算機與信息學院江蘇南京211100;河海大學計算機與信息學院江蘇南京211100【正文語種】中文【中圖分類】TP3010引言分詞對于搜索引擎有著很大的作用，是文本挖掘的基礎，可以幫助程序自動識別語句的含義，以達到搜索結果的高度匹配，分詞的質量直接影響了搜索結果的精確度。中文和英文的分詞不一樣，在英文中每個詞是用空格分開的，不需要進行額外的分詞處理，而在中文詞中，每個句子中的詞是沒有空格的，需要用分詞來處理。比較流行的方法有三個大類［1］：1）基于字符串匹配的分詞方法；2）基于統(tǒng)計的分詞方法；3）基于理解的分詞方法。目前這些方法都已經很成熟，但是成熟并不代表著能夠很好地解決中文分詞的問題。歧義的判斷和新詞的識別是中文分詞沒有完全突破的問題，也是判斷一個中文分詞系統(tǒng)好壞的重要標準。為了降低分詞過程中歧義出現(xiàn)的概率和增加發(fā)現(xiàn)新詞的機率，本文設計了一種組合分詞方法。一個句子通過正向最大匹配和反向最大匹配得到分詞的結果。如果得到的結果一致，那么說明這個句子沒有歧義。如果得到的結果不一致，那么可以認為在兩種匹配結果中，只有一種結果是正確的，需要通過學習來判斷哪種方式得到的結果是正確的。為了增加新詞發(fā)現(xiàn)的概率，本文通過預處理，使得隱馬爾科夫的假設獨立性對分詞的影響進一步降低，分詞結果更加準確。1傳統(tǒng)的分詞方法［2］1.1最大匹配法分詞最大匹配法分詞是基于字符串匹配的常用解決方案。這種方法分詞比較簡單、便捷，但是無疑存在明顯的缺陷，就是可能造成歧義和不能識別新詞?；谧址ヅ涞姆衷~方法首先要有一個事先準備好的字典，如果在分詞的過程中遇到一個字典中沒有的詞，那么就不能正確切分出來。如果從正向開始來匹配，當處理〃他們在研究生活”這句話，字典里有〃研究”、“研究生”、“生活”這些常用詞時，該句子會被切分為〃研究生|活”，這就是分詞里的歧義現(xiàn)象。1.2基于統(tǒng)計的分詞基于統(tǒng)計的分詞方法主要應用的是統(tǒng)計量，統(tǒng)計模型［3,4］有:互信息、N元文法模型、神經網絡模型［6］和隱Markov模型(HMM)模型等。這些統(tǒng)計模型主要利用詞與詞的聯(lián)合出現(xiàn)概率作為分詞的依據(jù)。其原理是從形式上看，詞是穩(wěn)定的字的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)越多，就越有可能構成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好地反映成詞的可信度?？梢詫φZ料中相鄰共現(xiàn)的各個字的組合的頻度進行統(tǒng)計，計算它們的互現(xiàn)信息?；诮y(tǒng)計的分詞方法的優(yōu)點是：(1)不受待處理文本的領域限制；(2)不需要一個機器可讀詞典。缺點是：(1)需要大量的訓練文本，用以建立模型的參數(shù)；(2)該方法的計算量非常大；(3)分詞精度與訓練文本的選擇有關。2組合型分詞方法正如前面所講的傳統(tǒng)的分詞方法都有各自的優(yōu)點和缺點，仔細分析可以發(fā)現(xiàn)基于統(tǒng)計的分詞的方法可以克服最大匹配法分詞不能發(fā)現(xiàn)新詞，而最大匹配法分詞同樣可以解決基于統(tǒng)計的分詞中計算量非常大和分詞精度與訓練文本的關系過于密切的缺點。正是基于這個想法，本文嘗試用組合分詞來設計一個新型的分詞系統(tǒng)，在這個系統(tǒng)中，綜合了最大匹配法和統(tǒng)計模型中的隱馬爾科夫方法，使在保證高效的前提下能夠準確找到新詞和解決可能出現(xiàn)的歧義。在本文中最后才采用隱馬爾科夫［5］方法，是因為隱馬爾科夫分詞是基于一個假設:一個字是不是一個詞的一部分只與它前一個字有關，和別的字沒關。我們可以發(fā)現(xiàn)這個假設有個缺陷就是人為地認定字與字之間的獨立性，這是不太符合邏輯的。好比我們用隱馬爾科夫的經典例子:天氣情況，來說明這個假設的不合理性。假設由晴天轉向陰天的概率是0.3，意思就是如果今天是晴天，那么明天是陰天的概率是0.3，但是如果按照自己的思維來考慮，如果已經連續(xù)一個月是晴天了，那么明天是陰天的概率肯定要高于0.3，而且連續(xù)的晴天天數(shù)越長，明天是陰天的概率越高。在分詞中也一樣會出現(xiàn)這樣的情況，所以為了盡量減少或者避免這種情況的發(fā)生，本文最后用隱馬爾科夫來切分比較短的句子。2.1組合型分詞方法的主要步驟首先通過正向最大匹配和反向最大匹配對輸入的文本進行分詞，然后對比兩種方法的分詞結果，把切分不一致的部分（歧義出現(xiàn)的情況）放入預處理的隊列中，而把切分一致的部分加入用于存放該文本中詞的詞庫中，若發(fā)現(xiàn)有連續(xù)2個及2個以上的單個詞組成的字符串時，認定這些字符串可能是一個新詞，就把它們加入存放可能是新詞的詞庫中。接著結合語料庫中詞之間的組合概率，在正向和反向切分不一致的詞中選擇出現(xiàn)概率大的切分方式，這樣就解決了歧義問題。然后對連續(xù)的單個詞組成的字符串進行處理，首先如果這個字符串在文中出現(xiàn)多次，并且結合預料庫中詞出現(xiàn)的概率，算出該字符串可能是一個新詞的概率，如果概率大于設定的閾值，則認為該字符串是一個新詞，然后對文中只出現(xiàn)一次的字符串用隱馬爾科夫方法進行分詞，把得到的新詞提出來。圖1是組合分詞的模型示意圖。圖1組合分詞模型示意圖2.2雙向最大匹配的實現(xiàn)為了能夠對句子進行分詞，我們需要構造一個詞典。這里用的詞典不是現(xiàn)成的，而是根據(jù)語料庫得到的，把1998年1月份《人民日報》切分標注語料庫里的詞條構成一定的數(shù)據(jù)結構。通常情況下有平衡二叉樹和哈希表兩種構造方法。平衡二叉樹的特點是增加和刪除詞條比較方便，哈希表的特點是查找速度快。這里采用的是平衡二叉樹來構造詞典，構造好的詞典有49194個詞，高度是16，也就是一個詞最多通過16次比較就能得到是不是在詞典中。2.2.1正向最大匹配方法基于正向最大匹配方法是一種常用的分詞方法，在各個搜索引擎中得到廣泛的應用。正向最大匹配方法的算法思想是：求出用于分詞的詞典里的最長的詞的詞長，長度標為n。從一個句子的左邊開始截取一個長度為n的字符串，用來和詞典中的詞進行依次比較。如果找到這樣的詞，就匹配成功，將該詞從句子中切分出來。⑷如果沒找到這樣的詞，則把該字符串的最后邊的字截去，用剩下的n-1字長的字符串繼續(xù)從詞典中進行查找，查找成功則從句子中切分出來，不成功就繼續(xù)截去最后邊的字用剩下的n-2字長的字符串進行繼續(xù)查找匹配。(5)當n=1時說明詞典中沒有這樣的詞，舍去，從下一個字重新開始正向最大匹配查找，直到整個句子切分完成。從上述的方法發(fā)現(xiàn)正向最大匹配方法原理很簡單，也便于實現(xiàn)。但是在判別歧義上往往導致切分的錯誤。據(jù)資料統(tǒng)計，正向最大匹配方法的錯誤切分率是1/169。2.2.2反向最大匹配方法反向最大匹配方法也是很常用的分詞方法，它和正向最大匹配方法的思想很類似，只不過正向最大匹配方法是從句子的左邊開始匹配，不成功時首先截去字符串的最右邊的字，而反向最大匹配是從句子的右邊開始匹配，不成功時首先截取字符串的最左邊的字。據(jù)統(tǒng)計，反向最大匹配方法的錯誤切分率是1/245?？梢钥闯鲞@比正向最大匹配方法的準確率有了提高，但是問題仍然是歧義的判斷和新詞的識別沒能完全突破?，F(xiàn)在我們已經知道了正向最大匹配的出錯概率是1/169和反向最大匹配的出錯概率是1/245。那么我們可以認為如果正向最大匹配和反向最大匹配的切分結果是—致的，那么這個句子就沒有歧義，可以正確切分出里面的詞。如果正向最大匹配和反向最大匹配切分的結果不一致，那么認為有一種切分是正確的，因為對一個句子來說，兩種方法同時出錯的概率太低了，那么在兩種方法切分不一致的情況下如何選擇其中正確的方法是我們接下來要做的工作。比如一個很常用的句子〃華東地區(qū)最大的鞋帽和服裝市場”，正向最大匹配的結果是〃華東地區(qū)|最大|的|鞋帽|和服|裝|市場|”，反向最大匹配的結果是“|華東地區(qū)|最大|的|鞋帽|和|服裝|市場〃。我們過濾掉切分一致的詞剩下”和服裝〃這個字符串是有歧義的部分。我們知道”和|服裝“這種切分是正確的，但是計算機不能這么判讀，它要做的是判讀”和|服裝〃和”和服|裝〃這兩種切分哪種概率大，哪種就是正確的切分方式。2.3分詞中歧義的消除在本文中我們引入字標注的方法，為了便于方便，我們規(guī)定每個字最多只有四個構詞位置:即詞首(B)，詞中(M)，詞尾(E)和單獨成詞(S)。那么〃祝偉大的祖國繁榮昌盛”這句話就可逐字標注為〃祝/S偉/B大/E的/S祖/B國/E繁/B榮/M昌/M盛/E”。通過對語料庫中詞的訓練，得到每個字作詞頭，詞中，詞尾和單獨成詞的概率。假設A，B，C為三個漢字，對“ABC”有“A|BC”和“AB|C”這2種切分方法，下面我們用偽代碼來判斷哪種方法是最有可能出現(xiàn)的。2.4識別新詞我們采用2次處理來識別新詞，第1次是根據(jù)統(tǒng)計的方法來得到新詞，第2次是用隱馬爾科夫模型來進行標注，得到新詞。2.4.1統(tǒng)計新詞的方法如果單純地對本文用統(tǒng)計方法來分詞，那么需要處理的數(shù)據(jù)量很大，而且準確率還有待于提高。在本文中，統(tǒng)計得到新詞的范圍僅限于單個漢字組成的連續(xù)的字符串中。步驟如下：步驟1待處理的字符串按長度由小到大排序。步驟2提取第一個字符串和后續(xù)的字符串進行比較，若后面的字符串等于或者包含第一個字符串則把第一個字符串提出，否則提取第二個字符串進行類似的比較，直到所有的字符串都比較過。步驟3在步驟2中，若字符串滿足第一條件，則結合語料庫計算出這個字符串。如果可以組成一個詞的概率是多少，如果概率大于預設的閾值則認定是一個新詞，否則過濾。通過上述的處理，存放字符串的數(shù)組的規(guī)模進一步縮小，剩下的字符串都是在文中僅出現(xiàn)一次的，接下來用隱馬爾科夫來對這些字符串作進一步的切分。2.4.2隱馬爾科夫模型隱馬爾科夫模型是一個5元組，M={Q,￡,P,A,n},其中Q={s1,s2，…，sn}是所有狀態(tài)的集合，￡={。1,。2,...,on}是所有的觀察序列的集合，P={pi,j}nxn,pi,j是概率轉移矩陣，即是狀態(tài)從si到sj的轉移概率，A={ai,j}nxm,ai,j是發(fā)現(xiàn)概率矩陣，即是狀態(tài)si觀察到oj的概率，n是初始向量的概率。在隱馬爾科夫模型中，如果第i個狀態(tài)出現(xiàn)的概率與它前面的i-1個狀態(tài)有關，那么這個隱馬爾科夫模型被稱為i-1階隱馬爾科夫模型。在這里為了方便，我們只認為一個詞的出現(xiàn)只與這個詞的前一個詞有關，就是1階隱馬爾科夫模型。本文中狀態(tài)集合是{B,M,E,S},觀察序列的集合是所要處理的漢字。通過最大匹配和統(tǒng)計方法處理后，現(xiàn)在剩下的句子都很短，一般以2個、3個字居多，4個字的其次，超過5個字的句子就很少了。隱馬爾科夫模型中有狀態(tài)集合和觀察序列的集合，本文中狀態(tài)集合是詞首(B),詞中(M),詞尾(E)和單獨成詞(S)這四個狀態(tài)，觀察序列是給出的句子中的漢字組成，分詞的算法是用Viterbi[5]的算法實現(xiàn)的。Viterbi的算法步驟如下：步驟1計算第一個字的概率:狀態(tài)的初始概率乘以隱藏狀態(tài)到觀察狀態(tài)的條件概率。步驟2計算第一個字以后的概率，首先從前一個字的每個狀態(tài)轉移到當前狀態(tài)的概率的最大值，然后乘以隱藏狀態(tài)到觀察狀態(tài)的條件概率。步驟3找到最后一個字呈現(xiàn)哪種狀態(tài)的概率最大。步驟4用動態(tài)規(guī)劃的方法逆推回去各個字出現(xiàn)什么狀態(tài)概率最大。雖然選擇訓練的語料數(shù)量是有限的，但是基本上涵蓋了常用的詞語，當在進行分詞測試的時候出現(xiàn)了個別語料庫中沒有的字時，我們認定這個字是一個未收入的詞的組成部分，于是賦予它作為詞首、詞中、詞尾的概率各為1/3，而單獨成詞的概率為0，通過實驗結果發(fā)現(xiàn)這樣可以很好地發(fā)現(xiàn)新詞。3實驗結果本文對上述系統(tǒng)的實現(xiàn)是基于Java和MyEclipse的開發(fā)工具。本文所用到的訓練語料庫是1998年1月份《人民日報》切分標注語料，刪除料中的復合專名標記、詞類標記，只留下詞語切分信息。召回率、準確率分別采用如下公式：本系統(tǒng)的召回率高達95%，是因為等待識別的新詞基本上是文章中所有的新詞。在消除歧義上，通過實驗結果發(fā)現(xiàn)本系統(tǒng)對句子進行切分的準確率為1/326，高于正向最大匹配的1/169和反向最大匹配的1/245。在新詞的識別中，用統(tǒng)計的方法得到新詞的準確率為90%。傳統(tǒng)的統(tǒng)計分詞的準確率是75%。接下來在用隱馬爾科夫識別新詞中，效果見表1。表12種HMM的對比圖長度為2的詞_長度為3的詞_長度為4的詞_長度為5的詞本文中_HMM交攵_果91.5%83%72%63%傳統(tǒng)的_HMM交攵—果81%71%52.5%41.6%通過實驗的結果發(fā)現(xiàn)分詞過程中歧義的出現(xiàn)概率進一步降低，是因為分詞在出現(xiàn)歧義時可以通過學習的方法來選擇正確的切分形式。新詞發(fā)現(xiàn)的效果也很理想，主要是因為大幅減少了接受統(tǒng)計分詞語料的復雜度，和降低了隱馬爾科夫的假設獨立性對于分詞結果的影響。結果說明這種分詞系統(tǒng)能夠很好地解決句子的歧義和識別新詞，具有一定的實用性。4結語對中文分詞方法的研究已經進行了很多年，但是至今仍然沒有一個完全令人滿意的分詞方法。為了能夠更好地處理分詞中存在的歧義現(xiàn)象，并識