基于Hash機(jī)制的分詞詞典的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、中文作為人類(lèi)傳播信息的重要語(yǔ)言工具之一，中文信息處理已經(jīng)成為信息處理領(lǐng)域的熱點(diǎn)研究問(wèn)題。中文自動(dòng)分詞是中文信息處理的重要組成部分，而詞典處理效率是影響中文自動(dòng)分詞系統(tǒng)性能的關(guān)鍵因素，因此，建立高效的分詞詞典具有顯著的意義。本文對(duì)中文分詞系統(tǒng)的詞典結(jié)構(gòu)進(jìn)行了深入研究，取得了一定研究成果，已用于國(guó)家863項(xiàng)目中的垃圾短信監(jiān)管處理，并將設(shè)計(jì)的算法申請(qǐng)?zhí)峤涣讼嚓P(guān)專利，主要研究成果如下： 1.比較分析并改進(jìn)了幾種的詞典存儲(chǔ)和處理方法：數(shù)組

2、-數(shù)組機(jī)制使用數(shù)組存儲(chǔ)詞條行，采用二分查找，在操作效率上不高，不利于詞典的更新；雙字哈希對(duì)前詞條兩個(gè)字哈希，使用深度為2的TRIE樹(shù)，結(jié)構(gòu)復(fù)雜；四字哈希機(jī)制只對(duì)四字成語(yǔ)有效，在應(yīng)用上有局限性。本文對(duì)這些方法作一定的改進(jìn)來(lái)解決效率問(wèn)題。 2.根據(jù)漢字GB碼的特點(diǎn)，提出了一種比較高效的詞典存儲(chǔ)算法，將相同首字的詞條作為一個(gè)文本行進(jìn)行存儲(chǔ)，而每個(gè)詞條格式化為：去掉首字詞條名、詞條哈希值和相關(guān)屬性，提高了存儲(chǔ)空間利用率。 3.利

3、用Hash表在查找效率上優(yōu)勢(shì)，提出了基于Hash機(jī)制的詞典查找、更新、刪除、添加等操作新算法。設(shè)計(jì)一個(gè)實(shí)用的Hash函數(shù)，經(jīng)實(shí)驗(yàn)驗(yàn)證沖突率極小，適合中小型詞典，通過(guò)將該函數(shù)改進(jìn)為適合大型詞典的無(wú)沖突Hash函數(shù)。 4.實(shí)現(xiàn)數(shù)組、鏈表、AVL樹(shù)、Hash表(帶極小沖突和無(wú)沖突兩種)五種詞典結(jié)構(gòu)算法，對(duì)這些算法從時(shí)間復(fù)雜度和空間復(fù)雜度等方面進(jìn)行詳細(xì)的分析和評(píng)估，從載入、寫(xiě)出、文件大小和操作時(shí)間等幾個(gè)方面進(jìn)行實(shí)驗(yàn)對(duì)比，驗(yàn)證了基于Has