一種快速中文分詞機制

隨著中文網絡覆蓋的大規模發展，包含中文信息的網絡數據也在迅速擴張。長期以來，對中國網絡數據的實時分析和處理已成為下一代中國信息處理技術必須關注的問題。作為中國信息事務管理的基礎，它已廣泛應用于漢語搜索、人工智能、信息提取、文本搜索等領域。成功的中文分詞機制需要同時具有較高的詞匯切分準確性和快速的詞匯切分能力.其中,前者需要解決未登錄詞匯(out-of-vocabulary)識別和詞匯歧義切分等難題,目前主要采用字符串頻度統計,語料字詞標注等機器學習方法;而快速詞匯切分能力是關系到整個中文信息處理系統,特別是實時處理類應用系統可用性的關鍵技術,目前主要通過設計高效的分詞詞典機制來實現速度提升.此類快速分詞機制一般基于傳統的詞典分詞方法,依靠已有的特征詞典作為文本切分匹配依據,設計簡單,實現容易,算法效率很高,詞典法分詞機制中與分詞速度相關的有2個要素:詞典構造方法和詞匯匹配方法,這2個方面相互關聯.常見的詞匯匹配方法有前向匹配、后向匹配、最大匹配、逐字匹配等.目前研究認為,采用前向最大匹配是分詞速度最高的匹配方法.本文不研究匹配方法造成的分詞速度差異,主要通過研究不同詞典的構造方法來實現高速的分詞機制.文中第1部分簡單描述了幾種經典分詞詞典機制;第2部分詳細介紹幾種改進詞典機制;在第3部分介紹作者提出的一種快速中文分詞詞典構造機制:雙字詞和長詞哈希索引機制(double-character-and-long-vocabulary-hash-indexing);第4部分通過分析和實驗說明新體制與原有體制相比具有的優勢.1傳統的詞典組織最為典型的分詞詞典機制有以下3類:整詞二分法、TRIE索引樹法和逐字二分法.1.1確定復雜詞的定位和導致匹配機制整詞二分法的詞典結構分為詞典正文、詞索引表、首字散列表等3級.通過首字散列表的哈希定位和詞索引表,很容易確定指定詞在詞典正文中的可能位置范圍,進而在詞典正文中通過整詞二分進行定位.基本的機制結構如圖1.1.2tre索引樹人工樹人本機TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹,基于TRIE索引樹的詞典機制由首字散列表和TRIE索引樹結點2部分組成.TRIE索引樹的優點是分詞應用中,在對被切分語句的一次掃描過程中,不需預知待查詢詞的長度,沿著樹鏈逐字匹配即可;基本的機制結構如圖2(a)所示.1.3整詞二分法和tre索引樹法基于逐字二分法的查詢機制是對前2種詞典機制的改進方案,一方面,從組織結構上,逐字二分與整詞二分的詞典結構完全一樣;另一方面,逐字二分吸收了TRIE索引樹的查詢優勢,即采用的是“逐字匹配”,而不是整詞二分的“全詞匹配”,這在一定程度上提高了匹配的效率,如圖2(b).以上3種基本的詞典機制是該方向研究中的經典機制,但他們的缺點也十分突出.整詞二分法完全采用全詞匹配的查詢過程,效率明顯較為低下;TRIE索引樹法的構造和維護比較復雜,而且都是單詞樹枝,浪費了一定的空間;而逐字二分法由于采用的仍是整詞二分的詞典結構,雖然采用了較為高效的匹配方法,但并沒有改進“整詞二分”的數據結構,使得匹配過程并不是完全意義上的逐字匹配,這使效率的提高受到很大的局限.各種新的詞典查詢機制應運而生,下面來介紹其中幾種有代表性的機制.2一些新的詞典機制2.1基于前2個字的詞典機制文獻提出了基于雙字哈希機制的詞典查詢方法,該方法主要根據漢語中雙字詞語較多的特點,基于TRIE索引數的詞典機制做出了改進,采用前2個字逐個哈希索引、剩余字串有序排列的結構,查詢過程采用逐字匹配的方法,這相當于使2字詞以下的短語用TRIE索引樹機制實現,3字詞以上的長詞的剩余部分用線性表組織,從而避免了深度搜索,在不提升已有典型詞典機制維護復雜度的情況下,提高分詞速度.圖3為該機制的正向實現圖.2.2基于位串的方法文獻提出了基于PATRICIAtree的漢字詞典查詢機制,PATRICIAtree本質上是一種壓縮的二叉查詢樹,它將關鍵詞作為二進制位串記錄在樹的結構中,從根節點到葉子節點的每一條路徑都代表一個關鍵詞位串.在文獻中,作者利用詞條的內碼來作為一個關鍵詞位串,然后通過位串比較構造出PATRICIAtree,樹的每個內部節點包括3個數據項:比較位、左指針、右指針,樹的葉子節點代表一個詞條.查詢時根據內部節點選擇后繼路徑,直到葉子節點.該方法的優點是引入了位比較,只需要進行為數不多的位比較和幾次字符串比較,就能完成各種查詢和更新功能.2.3e樹的改進方法文獻提出了一種基于雙數組Trie(double-arraytrie)的數據結構,Trie樹本質上是搜索樹的一種,是一個確定的有限狀態自動機(DFA),每個節點代表自動機的一個狀態,根據變量的不同,進行狀態轉移,當到達結束狀態或者無法轉移的時候,完成查詢.文獻使用文獻中對傳統的Trie進行的改進方法,用2個線性數組來進行Trie樹的表示,即雙數組Trie.2.4數碼序列到數偶碼的轉換文獻還提出了一種雙編碼機制,其基本思想是將GB-2312編碼中的6768個常用漢字唯一的映射到1～6768間的一個序列碼,從而每個漢字串都可以唯一地映射到一個數字串,這樣將對于詞語的查詢轉化為基于數字串的查詢.雙編碼中還要將數碼序列轉換為數偶碼表,排好序,供檢索用.雙編碼機制的第1步是從數碼序列到數偶碼的轉換,這種轉換主要采用歐幾里德算法(輾轉相除法)的思想,保證了從數碼序列和數偶碼之間轉換的唯一性;同時還達到了一定程度上數據壓縮的目的.第2步需要建立索引機制,對整個詞典進行編碼,這樣每個詞語就對應一對數偶碼,由于隨著詞語的長度增加,數值會變得很大,所以必須建立相應索引.2.5哈希機制的優勢雙字哈希機制是一種比較簡潔的機制,作為對TRIE索引樹的改進,在構造和維護上比前者簡單,但它對于中文分詞速度的提升并不明顯.原因一是在逐字匹配方法上它并不比TRIE索引樹有太多的改進,二是在于文獻中使用的java.util.Hashtable內置哈希算法也不是一個非常高效的算法.基于PATRICIAtree的自動分詞機制在速度上是一種較具有優勢的算法,但因為樹的構造完全基于內碼而非字,所以不可避免地導致樹的深度大大增加,從而造成了效率降低和空間的浪費.基于雙數組Trie的機制的算法效率很高,但也存在一個致命弱點:在構造調整的過程中,每個狀態都依賴于其他狀態,所以在詞典需要進行刪減或增加的時候,需要對雙數組進行全局的調整,靈活性很差,這也明顯不符合實際使用的需要.雙編碼機制的詞典查詢算法,優勢在于避免了傳統查詢中的字符串操作,在哈希機制上更加靈活;同時詞典的組織方式是線性表,調整方便.但文獻中使用的算法壓縮率不夠大,導致了大數組的產生,限制了查詢效率的提高.從上面的分析看出,現有的諸多基于詞典的分詞機制都存在著諸多問題,文本結合上述方法的優缺點提出了一種新的中文分詞詞典機制.3基于雙詞語-長詞的中文分詞詞典機制對以上若干參考文獻的分析容易發現,詞典法快速查詢方法中,分詞速度較高的機制往往需要消耗更多的內存資源.在計算機性能得到極大提高的情況下,可以承受快速分詞機制對資源的占用,但如果內存占用過大,也會影響算法的實際應用能力.本文中,作者提出了一種基于雙字詞-長詞的中文分詞詞典機制(DCLVHI).該機制不通過無限制占用內存,而主要依賴于減少詞匯切分所需的平均匹配次數來提高分詞效率.表1介紹了本文對中文詞匯的簡單分類.3.1雙漢字前2個字的詞匯結構在漢字詞匯中,雙字組成的詞匯占了大部分,對常用詞典(人民日報)的統計發現,在108783個詞匯中,51%為2字詞,31%為3字詞,13%為4字詞,3%左右為單字詞,多于4字以上的詞匯只占2%左右.而在對中文文本的權威統計中,雙字詞占有的比例更是高達70%以上,正是因為看到了雙字詞的作用,文獻提出了雙字哈希機制.在本文提出的新機制中,為了進一步體現雙字詞的重要性,直接針對雙字詞或多字詞的前2個字建立Hash索引,這樣進一步突出了雙字詞的作用,而將多字詞的剩余字串建立了專門的長詞表,長詞表也是一個Hash索引.也就是說,在詞典的結構化過程時,無論該詞匯為雙字詞、3字詞或其他多字詞,均首先將該詞匯首2字直接建立Hash表.而純粹的單字詞(非其他任何詞匯的前綴),在該詞典詞匯結構中不占用空間.具體詞典結構可以參見圖4.3.2實驗2:網絡結構的構建本節著重介紹圖4表現的機制具體構成,DCLVHI機制主要由2個主要部分構成:首詞Hash索引和長詞Hash索引.其中前者又包括了2項內容:(1)標志位(2bytes):詞的標志位,一般認為的漢字詞匯不會超過16個字,選取2個字節,16bit作為該詞的標志位,i比特位設置為1,則表示為該雙字詞可以是一個長度為i+1的長詞.如圖4,圖集是一個雙字詞,它不能作為其他詞的前綴,那么該詞標志位值為0000000000000010,表示其只能是一個2字詞.再如電老,它本身不是詞,但可以作為3字詞的前綴,它的標志位就是0000000000000100,而春夏秋冬,春夏單獨可以作為一個詞,但也可以作為春夏秋冬這個4字詞的前綴,于是它的標志位就是0000000000001010,其他詞匯的標志位值同理可得.(2)字符串指針(4bytes):指向詞匯在內存中的位置,將詞庫的所有詞匯放入到一段連續空間中,指向每個詞匯的指針保存在該項中.長詞Hash索引的結構與首詞索引類似,但只包括了1項內容.即字符串指針(4bytes)指向詞匯在內存中的位置.最后一部分是字符串存儲部分,詞庫中的所有詞匯均放入一段連續的存儲空間,中間使用‘＼0’作為間隔.以上描述的詞典結構的構建過程均使用程序自動實現,具有較好的查詢效率,是一種適合正向最大匹配分詞的詞典構造方法,且不用預知待查詞的長度.3.3算法的有效性檢驗假設查詢一無意義字符串“君子蘭圖籍是個電老虎,春夏都敢作敢為”.查詢步驟如下:(1)從首詞Hash索引中,通過Hash定位得到以“君子”開頭的索引項,發現該索引項對應的比特位為“0x0006”,說明可以為2字詞也可以為3字詞.(2)指針移到“蘭”上,計算“君子蘭”Hash索引,發現它的確是一個3字詞,匹配成功.(3)指針指向“圖籍”,通過Hash定位得到“圖籍”的索引項,發現該索引項的比特位是“0x0002”,只可能是2字詞.一次匹配成功.(4)“是個”,這種情況也會存在,2個單字組成的詞,在Hash索引中可能定位到的索引處沒有值,那么直接將“是”作為單字返回.如果發現索引處有值(Hash算法可能會碰撞),需要再進行比較.在Hash算法的設計時,方案會盡量減少這種碰撞的機會.(5)“春夏”,既可以是2字詞也可能是4字詞前綴,根據最大匹配法的原則,先匹配“春夏都敢”,查找長詞表后,發現它不存在,返回結果“春夏”為匹配成功的2字詞.剩余文本的處理也可參照上面的方法進行.4效率指標比較中文分詞機制的評價指標有詞匯召回率、準確率、分詞速度等.本文主要比較采用以上各類不同詞典構造方法,造成的分詞速度差異.同時將各詞典構造方法所需的系統內存也作為效率指標進行比較.下文中分別比較以下指標:(1)內存使用量,只有內存在允許的范圍內,分詞機制才具有可行性;(2)機制的平均詞匯查詢次數,即切割單個詞匯的平均查詢次數;(3)對于指定文本的查詢時間實驗.4.1基于tricortg的教育應用詞典查詢算法占用內存可以作為查詢機制效率的重要指標.分詞機制下的基本內存消耗有如下4項:(1)詞表占用空間574560bytes,SL=108000*(2*0.03+4*0.50+8*0.13+12*0.03)=574560bytes;(2)首字散列表每單元8bytes,共7500個單元左右,Fchi=7500*8=60000bytes;(3)詞索引表每個詞占4bytes,共108000個詞,Wit=108000*4=432000bytes;(4)TRIE索引數每個TRIE索引數結點單元占8bytes,Th=130000*8=1040000bytes.整詞二分和逐字二分的機制包括(1)、(2)、(3)項開銷:Ssbw=SL+Fchi+Wit=1066560bytes;(1)Ssbc=SL+Fchi+Wit=1066560bytes;(2)基于TRIE索引的包括(2)、(4)項開銷:STrie=Fchi+Th=1100000bytes;(3)PATRICIAtree方法的開銷約為SPr=2*10*108000=2160000bytes;(4)雙字哈希算法的開銷約為SDchi≈1800000bytes;(5)雙數組算法的開銷約為SDaTrie=113*108000+108000*2.4*3*4=15314000bytes;(6)雙編碼機制的開銷約為SDC=113*108000+3342430=15546430bytes;(7)本文中設計的新機制的內存消耗包括以下幾個部分:(1)首詞Hash表:使用2種不同的Hash算法,可以得到2種不同的內存消耗.(a)非壓縮算法索引數IN=C23500=3500(3500?1)2=6123250(2500ΙΝ=C35002=3500(3500-1)2=6123250(2500個常用單詞和1000個次常用單詞)標志位的長度Fb=2bytes;詞指針的長度Wp=4bytes;消耗內存S1a=IN*(Fb+Wp)=36739500bytes;(b)壓縮算法索引數IN=3*108000*0.5=162000bytes;(系數3是一個通用比例)消耗內存S1b=IN*(Fb+Wp)=1944000bytes;(2)長詞表索引長詞表索引數LIN=108000*0.4=43200;長詞指針長度Lwp=4bytes;消耗內存S2=LIN*Lwp=172800bytes;(3)詞庫SL=574560bytes;新機制2種方式下的內存消耗分別為:SDCLVHIa=S1a+S2+SL=37486860bytes,(8)SDCLVHIb=S1b+S2+SL=1719360bytes.(9)從圖5可以看出,不采用壓縮算法的機制SDCLVHIa需要占用較大的內存容量,而采用壓縮算法的新機制SDCLVHIb在內容消耗上與其他算法相差不大.4.2實際文本匹配和數據來源詞匯平均查詢次數是反映分詞機制效率的重要指標.一般認為,詞匯平均查詢次數越少,該機制可能分詞效率越高.在表1的基礎上,主要選取5類代表詞匯,其中包括單字詞、無前綴雙字詞和3類N字詞(如表2).理論分析新機制與上文提及的幾種典型詞典改進算法的平均查詢次數.從理論分析比較可以看出,在文本匹配的主要情況下,DCLVHI所需要的查詢次數都更少,具有優勢.當然在所查詞匯很短,而其2字詞根作為很多不同長度詞前綴的情況下,DCHI可能具有優勢.但此種情況需要前綴級數超過3級,在常用詞庫中極少出現.通過各類實驗顯示的實際文本詞匯出現規律,也表明這種情況造成的效率損失有限.作者進行了較大規模的統計實驗以證明上面的理論估計,實驗所用數據來自1999年和2000年的TDT測試中使用的簡體中文數據,由LDC提供.選取其中最大的中文文本集(13233篇)作為測試數據,進行了下面幾個方面的統計.(1)相同詞匯的計算在這13233篇文章中一共出現了1530000個詞匯(同一篇文章中出現相同詞匯僅計算為1次,不同文章中出現的相同詞匯計算為2次),其中出現26156個雙字詞679229次,占44.39%;出現3298個單字詞共665479次,占43.50%;10084個3字詞共118765次,占7.76%;4895個4字詞共34997次,占2.29%;另有31530次4字以上詞,占出現次數的2.06%.(2)雙漢字雙音節詞,雙給詞數字13233篇文章中一共出現了3671294次詞匯(出現一次就計算為1次),其中雙字詞1814756次,占49.43%;單字詞1423971次,占38.78%;3字詞285293次,占7.78%;4字詞70980次,占1.93%;4字以上詞76294次,占2.08%.(3)作為3.和4.4個.在出現的26156個雙字詞中,其中非前綴雙字詞有18345個,作為3字詞前綴的是6801個,作為4字詞前綴的是1281個,4字詞以上前綴的有328個;同時作為3字詞/4字詞以上前綴的599個,僅占所有出現詞匯種類的2.29%.(4)dcsi機制下的查線結果非前綴雙字詞出現1488093次,3字詞前綴出現242136次,4字詞前綴出現52492次,4字詞以上前綴出現32035次.在該文本數據集下,利用DCLVHI機制,平均每個詞匯的查找輪數為1.25次,而如果采用DCHI的查找輪數是2.34次.4.3實驗數據集和效率測試結果參照文獻,本文采用了3類不同類型的查詢時間測試:(1)對選用詞典的所有詞遍