一種中文分詞詞典存儲(chǔ)機(jī)制

一種中文分詞詞典存儲(chǔ)機(jī)制

如果中文文本在書(shū)面表達(dá)或計(jì)算機(jī)內(nèi)顯示，則該詞與詞、詞和詞之間沒(méi)有明顯的分布標(biāo)志。對(duì)于一句話(huà)，人可以通過(guò)自己的知識(shí)來(lái)得到哪些是詞，但如何讓計(jì)算機(jī)也能做到這一點(diǎn)，就是中文分詞算法的目的。中文分詞是中文信息處理的基礎(chǔ)，在諸多領(lǐng)域起著至關(guān)重要的作用，例如，機(jī)器翻譯、文本檢索、搜索引擎、自動(dòng)文摘等很多應(yīng)用都需要以中文分詞結(jié)果作為基礎(chǔ)。一個(gè)中文分詞算法的好壞，會(huì)對(duì)其后續(xù)的應(yīng)用產(chǎn)生極大的影響?，F(xiàn)有的分詞算法，基本上可以分為三種：機(jī)械式分詞、理解式分詞、統(tǒng)計(jì)式分詞。在這三種算法中，機(jī)械式分詞的準(zhǔn)確率最高，對(duì)于機(jī)械式分詞，需要一部詞典作為后臺(tái)依據(jù)，簡(jiǎn)單的說(shuō)是通過(guò)將文檔中的漢字串與字典中的詞相匹配來(lái)完成詞的切分。這是一種基于字符串匹配的分詞方法，它是按照一定的策略將待分析的漢字串與一個(gè)（充分大的）機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功（識(shí)別出一個(gè)詞）。按照對(duì)文本串的掃描方向的不同，機(jī)械分詞方法可以分為正向匹配和逆向匹配；按照不同長(zhǎng)度優(yōu)先匹配的情況，可以分為最大（最長(zhǎng)）匹配（MaximumMatchingMethod，簡(jiǎn)稱(chēng)MM法）和最?。ㄗ疃蹋┢ヅ?。正向最大匹配算法的原則是切分出來(lái)的詞越長(zhǎng)越好。因?yàn)樵~越長(zhǎng)，包含的信息量就越大。機(jī)械式分詞算法之所以成為“機(jī)械”，是因?yàn)檫@種算法沒(méi)有考慮任何語(yǔ)法及語(yǔ)義問(wèn)題，而是單純的，機(jī)械式的將文本與詞典中的詞相匹配。由此可以看出詞典所含詞匯量的大小將決定分詞精度的好壞。由于很多機(jī)構(gòu)已經(jīng)構(gòu)造出了極為豐富的詞典所以在這點(diǎn)上基本上已沒(méi)有改進(jìn)的余地。由于機(jī)械式分詞是基于字符串匹配的。所以詞典的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)和匹配算法的好壞將會(huì)直接影響該算法的時(shí)間和空間復(fù)雜度。1分詞詞典的存儲(chǔ)結(jié)構(gòu)想要提高機(jī)械式分詞算法的執(zhí)行效率，就要降低匹配算法的時(shí)間復(fù)雜度，而一個(gè)匹配算法的時(shí)間復(fù)雜度，從很大程度上取決于匹配數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。在機(jī)械式分詞算法中，最重要的就是分詞詞典的存儲(chǔ)結(jié)構(gòu)。下面介紹幾種傳統(tǒng)的分詞詞典機(jī)制：(1）詞典信息編碼該詞典的存儲(chǔ)機(jī)制把詞典分為詞典正文、詞索引表、首字Hash表等三級(jí)。詞典正文是以詞為單位的線(xiàn)性表，詞索引表是指向詞典正文中每個(gè)詞的指針表。通過(guò)首字Hash表的散列函數(shù)和詞索引表很容易確定指定詞在詞典正文中的可能位置范圍，進(jìn)而在詞典正文中通過(guò)整詞二分進(jìn)行定位。(2）tre索引樹(shù)節(jié)點(diǎn)TRIE索引樹(shù)是一種以多重鏈表形式表示的鍵樹(shù)?；赥RIE索引樹(shù)的分詞詞典機(jī)制有首字散列表和TRIE索引樹(shù)節(jié)點(diǎn)兩部分組成。TRIE索引樹(shù)的優(yōu)點(diǎn)是在對(duì)被切分語(yǔ)句的一次掃描過(guò)程中，不需預(yù)知待查詢(xún)?cè)~的長(zhǎng)度，沿著樹(shù)鏈逐字匹配即可；缺點(diǎn)是它的構(gòu)造和維護(hù)比較復(fù)雜，而且都是單詞樹(shù)枝（一條樹(shù)枝僅代表一個(gè)詞），浪費(fèi)了一定的空間。(3）逐字第二，從整體匹配到全詞匹配這種詞典機(jī)制是前兩種機(jī)制的一種改進(jìn)方案。逐字二分與整詞二分的詞典機(jī)構(gòu)完全一樣，只是查詢(xún)過(guò)程有所區(qū)別：逐字二分吸收了TRIE索引樹(shù)的查詢(xún)優(yōu)勢(shì)，即采用的是“逐字匹配”，而不是整詞二分的“全詞匹配”，這就一定程度地提高了匹配的效率。但由于采用的仍是整詞二分的詞典結(jié)構(gòu)，使效率的提高面臨很大的局限。2基于一級(jí)索引的發(fā)現(xiàn)在上一章介紹了幾種傳統(tǒng)的分詞詞典機(jī)制，通過(guò)介紹，可以了解到已有的詞典機(jī)制都存在很明顯的優(yōu)缺點(diǎn)。對(duì)于基于整詞二分的詞典機(jī)制，詞典結(jié)構(gòu)簡(jiǎn)單，維護(hù)容易，但由于采用的是全詞匹配，所以速度較慢。而對(duì)于TRIE樹(shù)，采用逐字匹配，速度較快，但詞典的存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)復(fù)雜，較難維護(hù)。而對(duì)于第三種相當(dāng)于兩種算法的折中，對(duì)兩種算法的優(yōu)點(diǎn)都不能全部發(fā)揮。為了最大程度的提高算法的匹配效率和詞典的可維護(hù)性。設(shè)計(jì)了一種新的分詞詞典存儲(chǔ)結(jié)構(gòu)—基于二級(jí)索引的分詞詞典。在檢測(cè)以某一個(gè)漢字開(kāi)始的漢字串是否是一個(gè)詞的時(shí)候，算法的工作是檢測(cè)在詞典中是否有以該漢字開(kāi)始的詞條與此漢字串相同，如果有則就是詞。算法的關(guān)鍵在與怎么才能迅速實(shí)現(xiàn)判定。為了迅速定位以某一個(gè)漢字開(kāi)始的所有詞條首先為首漢字建立索引。這里利用漢字的機(jī)內(nèi)碼和區(qū)位碼相互關(guān)系，根據(jù)轉(zhuǎn)換公式：內(nèi)碼高位=區(qū)碼+A0H(H表示十六進(jìn)制）內(nèi)碼低位=位碼+A0H很容易將一個(gè)漢字的機(jī)內(nèi)碼轉(zhuǎn)換為區(qū)位碼，而在將區(qū)位碼轉(zhuǎn)換為十進(jìn)制表示。例如“中”字的最終轉(zhuǎn)換結(jié)果為十進(jìn)制“5448”，由于漢字的區(qū)位碼最大為“8794”，所以可以用一個(gè)固定的結(jié)構(gòu)體數(shù)組來(lái)存儲(chǔ)這第一級(jí)索引。例如該數(shù)組的第5448項(xiàng)（第0項(xiàng)不用），里面存儲(chǔ)的就是所有以“中”開(kāi)頭的詞條的存儲(chǔ)位置的頭指針，當(dāng)然如果某一個(gè)漢字不能組詞，則該指針為空。這樣已知一個(gè)漢字串的首字就可以在復(fù)雜度O(1）的時(shí)間里定位到以該漢字開(kāi)始的詞條。這是詞典的第一級(jí)索引。經(jīng)過(guò)一級(jí)索引可以將時(shí)間復(fù)雜度大大地降低，但是文獻(xiàn)對(duì)漢語(yǔ)中的詞條分布進(jìn)行了統(tǒng)計(jì)，具體情況見(jiàn)表1。由統(tǒng)計(jì)結(jié)果可以看出漢語(yǔ)中雙字詞較多，而三字、四字次之，其他詞較少。經(jīng)過(guò)為詞典建立的一級(jí)索引后，由于二字詞較多，例如以“中”字開(kāi)始的二字詞就有100多個(gè)，這樣如果順序匹配的話(huà)，仍然會(huì)花費(fèi)很多的時(shí)間，所以在一級(jí)索引的基礎(chǔ)上，在為分詞詞典建立一個(gè)二級(jí)索引。由于詞的第二個(gè)漢字分布的不確定性，利用第一級(jí)索引的方法是不現(xiàn)實(shí)的，所以建立二級(jí)索引是本文采用除留余數(shù)的Hash方法來(lái)記錄不同的詞條存儲(chǔ)位置。Hash函數(shù)為：其中ch1,ch2為漢字機(jī)內(nèi)碼的高、低字節(jié)。length代表以某一首漢字開(kāi)始的詞條的個(gè)數(shù)。既然是散列函數(shù)，就有可能出現(xiàn)沖突，在解決沖突方面采用了鏈地址法，即如果有兩個(gè)以上的詞有相同的Hash值，則分別將其鏈在一起。當(dāng)然，利用上述建立索引的方法可以為詞典建立三級(jí)，甚至四級(jí)索引，但是考慮到漢語(yǔ)中三字、四字等詞比較少，而且以相同的兩個(gè)漢字開(kāi)始的多字（三字及以上）詞較少，所以沒(méi)有必要建立更多級(jí)的索引。經(jīng)過(guò)二級(jí)索引，很容易就能夠識(shí)別二字詞，由于在漢語(yǔ)中二字詞較多，所以這大大提高了匹配速度。但在匹配過(guò)程中不可避免會(huì)遇到三字詞或更長(zhǎng)的詞，而且也說(shuō)過(guò)沒(méi)有必要再建立更多的索引，為了進(jìn)一步提高匹配的速度，對(duì)除去前兩個(gè)漢字的剩下串按升序排列，這種存儲(chǔ)結(jié)構(gòu)的優(yōu)勢(shì)在匹配時(shí)將會(huì)見(jiàn)到。為了節(jié)省存儲(chǔ)空間經(jīng)過(guò)兩次索引之后，在詞的存儲(chǔ)過(guò)程中，只存儲(chǔ)剩下的詞，例如在下面給出的例子中“中心匯率”這個(gè)詞時(shí)，其實(shí)在正文詞典里只存儲(chǔ)了“匯率”這個(gè)詞，而其首字和次字可以在匹配過(guò)程中自動(dòng)得到，無(wú)需存儲(chǔ)，這從很大程度上節(jié)省了內(nèi)存空間（為了提高匹配速度，詞典常駐內(nèi)存）。介紹完詞典的存儲(chǔ)機(jī)制，下面簡(jiǎn)要介紹一下基于該分詞詞典的正向最大匹配算法。例如匹配“我不知道中心詞是什么”，現(xiàn)在從“中”字開(kāi)始進(jìn)行正向最大切分，(1）根據(jù)首漢字“中”的區(qū)位碼“5448”作為首字索引表的下表得到其索引結(jié)構(gòu)體。(2）由于結(jié)構(gòu)體中的次字索引表基指針base不為空，說(shuō)明可以繼續(xù)匹配漢字串，則根據(jù)base找到以“中”開(kāi)始的次字索引表。(3）通過(guò)Hash（“心”），求出次字為“心”的所有詞的索引項(xiàng)在次字Hash表的偏移量offset，根據(jù)base+offset求出以“中心”開(kāi)始的所有詞的存儲(chǔ)位置的頭指針，當(dāng)然在這一過(guò)程中，需要解決Hash值的沖突問(wèn)題。在本例中不存在這一問(wèn)題。(4）在剩下的串中采取臨近匹配算法，這就是要把剩余漢字按升序排列的原因。理由是，在找到某個(gè)字符串后，在其后增加一個(gè)字得到一新字串，如果新字串在詞典中出現(xiàn)，那么新詞一定在原字串的后面，且相隔不會(huì)太遠(yuǎn)。最終匹配出“中心詞”。詞典的存儲(chǔ)機(jī)制及示例的匹配過(guò)程如圖1所示。3實(shí)驗(yàn)數(shù)據(jù)及分析根據(jù)以上敘述的理論，用VC++6.0實(shí)現(xiàn)一個(gè)中文分詞系統(tǒng)。并在AMD2600+，512M內(nèi)存的情況下對(duì)本系統(tǒng)和沒(méi)有改進(jìn)前的系統(tǒng)做了比較，輸入文本統(tǒng)一采用1M網(wǎng)頁(yè)，用正向最大匹配算法切分。實(shí)驗(yàn)數(shù)據(jù)如表2所示。從表2可以看出，分詞詞典索引對(duì)于分詞算法的好壞有著很大的影響。如果不加索引則每次都要匹配詞典里所有的詞，切分速度非常慢。本文所設(shè)計(jì)的詞典為詞典加了兩級(jí)索引，并且為兩級(jí)索引以后的漢字采用了臨近匹配算法，最大程度上避免了全詞匹配。由于在漢語(yǔ)中二字詞占大多數(shù)，而在本文所設(shè)計(jì)的詞典中所有的二字詞