一種改進(jìn)的基于patricia樹的漢語自動(dòng)分詞詞典機(jī)制

《一種改進(jìn)的基于patricia樹的漢語自動(dòng)分詞詞典機(jī)制》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、萬方數(shù)據(jù)華南理工大學(xué)學(xué)報(bào)(自然料擘版)第32卷增刊JournalofSoulbChinaUniVersityofTechn0109yvol32suppl2004年11月(NamralscienceEdmon)November2004文章編號(hào)：lD00—565x(2004)s—0028—04一種改進(jìn)的基于PATⅪcIA樹的漢語自動(dòng)分詞詞典機(jī)制+馬哲(浙旺大學(xué)計(jì)算機(jī)系，姚敏浙江杭州310027)摘要：分詞詞典機(jī)制是影響自動(dòng)分詞的重要因素，而查找速度是衡量一個(gè)詞典好壞的重要標(biāo)準(zhǔn)．吏中分析比較了現(xiàn)有的幾種典型的詞典機(jī)制．井在此基礎(chǔ)上提

2、出了一種新的詞典機(jī)制，即在pATRfc認(rèn)tree的基礎(chǔ)上加入Hash機(jī)制，從而在明顯提高查找速度的同時(shí)，降低了構(gòu)造和維護(hù)詞典的復(fù)雜度．關(guān)鍵詞：PATRIcIA樹；漢語；自動(dòng)分詞；分詞詞典機(jī)制中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A漢語的自動(dòng)分詞技術(shù)的應(yīng)用十分廣泛，如漢字的拼音輸入、語音識(shí)別與合成、漢語分析與理解、中文句法分析、機(jī)器翻澤、中文文獻(xiàn)自動(dòng)標(biāo)引、中文信息檢索等等．分詞技術(shù)的研究已有10多年的歷史，取得了很大的進(jìn)展．分詞方法主要分為基于統(tǒng)計(jì)的機(jī)械分詞法和基于規(guī)則的專家系統(tǒng)分詞法．無論哪種方法，其最終目的都是快速精確地取得分詞

3、結(jié)果．詞典作為許多分詞方法的重要工具，它的查詢速度是制約分詞速度的決定因素，又因?yàn)闆]有任何一個(gè)詞典所收錄的詞是完備的，所以詞典應(yīng)該易于進(jìn)行添加刪除等維護(hù)工作．所以～個(gè)好的詞媳機(jī)制應(yīng)能提供快速查詢，并且便于維護(hù)．根據(jù)分詞系統(tǒng)特點(diǎn)，分詞詞典的查詢方式大致分為三種．(1)確定詞條查詢：在分詞詞典中查找指定詞w。(詞在分詞詞典中的定位)．(2)最長詞條查詢：根據(jù)分詞詞典，在漢字串s中查找從某一指定位置f開始的最長詞w?。(對應(yīng)最大匹配分詞方法)．(3)前綴詞條查詢：根據(jù)分詞詞典，在漢字串s中查找從某一指定位置f開始的所有詞w。，w。，

4、收稿日期：2004—08—24·基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(79970037)作著簡介：馬哲(1980一)，女，碩士生，主要從事數(shù)據(jù)挖掘和模糊信息處理的研究E·mail：mz·fcidan@sohu．com?，w。。。(對應(yīng)全切分分詞方法)l現(xiàn)有分詞機(jī)制分析1．1基于Hash機(jī)制的分詞詞典機(jī)制(I)首字HaSh+索引表+整詞二分機(jī)制，首字H“h+索引表+逐字二分機(jī)制”1．這齷種機(jī)制都是基于首字Hash+索引表．前～種分詞機(jī)制比較適合確定詞條查詢，但是對于最長詞條和前綴詞條查詢，其性能卻不佳．后一種分詞機(jī)制是在前一種上的

5、改進(jìn)，吸取了基于TRIE的逐字比較的優(yōu)勢，對于最長和前綴詞條查詢方式有較大改善．這兩種機(jī)制的優(yōu)點(diǎn)是構(gòu)造和維護(hù)簡單，占用空間?。?2)首字Hash+TRIE索引樹?機(jī)制，雙字Hash+TRlE索弓I樹”l，首字Hash+語詞樹”1機(jī)制這三種都是基于Hash+鍵樹機(jī)制．鍵樹”1，又稱數(shù)字查找樹，它是一棵度大于或等于2的樹，樹中的每個(gè)節(jié)點(diǎn)中不是包含一個(gè)或幾個(gè)關(guān)鍵詞．而是只含有組成關(guān)鍵詞的符號(hào)．鍵樹有兩種存儲(chǔ)結(jié)構(gòu)，一種是以樹的孩子兄弟鏈表來表示鍵樹，應(yīng)用于詞典中即為語詞樹；另一種是以樹的多重鏈表來表示鍵樹，即TRIE樹．這三種機(jī)制的好

6、處是查詢速度快，但是數(shù)據(jù)結(jié)構(gòu)復(fù)雜，浪費(fèi)空間較大，J．2基于PATRIcIA樹的詞典機(jī)制”1PATRIcIA(Prac石calAlgorithmtoRetrieveIn-萬方數(shù)據(jù)萬方數(shù)據(jù)萬方數(shù)據(jù)增刊馬哲等：～種改進(jìn)的基于PATRIcIA樹的漢語自動(dòng)分詞詞典機(jī)制3l圉3添加關(guān)鍵誦Fig．3Insenk。ywords凰4刪除關(guān)鍵詞升g4DeIetekeyword83基于首字Hash與PATRIcIAtree的分詞詞典機(jī)制的性能分析31空間特性與原來的PATRIcIAtree機(jī)制相比較。新機(jī)制擺當(dāng)于把原來的～棵龐大的PATRIcIA仃

7、ee拆分為許多相對較小的PATRIcIAtree，由于詞條數(shù)目不變，則內(nèi)部節(jié)點(diǎn)數(shù)目不變，相當(dāng)于增加了一個(gè)Hash散列表的空間．新機(jī)制所占的空間為Hash散列表+內(nèi)部節(jié)點(diǎn)+葉子節(jié)點(diǎn)．3．2平均路徑長度在進(jìn)行查找時(shí)，Hash散列表和將進(jìn)行查詢的PATRIclA仳e都在內(nèi)存中，不用進(jìn)行I／O操作，比原PATRIclAtree機(jī)制的時(shí)間復(fù)雜度降低很多，(I)查找單字詞無需比較；(2)根據(jù)文獻(xiàn)[2】得到的統(tǒng)計(jì)結(jié)果，如表1所示．由于新機(jī)制查詢詞條相當(dāng)于比原機(jī)制少查找一個(gè)字，所以相應(yīng)的平均路徑長度普遍下降．即查找三字詞相當(dāng)于查找二字詞．則原

8、機(jī)制的平均路徑長為21．94，而新機(jī)制的平均路徑長約為1728，比最理想的log：77228m16．24次多1次，比原機(jī)制有很大改善．表1不同長度關(guān)鍵詞的平均路徑長度Table1AVaragepathlengthofdifferentkeywords(3)同理進(jìn)行最長字串查詢