中文自動(dòng)分詞機(jī)制研究

1中朝文本分詞詞典機(jī)制的研究漢語詞典的研究是語文信息處理的基礎(chǔ)工作。它在許多領(lǐng)域的中文自動(dòng)分詞、文本檢索、機(jī)器翻譯和中文機(jī)器理解等應(yīng)用價(jià)值非常高。國內(nèi)自80年代中后期就開展了中文分詞詞典機(jī)制的研究,目前已有的分詞詞典機(jī)制主要有:基于整詞二分的分詞詞典機(jī)制、基于TRIE索引樹的分詞詞典機(jī)制和基于逐詞二分的分詞詞典機(jī)制。第2部分詳細(xì)介紹這三種分詞詞典機(jī)制,并對(duì)其進(jìn)行了比較;第3部分通過對(duì)漢字編碼體系、漢語詞特點(diǎn)的分析,充分發(fā)揮了現(xiàn)代計(jì)算機(jī)內(nèi)存大空間的優(yōu)勢,提出了四字哈希機(jī)制,給出了分詞詞典的結(jié)構(gòu)和分詞詞典的查找算法,提高了分詞的速度和效率。2現(xiàn)有的詞典機(jī)制2.1典中表文本設(shè)計(jì)該機(jī)制的詞典結(jié)構(gòu)分為詞典正文、詞索引表、首字散列表等三級(jí)。詞典正文是以詞為單位的有序表,詞索引表是指向詞典正文中每個(gè)詞的指針表。通過首字散列表的哈希定位和詞索引表很容易確定指定詞在詞典正文中的可能位置范圍,進(jìn)而在詞典正文中通過整詞二分進(jìn)行定位。2.2tre索引樹機(jī)制TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹?；赥RIE索引樹的分詞詞典機(jī)制由首字散列表和TRIE索引樹結(jié)點(diǎn)兩部分組成。TRIE索引樹的優(yōu)點(diǎn)是在對(duì)被切分語句的一次掃描過程中,不需預(yù)知待查詢?cè)~的長度,沿著樹鏈逐字匹配即可;缺點(diǎn)是它的構(gòu)造和維護(hù)比較復(fù)雜,而且都是單詞樹枝(一條樹枝僅代表一個(gè)詞),浪費(fèi)了一定的空間。2.3逐字第二部分分匹配這種詞典機(jī)制是前兩種機(jī)制的一種改進(jìn)方案。逐字二分與整詞二分的詞典結(jié)構(gòu)完全一樣,只是查詢過程有所區(qū)別:逐字二分吸收了TRIE索引樹的查詢優(yōu)勢,即采用的是“逐字匹配”,而不是整詞二分的“全詞匹配”,這就一定程度地提高了匹配的效率。但由于采用的仍是整詞二分的詞典結(jié)構(gòu),使效率的提高受到很大的局限。2.4查詢效率較高通過對(duì)3種分詞詞典的介紹可以看出,整詞二分和TRIE索引樹是分詞詞典機(jī)制的兩種極端。前者的數(shù)據(jù)結(jié)構(gòu)簡單、占用空間小,構(gòu)建及維護(hù)也簡單易行,但由于采用全詞匹配的查詢過程,效率低下,后者的數(shù)據(jù)結(jié)構(gòu)復(fù)雜、空間浪費(fèi)較為嚴(yán)重,樹的構(gòu)造和維護(hù)也較為繁瑣,但它采用的查詢過程是“逐字匹配”,所以查詢效率較高。第三種分詞詞典機(jī)制(基于逐字二分)雖然采用了較為高效的匹配方法――逐字匹配,但并沒有改進(jìn)“整詞二分”的數(shù)據(jù)結(jié)構(gòu),使得匹配過程并不是完全意義上的逐字匹配,這就導(dǎo)致查詢效率并沒有得到最大限度的提高。3字哈希機(jī)制文獻(xiàn)對(duì)漢語中的詞條分布進(jìn)行了統(tǒng)計(jì),具體情況見表1:由上表可以看出,中文詞語中雙字詞語最多,三字詞語和四字詞語也較多,隨著現(xiàn)代計(jì)算機(jī)硬件技術(shù)的提高,計(jì)算機(jī)內(nèi)存大、空間大,筆者覺得有必要對(duì)文獻(xiàn)雙字哈希機(jī)制擴(kuò)展到四字哈希機(jī)制,這樣可以發(fā)揮計(jì)算機(jī)內(nèi)存大空間的優(yōu)勢,最大限度的提高匹配的時(shí)間效率。3.1漢字在編碼表中的偏移量實(shí)現(xiàn)Hash算法的關(guān)鍵是有效地分配空間和實(shí)現(xiàn)Hash映射。實(shí)現(xiàn)Hash映射時(shí),詞與詞之間存在地址沖突問題,所以除分配當(dāng)前空間供Hash映射用,還要分配有備用空間,用來存放地址有沖突的詞。備用空間有兩種設(shè)置方案:一是為每個(gè)地址設(shè)置備用空間,緊隨當(dāng)前空間放置,這樣可確保有沖突時(shí),搜索的空間小、次數(shù)少,缺點(diǎn)是整個(gè)備用空間占用量大;二是同一首字下所有相同的詞分配一個(gè)備用池,這種分配法空間占用量小,但當(dāng)詞之間存在沖突時(shí),要在備用池中查找,搜索匹配次數(shù)多。漢字在計(jì)算機(jī)內(nèi)部是以內(nèi)碼的形式進(jìn)行存儲(chǔ)的,漢字內(nèi)碼是漢字在漢字信息處理系統(tǒng)中最基本的表達(dá)形式,它與漢字交換碼、漢字區(qū)位碼有一定的對(duì)應(yīng)關(guān)系。由于自定義編碼順序的特殊性,因此可以通過計(jì)算偏移量的方法來定義該漢字在編碼表中任意的位置。國標(biāo)GB2312漢字編碼表共收錄了6763個(gè)漢字,漢字在編碼表中的偏移量計(jì)算公式如下:offset=(c1-0xB0)*94+(c2-0xA1)①其中,offset代表某漢字在漢字編碼表中的位置,c1、c2分別代表漢字的內(nèi)部碼(c1代表內(nèi)部碼的高字節(jié),c2代表內(nèi)部碼的低字節(jié))。本文中的地址分配空間采用的是為每個(gè)地址設(shè)置備用空間,首字Hash索引是采用漢字內(nèi)碼來計(jì)算的。3.2單詞分類詞典的結(jié)構(gòu)四字讓字?jǐn)?shù)的個(gè)數(shù)首字Hash索引中的每個(gè)單元包括下面幾項(xiàng)內(nèi)容:(1)關(guān)鍵字:詞的第一個(gè)漢字;(2)是否為詞:標(biāo)志單個(gè)首字是否為詞;(3)2-Pre-F:是否為2字詞的前綴;(4)3-Pre-F:是否為3字詞的前綴;(5)4-Pre-F:是否為4字詞的前綴;(6)m-Pre-F:是否為多字詞的前綴;(7)次字Hash表指針;(8)以該首字為前綴的雙字詞的個(gè)數(shù);(9)三字Hash表指針;(10)以前兩字為前綴的三字詞的個(gè)數(shù);(11)四字Hash表指針;(12)以前三字為前綴的四字詞的個(gè)數(shù);(13)多字Hash表指針。兩個(gè)漢字的類型次字Hash索引中的每個(gè)單元包括下面幾項(xiàng)內(nèi)容:(1)關(guān)鍵字:詞的前兩個(gè)漢字;(2)是否為詞:標(biāo)志前兩個(gè)漢字是否為詞;(3)3-Pre-F:是否為3字詞的前綴;(4)4-Pre-F:是否為4字詞的前綴;(5)m-Pre-F:是否為多字詞的前綴;(6)三字Hash表指針;(7)以前兩字為前綴的三字詞的個(gè)數(shù);(8)四字Hash表指針;(9)以前三字為前綴的四字詞的個(gè)數(shù);(10)多字Hash表指針。前三個(gè)漢字的數(shù)和表的數(shù)字化三字Hash索引中的每個(gè)單元包括下面幾項(xiàng)內(nèi)容:(1)關(guān)鍵字:詞的前三個(gè)漢字;(2)是否為詞:標(biāo)志前三個(gè)漢字是否為詞;(3)4-Pre-F:是否為4字詞的前綴;(4)m-Pre-F:是否為多字詞的前綴;(5)四字Hash表指針;(6)以前三字為前綴的四字詞的個(gè)數(shù);(7)多字Hash表指針。近充字2字四字Hash索引中的每個(gè)單元包括下面幾項(xiàng)內(nèi)容:(1)關(guān)鍵字:詞的前四個(gè)漢字;(2)是否為詞:標(biāo)志前四個(gè)漢字是否為詞;(3)m-Pre-F:是否為多字詞的前綴;(4)多字Hash表指針。有序兩組學(xué)習(xí)剩余字串組是以前四個(gè)漢字起始的所有詞語的剩余字串有序數(shù)組,每個(gè)單元包括兩項(xiàng)內(nèi)容:(1)剩余字串:除去詞的前四個(gè)漢字的剩余部分;(2)是否為詞:標(biāo)示從第一個(gè)漢字A至對(duì)應(yīng)位置的子串是否也構(gòu)成一個(gè)詞。3.3詞典中的搜索算法由“前前字”至“前字”的產(chǎn)生,網(wǎng)“就”首先計(jì)算字串的首字在編碼表中的偏移量(即為相應(yīng)的Hash地址),如果首字前綴關(guān)系都為0,則表明此字不為任何詞的前綴,可以獨(dú)立成詞,將其切分出來。否則,增字,進(jìn)入2字詞的查找;前2字作詞切出根據(jù)首字Hash索引單元中的次字Hash表指針定位次字Hash索引單元,如果是否為詞標(biāo)志為0并且也不是其他詞的前綴(如果所有的前綴關(guān)系標(biāo)志都為0,則表明該2字詞不是其他詞的前綴),將首字切出;否則,查看相應(yīng)的成詞標(biāo)志,如果能獨(dú)立成詞,且與3字詞、4字詞和多字詞不存在前綴關(guān)系,則將字串中的前2字作為詞切出。否則,增字進(jìn)行跳躍查詢。例如:與3字詞和4字詞不構(gòu)成前綴關(guān)系,但與多字詞構(gòu)成前綴關(guān)系,則可以1次增3字進(jìn)入多字表進(jìn)行查詢。若同時(shí)與不同長度的詞構(gòu)成前綴關(guān)系,則按3字詞、4字詞和多字詞表的順序進(jìn)行查找;單元有關(guān)為0且不與其他詞的前置關(guān)系根據(jù)次字Hash索引單元中的三字Hash表指針定位四字Hash索引單元,如果是否為詞標(biāo)志為0并且也不是其他詞的前綴,則將前2字切出;否則,若前3字獨(dú)立成詞并且不與其他詞構(gòu)成前綴關(guān)系,則將前3字切出;否則,根據(jù)前綴關(guān)系標(biāo)志判斷是獨(dú)立成詞,還是進(jìn)入4字詞、多字詞的查找;4個(gè)單詞的搜索與3字詞的查找類似;由獨(dú)立成詞標(biāo)志的前5字如果在剩余字串?dāng)?shù)組中查不到,則將前4字切出;否則,如果獨(dú)立成詞標(biāo)志為0,則將前5字切出;否則,增字再次進(jìn)入多字詞的查找,直到所有的詞都被切分為止。4分詞詞典結(jié)構(gòu)設(shè)計(jì)本文首先對(duì)現(xiàn)有的中文分詞詞典機(jī)制進(jìn)行了簡單的介紹,然后在對(duì)中文編碼體系和中文詞語特點(diǎn)分析的基礎(chǔ)上,充分發(fā)揮現(xiàn)代計(jì)算機(jī)內(nèi)存大空