漢語自動分詞的詞典機制

漢語自動分詞的詞典機制

0自動分詞處理分詞依據(jù)中文信息處理包括文獻(xiàn)探索、機器翻譯、文獻(xiàn)分類、文獻(xiàn)過濾、自動編輯等。與印歐語不同，漢字是“字”的字符串，所以漢語和漢語之間沒有區(qū)別。利用計算機處理中文信息時,往往涉及到詞的問題,即書面漢語中的詞的切分問題。所謂漢語自動分詞,是把輸入計算機的漢語詞句自動切分為詞的序列的過程。特定情況下分詞結(jié)果中也包括一些詞組和詞素。由于現(xiàn)代漢語缺乏明顯的形態(tài)標(biāo)志,詞素組合成詞也沒有嚴(yán)格的規(guī)律遵循,從而給自動分詞帶來很大的困難。本文首先簡單描述了已有的分詞詞典機制,接著介紹了我們提出的新的詞典機制——一種基于雙哈希二叉樹的索引結(jié)構(gòu),最后對新的機制和已有的機制進(jìn)行了比較和實驗分析。1分詞算法的研究方法迄今為止人們己經(jīng)提出了許多計算機自動分詞算法,根據(jù)研究方法的出發(fā)點不同,可以歸納為三大類:基于詞典的分詞方法、基于統(tǒng)計的分詞方法、基于AI的分詞方法。1.1基于詞典的分詞方法這種分詞方法是前蘇聯(lián)專家在上個世紀(jì)50年代末提出來的,由于該分詞方法是使用詞典作為分詞依據(jù),故稱為基于詞典的分詞方法。其基本思想是:事先建立一詞庫,其中包含所有可能出現(xiàn)的詞。對給定的待分詞的漢字串S,按照某種確定的原則切取S的子串,若該子串與詞庫中的某詞條相匹配,則該子串是詞,繼續(xù)分割剩余的部分,直到剩余部分為空;否則,該子串不是詞,轉(zhuǎn)上重新切取S的子串進(jìn)行匹配。1.2相鄰之間的頻率或概率計算漢語語言文字較之西文的一個顯著區(qū)別是:詞與詞之間沒有顯著的分隔標(biāo)記。還有一個很難纏的問題是:“什么是詞?”“漢語中究竟有多少個詞”,這樣就產(chǎn)生了基于統(tǒng)計的分詞方法,又稱為無詞典分詞方法。這類方法的主要依據(jù)和思想是:詞是穩(wěn)定的字的組合,因此在上下文中,相鄰的字同時出現(xiàn)的越多,就越有可能構(gòu)成一個詞。因此字與字相鄰共現(xiàn)的頻率或概率就能夠較好地反映成詞的可信度?？梢詫φZ料中相鄰共現(xiàn)的各個字的組合的頻度進(jìn)行統(tǒng)計,計算它們的互現(xiàn)信息?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當(dāng)緊密程度高于某一個閾值時,便可以認(rèn)為此字的組合可能構(gòu)成了一個詞。基于統(tǒng)計的分詞方法優(yōu)點在于,能夠有效地自動排除歧義,能夠識別新詞、怪詞,例如人名、地名等,解決了基于字典的分詞方法的弊病。但這種方法也有一定的局限性,會經(jīng)常抽出一些共現(xiàn)頻度高,但并不是詞的常用字組,例如“這一”、“之一”、“有的”、“我的”、“許多的”等,并且對常用詞的識別精度差,時空開銷大。一般的應(yīng)用中,我們一般是將其與基于詞典的分詞方法結(jié)合起來,即發(fā)揮匹配分詞切分速度快、效率高的特點,又利用了無詞典分詞結(jié)合上下文識別生詞、自動消除歧義的優(yōu)點1.3根據(jù)ai的價格分布方法將專家系統(tǒng)和神經(jīng)網(wǎng)絡(luò)應(yīng)用到中文自動分詞中來提高分詞的智能性,是近年來研究的一個熱點。2現(xiàn)有的詞典機制傳統(tǒng)的分詞詞典機制有5種。下面我們簡單介紹一下。(1)詞典信息編碼如圖1所示,該機制的詞典結(jié)構(gòu)分為首字Hash表、詞索引表、詞典正文三級。詞典正文是以詞為單位的有序表,詞索引表是指向詞典正文中每個詞的指針表。通過首字散列表的哈希定位和詞索引表很容易確定指定詞在詞典正文中的可能位置范圍,進(jìn)而在詞典正文中通過整詞二分進(jìn)行定位。(2)樹的分詞詞典機制TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹。如圖2所示,基于TRIE索引樹的分詞詞典機制由首字散列表和TRIE索引樹結(jié)點兩部分組成。TRIE索引樹的優(yōu)點是在對被切分語句的一次掃描過程中,不需預(yù)知待查詢詞的長度,沿著樹鏈逐字匹配即可;缺點是它的構(gòu)造和維護(hù)比較復(fù)雜,而且都是單詞樹枝(一條樹枝僅代表一個詞),浪費了一定的空間。(3)逐字第二部分分匹配這種詞典機制是前兩種機制的一種改進(jìn)方案。逐字二分與整詞二分的詞典結(jié)構(gòu)完全一樣,只是查詢過程有所區(qū)別:逐字二分吸收了TRIE索引樹的查詢優(yōu)勢,即采用的是“逐字匹配”,而不是整詞二分的“全詞匹配”,這就一定程度地提高了匹配的效率。但由于采用的仍是整詞二分的詞典結(jié)構(gòu),使效率的提高受到很大的局限。(4)模式1:順序搜尋、二元追蹤如圖3所示,在詞典中對于特定的首字,前兩字相同的詞條很少,前三字相同的詞條更少。當(dāng)以這種形式組織詞典后,除子表的第一層外,各個節(jié)點的兄弟數(shù)目都很小,對它們的查找采用順序查找方法較為適宜。對于子表的第一層,則采用二分查找。由于無法在一個純粹的鏈表結(jié)構(gòu)中進(jìn)行二分查找,為此,可以將子表的首層節(jié)點以動態(tài)數(shù)組形式組織,或裝入容器類的可直接存取的線性表結(jié)構(gòu)中。顯然,這實際上是將詞典以二叉樹的形式組織起來,只是于該文算法。同一首字下的所有詞條組織成的子表的查找,應(yīng)各節(jié)點中增加了接收狀態(tài)。分詞使用該詞典不會出現(xiàn)同一詞條的重復(fù)比較,在字表首層以下的搜索過程中,每次搜索的范圍因詞典的組織方式變化而大大縮小,這也在一定程度上提高了分詞效率。(5)“雙確定”下的哈希索引,“雙下墊型”的詞典和未收詞型,2該機制吸納了”整詞二分”及”TRIE索引樹”二者的優(yōu)點,僅對詞語的前兩個字順次建立哈希索引,構(gòu)成深度僅為2的TRIE子樹,詞的剩余字串按序組成類似”整詞二分”的詞典正文,詞典結(jié)構(gòu)如圖4所示。3改進(jìn)的詞典組織3.1分詞詞典機制從第2節(jié)中對5種典型詞典機制的介紹可以看出:整詞二分和TRIE索引樹是分詞詞典機制的兩個極端。整詞二分的數(shù)據(jù)結(jié)構(gòu)簡單、占用空間小,構(gòu)建及維護(hù)也簡單易行,但由于采用全詞匹配的查詢過程,效率低下;TRIE索引樹的數(shù)據(jù)結(jié)構(gòu)復(fù)雜、空間浪費較為嚴(yán)重,樹的構(gòu)造和維護(hù)也較為繁瑣,但它采用的查詢過程是“逐字匹配”,所以查詢效率較高。第三種分詞詞典機制(基于逐字二分)雖然采用了較為高效的匹配方法——逐字匹配,但并沒有改進(jìn)“整詞二分”的數(shù)據(jù)結(jié)構(gòu),使得匹配過程并不是完全意義上的逐字匹配,這就導(dǎo)致查詢效率并沒有得到最大限度的提高。第四種分詞詞典機制(基于自動機)實際上是將詞典以二叉樹的形式組織起來,只是各節(jié)點中增加了接收狀態(tài)。依此算法,顯然不會出現(xiàn)同一詞條中的重復(fù)比較,且每次比較的字符串(一個漢字)長度均為2。與算法1、算法2和算法3相比,在子表首層以下的搜索過程中,每次搜索的范圍因詞典的組織方式變化而大大縮小,這也在一定程度上提高了分詞效率。為了最大限度的提高匹配的時間效率并兼顧空間利用率,我們提出了一種新的分詞詞典機制———基于雙哈希二叉樹的分詞詞典機制。3.2字典結(jié)構(gòu)1計算哈希地址的確定首字Hash索引的每個單元包括三項內(nèi)容:①關(guān)鍵字:詞的第一個漢字A;②p值:存儲次字Hash的p值;③次字Hash索引指針:指向以漢字A起始的所有詞語的第二個漢字的索引。采用除留余數(shù)法計算哈希地址首字哈希表的單元:Typedefstruct{CharFirstKey;Intp;Tnode*FChild;}FHnode;2字串近接口字次字Hash索引的每個單元包括一項內(nèi)容:剩余字串指針:指向以A為首字且次字Hash地址同為i的字結(jié)點組成的單鏈表;Typedefstruct{Tnode*Head;}SHnode;3叉樹結(jié)構(gòu)結(jié)點的數(shù)據(jù)結(jié)構(gòu)如下定義:Typedefstruct{Tnode*LBrother;CharKey;BooleanAccepted;Tnode*RChild;}Tnode,*Pnode;在該結(jié)構(gòu)中,LBrother為兄弟鏈,指向出現(xiàn)概率較本結(jié)點小的字,Accepted為T時表示獨立成詞,為F時表示不獨立成詞,RChild為孩子鏈,指向下一個出現(xiàn)概率最大的字,如圖5所示。3.3算法描述1odl的編碼在此算法中,單個漢字的哈希值H=VmodL,其中V是此漢字的內(nèi)碼,L是Hashtable的可變表長,L的初始值取常數(shù)initCapacity。(1)選取內(nèi)碼中心上的哈希漢字在計算機內(nèi)采用內(nèi)碼來存儲,而漢字的內(nèi)碼具有唯一性和連續(xù)性,因此對于首字哈希,V值我們選取漢字內(nèi)碼,L值我們選取合適的質(zhì)數(shù)p,使哈希地址與漢字一一對應(yīng)。(2)哈希表的編碼和重組以某個漢字開頭的非單字詞,多則幾百個少則幾個,甚至一個,如果對第二個字進(jìn)行哈希存儲,則表長不能一概而論,如圖5所示,此算法采用鏈地址法來處理溢出情況,它把哈希表中儲存的所有關(guān)鍵碼劃分為L個子集合(桶),具有同一個哈希值H(0≤H≤L-1)的表項均被置于第H個桶中;同一個桶中的不同表項通過指針存儲在一個單鏈表中。當(dāng)哈希表中儲存的所有表項總數(shù)C滿足C/L>loadFactor時,此算法令L=2×L+1,并對哈希表進(jìn)行重組,其中l(wèi)oadFactor是滿足0<loadFactor<1的常數(shù)。在本實驗中,我們令初始表長initCapacity和裝添因子上限loadFactor均取缺省值,即令initCapacity=11,loadFactor=0.75。(3)c型的rhild指導(dǎo)思想中,a次字哈希表中的一個表項指向一棵二叉樹,該二叉樹的根結(jié)點是以AB為前兩個字的詞中出現(xiàn)概率最大的第三個字,我們稱該結(jié)點為C,它的LBrother指針指向的結(jié)點的字的出現(xiàn)概率較C結(jié)點小,它的RChild指針指向的結(jié)點是以ABC為頭三個字的詞中出現(xiàn)概率最大的第四個字。如果以AB開頭的詞只有AB本身,則該二叉樹為空。2rchild指導(dǎo)思想①取出待分詞文章的第一個字A,將A存入一個長度為17的空數(shù)組W中,經(jīng)過哈希運算求出哈希地址i,在首字哈希表中找到相應(yīng)的位置i,如果該位置的指針域為空,則該字是一個單字詞,設(shè)標(biāo)志位F=1,計數(shù)位S=1,繼續(xù)①。否則②。②取下一個字B,計數(shù)位S加1,經(jīng)過哈希運算求出哈希地址,在次字哈希表中找到相應(yīng)的位置,在相應(yīng)的單向鏈表中查找第二個字所對應(yīng)的結(jié)點,如果找到相應(yīng)的結(jié)點,將B字順次存入數(shù)組W中,判斷該結(jié)點的Accepted域是否為T,F=S,轉(zhuǎn)向③。如果找不到,則A是一個單字詞。轉(zhuǎn)向①。③如果該結(jié)點的Rchild域為空,則數(shù)組W中的前F個字成詞,轉(zhuǎn)向①。否則,取下一個字C,計數(shù)位S加1,與相應(yīng)的結(jié)點的Rchild指針指向的結(jié)點比較,如果相等,判斷該結(jié)點的Accepted域是否為T,為T,F=S,轉(zhuǎn)向③;如果不等,轉(zhuǎn)向④。④如果待分詞文章結(jié)束,則轉(zhuǎn)向⑥。否則,如果相應(yīng)結(jié)點的Lchild指針為空,則數(shù)組W中的前F個字成詞,轉(zhuǎn)向①。否則,指針指向該結(jié)點的Lchild域指向的結(jié)點,如果相等,判斷該結(jié)點的Accepted域是否為T,為T,F=S,轉(zhuǎn)向③;如果不等,轉(zhuǎn)向④。⑤如果待分詞文章結(jié)束,則轉(zhuǎn)向⑥。否則,如果相應(yīng)結(jié)點的左指針為空,則數(shù)組W中的前F個字成詞,轉(zhuǎn)向①。繼續(xù)比較。如果相等,轉(zhuǎn)向④。如果不等,轉(zhuǎn)向⑤。⑥結(jié)束。例如:源文本“這個謊言將大白于天下?！狈衷~結(jié)果=“這個/謊言/將/大白于天下”以“大白于天下”為例介紹一下分詞過程:(1)取“大”字,將“大”字存入空數(shù)組W,F=1,S=1,在首字Hash表中直接定位,如果該位置的指針域為空,則該字是一個單字詞,否則(2)。(2)取“白”字,將“白”字順次存入空數(shù)組W,S=2,在“大”字指向的次字hash表中定位,沿著單向鏈表找到“白”字,“白”字的Accepted域為T,F=S。(3)取“于”字,將“于”字順次存入空數(shù)組W,S=3,“白”字結(jié)點的RChild指針指向的結(jié)點等于“于”。(4)取“天”字,將“天”字順次存入空數(shù)組W,S=4,“于”字結(jié)點的RChild指針指向的結(jié)點等于“天”。(5)取“下”字,將“下”字順次存入空數(shù)組W,S=5,“天”字結(jié)點的RChild指針指向的結(jié)點等于“下”?！跋隆弊值腁ccepted域為T,F=S。待分詞文章結(jié)束。(6)所以數(shù)組中從“大”字開始的前F個字成詞,即“大白于天下”是一個詞。4種詞典機制的比較基于逐字二分的詞典機制是基于整詞二分和基于TRIBE索引樹的分詞詞典機制的一種改進(jìn)方案。逐字二分與整詞二分的詞典結(jié)構(gòu)完全一樣,只是查詢過程有所區(qū)別:逐字二分吸收了TRIE索引樹的查詢優(yōu)勢,即采用的是“逐字匹配”,而不是整詞二分的“全詞匹配”,這就一定程度地提高了匹配的效率。所以我們在實驗時沒有考慮基于整詞二分和基于TRIBE索引樹的分詞詞典機制。我們分時間和空間兩個方面來對基于逐字二分的詞典機制、基于自動機的詞典機制、基于雙字哈希的詞典機制、基于雙哈希二叉樹的分詞詞典機制的四種詞典機制進(jìn)行分析比較,后面依次稱為算法1、算法2、算法3、算法4。從空間復(fù)雜度的角度來考慮算法1所占空間最小,算法4最大,由于空間復(fù)雜度是一次性消費,而分詞的速度取決于平均比較次數(shù),所以下面從時間復(fù)雜度的角度考慮:本次實驗采用的是windows2003server,奔騰Ⅲ,800M主頻,1GB內(nèi)存,Java語言編程實現(xiàn)。實驗采用的語料是3.23MB的文本,對于上述4種詞典機制采用正向最大匹配方法,實驗結(jié)果如表1所示。從該表可以看出算法2至算法4無論從時間上還是從比較次數(shù)上都大大優(yōu)于算法1,而其中算法4為最佳,究其原因是算法4綜合了算法2和算法3的優(yōu)點,因為字典中兩個字的詞居多,所以我采用首字和次字哈希索引,對于兩字詞可