基于JAVA的小型中文分詞系統(tǒng)

摘要：互聯(lián)網(wǎng)信息飛速增長，網(wǎng)絡(luò)資源不斷增加，于是搜索引擎應(yīng)運(yùn)而生，它的出現(xiàn)為我們在網(wǎng)絡(luò)上搜集我們所需要的資源提供了很大的方便，但是人們并不滿足于早期的搜索引擎的功能和速度，于是搜索引擎開始不斷地被更新和完善，而分詞對于搜索引擎的更新和完善起著很重要的作用。分詞作為搜索引擎的重要組成部分，對搜索引擎的查找正確率以及查找速度具有很大的影響。它將用戶輸入的語句分割成一個個詞語和單字，這樣檢索程序就能很容易地理解用戶所需要的信息，從而為用戶返回正確且有價值的信息資料。本文通過對正向最大匹配、逆向最大匹配等分詞算法以及詞典的整詞二分、TRIE索引樹、逐字二分和雙哈希構(gòu)造方法進(jìn)行理論分析，了解各種分詞算法和詞典構(gòu)造方法的優(yōu)點(diǎn)和缺點(diǎn)，并用Java編程實(shí)現(xiàn)正向最大匹配、逆向最大匹配的分詞算法以及一維線性表、首字哈希、雙哈希三種詞典構(gòu)造方法，最終整合實(shí)現(xiàn)了Java分詞系統(tǒng)。

關(guān)鍵詞：中文分詞；詞典；最大匹配；雙哈希

中圖分類號：G642.0 文獻(xiàn)標(biāo)志碼：A 文章編號：1674-9324（2013）24-0151-04

一、緒論

對于搜索引擎來說，最重要的并不是找到所有結(jié)果，因?yàn)樵谏习賰|的網(wǎng)頁中找到所有結(jié)果沒有太多的意義，也沒有人能看得完，最重要的是把最相關(guān)的結(jié)果排在最前面，這也稱為相關(guān)度排序。中文分詞的準(zhǔn)確與否，常常直接影響到對搜索結(jié)果的相關(guān)度排序。例如在搜索引擎上輸入“和服”，得到的結(jié)果中就發(fā)現(xiàn)了下面這句話“通信信息報：卡巴斯基以技術(shù)和服務(wù)開拓網(wǎng)絡(luò)安全市場”，這就是由于分詞不準(zhǔn)確所造成的問題。從這里看到中文分詞的準(zhǔn)確度，對搜索引擎結(jié)果相關(guān)性和準(zhǔn)確性有相當(dāng)大的關(guān)系。另外，在整個搜索過程中進(jìn)場要進(jìn)行詞典的查詢，所以分詞對于搜索引擎的速度也是有影響的。

二、分詞的方法

1.分詞的意義。由于中文語句沒有自然的將詞語分開，所以計(jì)算機(jī)無法了解用戶輸入文字串的意思，我們需要將用戶輸入的內(nèi)容拆分成詞，這樣計(jì)算機(jī)才能通過詞語的比對來實(shí)現(xiàn)對信息的檢索和查找。而這個將用戶輸入文字串拆分成詞的過程就是分詞。

2.目前的分詞算法。現(xiàn)有的分詞算法可分為三大類：基于字符串匹配、基于理解和基于統(tǒng)計(jì)的分詞算法。基于字符串匹配的分詞算法又叫做機(jī)械分詞算法，它是按照一定的策略將待分析的漢字串與一個“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個字符串，則匹配成功（識別出一個詞）。常用的幾種機(jī)械分詞算法有正向最大匹配法、逆向最大匹配法、最少切分。一般說來，逆向匹配的切分精度略高于正向匹配，遇到的歧義現(xiàn)象也較少。這種分詞方法目前使用較多，我的程序也使用的是這種分詞算法。

三、分詞詞典的構(gòu)造

1.詞典的作用。為了進(jìn)行分詞，我們首先要構(gòu)建一個文本文件，這個文本文件中存放用來構(gòu)造具體的詞典所用的詞，這些詞可以通過詞典程序構(gòu)造一個詞典，再通過分詞程序的加載進(jìn)行輸入文本的分詞操作。

2.目前的幾種詞典構(gòu)造方法、簡介及優(yōu)缺點(diǎn)。目前分詞主要有以下幾種實(shí)現(xiàn)方法：整詞二分法、TRIE索引樹、逐字二分法、雙哈希算法。我最終使用的是雙哈希算法，所以我詳細(xì)介紹雙哈希算法，其他算法就不做介紹了。經(jīng)分析發(fā)現(xiàn)中文詞語中多字詞較少，利用這種情況，我們得到了如下兩種雙哈希算法：第一種是建立首字哈希索引，然后再對次字建立哈希索引，后面的字組成類似于“整詞二分”的“詞典正文”的構(gòu)造（如圖3-1）。下面我們舉例看一下雙哈希查找詞語的方法。例如查詢“吃一塹長一智MP4行業(yè)標(biāo)準(zhǔn)年底即將出臺。”中從“吃”字開始的最長詞。①首先在首字Hash索引I1中通過Hash定位得到以“吃”字開頭的索引項(xiàng)E1。②因?yàn)镋1中的“是否為詞”項(xiàng)值為“T”，所以“吃”是一個詞。再由E1的“指針”項(xiàng)得到以“吃”字開頭的所有詞的次字哈希索引I2并通過類似（1）中的查找，找到“一”字相關(guān)信息，并找到剩余字串組W。③在W中查找第一個字為“塹”的詞，得到范圍W1而后逐字搜索后續(xù)的字“長”、“一”、“智”并縮小范圍，最終得到語句S中從“吃”字開始的最長詞為“吃一塹長一智”。

第二種是先對文字長度進(jìn)行哈希索引，再進(jìn)行首字哈希索引。這個結(jié)構(gòu)類似于上面一種方法，就不做圖片和舉例介紹了。

雙哈希算法，速度雖和TRIE差不多，但是維護(hù)更為簡潔方便，所以是一種比較好的算法。

四、系統(tǒng)實(shí)現(xiàn)

1.系統(tǒng)的實(shí)現(xiàn)。為了讓看程序的人能夠一目了然，我把詞典和分詞所用到的類和接口分別放在兩個包中，他們分別建立在包processor和包dictionary中，兩個包之間通過接口聯(lián)系，在每個包中將不同的實(shí)現(xiàn)方法分別構(gòu)造自己的類文件。具體我們設(shè)置兩個包文件，我們分別在兩個包中各建立一個接口，分別為DictionaryImpl和SegmentProcessorImpl。

2.兩個包的UML圖。下面分別畫出詞典包的UML圖（圖4-1）和分詞包的UML圖（圖4-2）。

3.程序運(yùn)行效果。程序運(yùn)行環(huán)境：操作系統(tǒng)：Windows Vista JAVA環(huán)境：Java Development Kit 6.0。

WEB環(huán)境：Tomcat 5.5.20首先輸入待分詞文本：“在某些方面，Hashtable對象非常類似于ArrayList……”點(diǎn)擊進(jìn)行分詞后輸出結(jié)果：“在某些方面，hashtable，對象，非常，類似于，arraylist……”程序運(yùn)行效果圖如下（分詞前效果如圖4-3，分詞后效果如圖4-4）。

4.程序運(yùn)行效率。測試文字長度：2491字。測試效率如下：①正向最大匹配出現(xiàn)錯誤詞語26個。②逆向最大匹配出弧錯誤詞語14個。③單哈希結(jié)構(gòu)使用時間0分42.39秒。④雙哈希結(jié)構(gòu)使用時間0分18.42秒。

五、畢業(yè)設(shè)計(jì)總結(jié)

搜索引擎技術(shù)在目前越來越受到關(guān)注和重視，作為其重要組成部分的分詞技術(shù)也是目前互聯(lián)網(wǎng)研究方面的一個重要話題。通過這次對分詞技術(shù)的研究使我對分詞以及搜索引擎技術(shù)都有了很深的了解，同時也加深了我對Java語言的了解，還掌握了很多相關(guān)的知識技術(shù)，這是我離開學(xué)校前學(xué)校給我上的一堂很重要的課程，為我將從課本學(xué)到的知識運(yùn)用的實(shí)際應(yīng)用中又提供了很好的實(shí)踐經(jīng)驗(yàn)。本次設(shè)計(jì)也使我了解到自己在Java方面的不足，需要在以后多進(jìn)行編程練習(xí)。

致謝：在我的畢業(yè)設(shè)計(jì)過程中，我的指導(dǎo)老師趙洋和劉博老師對我的畢業(yè)設(shè)計(jì)有很大的幫助。他們幫我分析設(shè)計(jì)思路，幫我找參考資料，耐心解答我在查看資料中遇到的不懂的問題，還幫助我完善程序。他們的耐心講解以及嚴(yán)格要求為我順利地完成我的畢業(yè)設(shè)計(jì)鋪平了道路。同時，學(xué)校給提供的良好的設(shè)計(jì)環(huán)境以及同學(xué)之間的互相幫助也為我能夠順利完成畢業(yè)設(shè)計(jì)提供了很好的支持。在此向我的輔導(dǎo)老師趙洋和劉博老師，以及在畢業(yè)設(shè)中幫助我的老師和同學(xué)表示衷心的感謝，同時也衷心感謝學(xué)校給我提供這次有意義的實(shí)踐機(jī)會，為我成功地步入社會增加了寶貴的經(jīng)驗(yàn)。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2003.

[2]耿祥義，張躍平.JAVA2實(shí)用教程（修訂）[M].北京：清華大學(xué)出版社，2003.

[3]Thomas H.Cormen，Charles E.Leiserson，Ronald L.Rivest，Clifferd Stein.Introduction to Algorithms（Second Edition）[M].Americon：The Massachusetts Institute of Technology，2001.

[4]李江波，周強(qiáng)，陳祖舜.漢語詞典的快速查詢算法研究[J].中文信息學(xué)報，200，20：31.

[5]孫茂松，左正平，黃昌寧.漢語自動分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報，1999，14：1.

[6]李慶虎，陳玉健，孫家廣.一種中文分詞詞典新機(jī)制——雙字哈希機(jī)制[J].中文信息學(xué)報，2002，17：13.

[7]陳小荷.自動分詞中未登錄詞問題的一攬子解決方案[J].語言文字應(yīng)用，1999，31：103.