中文快速分詞方法

一種基于自動(dòng)機(jī)的分詞方法摘要本文介紹一種簡潔有效的快速分詞方法，并通過理論分析和實(shí)驗(yàn)對比說明幾種分詞方法的效率差異，以說明我們所提出的方法的有效性。關(guān)鍵詞：中文信息處理，分詞，順序查找，二分查找，自動(dòng)機(jī)，二叉樹分類號(hào)：TP文獻(xiàn)標(biāo)識(shí)碼1引言西方語言在語句（或從句）內(nèi)詞匯之間存在分割符（空格），而漢語的詞匯在語句中是連續(xù)排列的。因此，漢語詞匯的切分（分詞）在中文信息處理的許多應(yīng)用領(lǐng)域，如機(jī)器翻譯、文獻(xiàn)檢索、文獻(xiàn)分類、文獻(xiàn)過濾、以及詞頻統(tǒng)計(jì)等，是非常重要的第一步。自動(dòng)分詞是基于字符串匹配的原理進(jìn)行的。迄今為止，已經(jīng)有許多文獻(xiàn)對各種分詞方法進(jìn)行探討，其著重點(diǎn)或?yàn)榉衷~的速度方面，或?yàn)榉衷~的精度方面以及分詞的規(guī)范。本文主要探討分詞的速度問題，通過實(shí)驗(yàn)對比和理論分析，說明我們所提出的算法是有效的。目前人們所提出的分詞方法，在考慮效率問題時(shí)，通常在詞典的組織方面進(jìn)行某種調(diào)整，以適應(yīng)相應(yīng)的算法，如最大匹配法、最小匹配法、逐詞遍歷法、以及最佳匹配法等。這些方法中，或?qū)⒃~典按詞條長度排序或按詞頻排序，其目的在于協(xié)調(diào)算法與數(shù)據(jù)結(jié)構(gòu)，使之效率最高?？陀^地說，它們都在一定程度上提高了分詞的效率。本文所介紹的是基于詞典的最大向前匹配方法。而在數(shù)據(jù)結(jié)構(gòu)方面，我們則是將詞典組織成自動(dòng)機(jī)形式。2數(shù)據(jù)結(jié)構(gòu)與算法文獻(xiàn)［1，2，3］給出了三種基于詞典的最大向前匹配方法的分詞算法（相應(yīng)于文獻(xiàn)編號(hào)，我們以后分別稱其對應(yīng)的算法為算法1、算法2、和算法3）。我們可以把算法1看作是原始算法，把算法2看作是算法1的改進(jìn)，而算法3則是算法2的進(jìn)一步優(yōu)化。在詞典的組織方面，算法2和算法3是按照正常的詞典排序（即按漢字的機(jī)器內(nèi)碼表示排序），并輔以詞條的首字索引，以標(biāo)明以該字起始詞條在詞典中的首記錄。例如，在一般的詞典中，詞條的形式如下圖所示：圖1：一般分詞詞典的形式啊啊哈啊呀啊喲阿阿爸阿斗阿爾巴尼亞阿飛阿富汗在實(shí)際存儲(chǔ)時(shí)，可以在詞尾部分刪除首字。這樣做不僅節(jié)省了存儲(chǔ)空間，更重要的是縮短了字符串比較的長度。算法2和算法3對首字的檢索都是基于哈希算法；算法2對于詞尾部分采用線性搜索，而算法3則采用二分搜索。采用何種搜索算法應(yīng)根據(jù)所用詞典中每個(gè)首字下的詞條數(shù)目確定，一般詞條數(shù)較小時(shí)，二者無明顯差異。這是由這兩種算法本身的特性決定的。實(shí)際詞典中許多首字下的詞條數(shù)目很大，因此，采用二分搜索法較優(yōu)。我們的實(shí)驗(yàn)結(jié)果也證實(shí)了這一點(diǎn)。算法2和算法3在詞典的組織方面是一致的，即如同普通詞典一樣，按照漢字的內(nèi)碼遞增排序，并以詞條的首字建立哈希索引。我們可以將同一首字下的所有詞條組織成一個(gè)子表結(jié)構(gòu)，如下圖所示。圖2：詞典的邏輯結(jié)構(gòu)假設(shè)：源文本source_text=“中華人民共和國成立于1949年?！狈衷~結(jié)果=“中華人民共和國/成立/于/1949/年/?！狈衷~過程為：從源文本source_text中取首字head_word=“中”，并設(shè)置已切分詞匯segmented_word=head_word；從索引中查找該首字。若未找到，則暫將該字作為單字詞輸出；否則，將其后續(xù)字符加入臨時(shí)變量tail_word=“華”；在以“中”為首字的子表中查找包含tail_word的詞條；若查到，則從source_text中取字，繼續(xù)加入tail_word中，并繼續(xù)在子表中查找。在此過程中，如果滿足條件的詞條等于當(dāng)前的tail_word，則置segmented_word=head_word+tail_word；步驟3中的查找失敗時(shí)，則以當(dāng)前segmented_word中的字符串作為輸出結(jié)果。算法2和算法3的處理思想是一致的，只是在上述第三步的查找中，算法2采用的是順序查找，而算法3采用的是二分查找。在本例中，tail_word從“華”遞增到“華人民共和國”的過程中，即使不計(jì)查找過程中的比較次數(shù)，tail_word與詞典中的子表項(xiàng)“華”字比較了1次，同“華人民共和國”比較了5次。其比較長度分別為2、4、6、8、10、12?！叭A” （segmented_word=“中華”）“華人”“華人民”“華人民共”“華人民共和”“華人民共和國” （segmented_word=“中華人民共和國”）顯然，這種比較過程存在冗余的比較操作。例如，“人”字比較了5次，其中后4次的比較是多余的。因?yàn)樽址容^所需的時(shí)間同字符串的長度成正比，對于較長的詞條，這種現(xiàn)象尤為突出。為了消除這種冗余操作，我們提出將詞典的詞尾部分以自動(dòng)機(jī)的形式來組織。為此，我們將組成單詞的每個(gè)字以一種鏈表節(jié)點(diǎn)的形式存儲(chǔ)，其抽象數(shù)據(jù)結(jié)構(gòu)的定義如下：Pnode=ATnode;Tnode=recordBrother:Pnode;Cchar:String[2];Accepted:Boolean;Child:Pnode;End;這樣，上述的例子中，詞典的部分內(nèi)容形式如下（其中T代表True,F代表False；節(jié)點(diǎn)左側(cè)為兄弟鏈，右側(cè)為孩子鏈）：圖3：改進(jìn)的詞典邏輯結(jié)構(gòu)顯然，這實(shí)際上是將詞典以二叉樹的形式組織起來，只是各節(jié)點(diǎn)中增加了接收狀態(tài)。在詞典中對于特定的首字，前兩字相同的詞條很少，前三字相同的詞條更少。當(dāng)我們以這種形式組織詞典后，除子表的第一層外，各個(gè)節(jié)點(diǎn)的兄弟數(shù)目都很小，對它們的查找采用順序查找方法較為適宜。對于子表的第一層，則采用二分查找。由于我們無法在一個(gè)純粹的鏈表結(jié)構(gòu)中進(jìn)行二分查找，為此，我們可以將子表的首層節(jié)點(diǎn)以動(dòng)態(tài)數(shù)組形式組織，或裝入容器類（Container）的可直接存取的線性表結(jié)構(gòu)中（如C++的vector,Delphi的Tlist等）。對應(yīng)于前文所述的算法，其第三步變?yōu)椋阂远植檎曳椒ㄔ谧颖硎讓又胁檎液瑃ail_word的節(jié)點(diǎn)；若查到,從source_text中取后續(xù)漢字,繼續(xù)加入tail_word中,并繼續(xù)在當(dāng)前子表的孩子節(jié)點(diǎn)中順序查找該漢字。在此過程中，如果滿足條件的節(jié)點(diǎn)中Accepted域?yàn)檎?，則置segmented_word=head_word+tail_word；依此算法，顯然不會(huì)出現(xiàn)同一詞條中的重復(fù)比較，且每次比較的字符串（一個(gè)漢字）長度均為2。與算法2和算法3相比，在子表首層以下的搜索過程中，每次搜索的范圍因詞典的組織方式變化而大大縮小，這也在一定程度上提高了分詞效率。3對比文獻(xiàn)［2，3］都采用了文獻(xiàn)［2］所提出的復(fù)雜度估算方法，其相應(yīng)算法的復(fù)雜度分別為2.89和1.66。由于在處理3字以上詞時(shí)搜索空間的縮?。词箤τ诔霈F(xiàn)頻率最高的雙字詞，基于最大匹配原則，也需對其后繼字符進(jìn)一步測試比較），本文的算法復(fù)雜度顯然應(yīng)低于算法3的1.66。此外，文獻(xiàn)［2］所提出的復(fù)雜度估算方法并未考慮字符串長度對比較時(shí)間的影響。根據(jù)我們的實(shí)驗(yàn)測定，算法3比算法2大約快3倍。表1是針對同一組2.576MB文本的分詞結(jié)果比較，其中的比較次數(shù)是指實(shí)際調(diào)用字符串比較函數(shù)的次數(shù)，比較總長度是指每次調(diào)用字符串比較函數(shù)所比較的字符串的總長度，運(yùn)行環(huán)境為Windows2000（奔騰III，800M主頻，256M內(nèi)存）。算法時(shí)間（秒）切分詞數(shù)比較次數(shù)比較總長度算法231.345212952066410745567532算法311.76521295411090012461118本文6.32(3.37)52129535967607193520表1三種算法針對同一組語料的分詞實(shí)驗(yàn)結(jié)果從表1可以看出，算法2比較次數(shù)過多，且字符串比較的總長度過大。而算法3的比較次數(shù)和字符串比較的總長度均大于本文算法。同一首字下的所有詞條組織成的子表的查找應(yīng)采用二分查找。這正是算法3優(yōu)于算法2的關(guān)鍵之處。而本文算法的優(yōu)勢則體現(xiàn)在比較次數(shù)的縮小和被比較字符串的長度縮小，絕無多余的比較，從而在總比較長度上占絕對優(yōu)勢從實(shí)驗(yàn)結(jié)果可以看出，分詞時(shí)間大約與字符串比較的總長度成正比。實(shí)際上，我們的多組對比實(shí)驗(yàn)表明，隨著被處理語料規(guī)模的增大，這種線性比例關(guān)系表現(xiàn)得更為明顯。這也是“字符串比較所需的時(shí)間同字符串的長度成正比”這一結(jié)論的實(shí)際驗(yàn)證。我們的實(shí)驗(yàn)所對比的三種算法均至少用C++和ObjectPascal兩種語言實(shí)現(xiàn)，而且為了對比結(jié)果客觀公正，所用數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)細(xì)節(jié)都盡可能一致。文中的實(shí)驗(yàn)數(shù)據(jù)是Delphi版本的結(jié)果，其中括號(hào)內(nèi)的時(shí)間是在用小于運(yùn)算代替字符串比較函數(shù)時(shí)的結(jié)果（ObjectPascal對字符串的處理能力強(qiáng)于C/C++）0另外，C++的標(biāo)準(zhǔn)模板庫（STL）的運(yùn)行效率很低，我們的其它實(shí)驗(yàn)對比表明，C++版本的分詞程序在不使用STL時(shí)運(yùn)行速度大約是使用STL時(shí)的9倍。另需說明的是，在本文的算法描述中，為了以文字形式描述方便，引入了幾個(gè)輔助變量。它們在實(shí)際編程時(shí)并非必需，例如可以用一些下標(biāo)變量來完成segmented_word和tail_word的功能。4結(jié)論隨著網(wǎng)絡(luò)技術(shù)的不斷普及和發(fā)展，中文信息處理的某些應(yīng)用領(lǐng)域，如信息的過濾與檢索，對于漢語分詞的效率要求越來越高。我們所討論的快速分詞算法，是在中文信息處理的研究與應(yīng)用中遇到的實(shí)際問題。本文主要對比分析了文獻(xiàn)[2，3]所提出的算法，指出其冗余的比較操作，并在此基礎(chǔ)上提出了改進(jìn)的詞典數(shù)據(jù)結(jié)構(gòu)和相應(yīng)的分詞算法，以提高分詞效率。通過分析和實(shí)驗(yàn)，說明了我們所提出的算法的有效性。參考文獻(xiàn)揭春雨，劉源，梁南元.論漢語自動(dòng)分詞方法?中文信息學(xué)報(bào),1989,3(1):1?8,1989。1?8吳勝遠(yuǎn).一種漢語分詞方法計(jì)算機(jī)研究與發(fā)展1996年第4期。306~311陳桂林，王永成，韓客松，王剛.一種改進(jìn)的快速分詞算法.計(jì)算機(jī)研究與發(fā)展.2000年第4期：418?424AnAutomaton-basedWordSegmentation

Method1ChiChenying,2ZhanXuegang,2YaoTianshun

(1AnshanUniversityofScienceandTechnology,SchoolofComputerScienceandTechnology,

Anshan,China,114000;2NortheasternUniversity,SchoolofInformationScienceandEngineering,Shenyang,China,

110004)AbstractThispaperproposesafastmethodforCh