計算機畢設(shè)——中文分詞方法研究與實現(xiàn)
畢業(yè)論文
中文分詞方法研究與實現(xiàn)
1．課題意義及目標(biāo)
中文分詞技術(shù)不斷發(fā)展，各種中文分詞系統(tǒng)層出不窮。中文分詞技術(shù)應(yīng)用也原來越廣泛。如搜索引擎的應(yīng)用、語音識別系統(tǒng)、機器翻譯、自動分類校對等。學(xué)生應(yīng)通過本次畢業(yè)設(shè)計，綜合運用所學(xué)過的基礎(chǔ)理論知識，深入中了解文分詞技術(shù)，為學(xué)生在畢業(yè)后相關(guān)工作打好基礎(chǔ)。
2．主要任務(wù)
研究常見的幾種分詞方法，闡述其原理、優(yōu)缺點。
著重研究正向最大分詞的原理，得出相關(guān)結(jié)論。
根據(jù)最大分詞方法做出相應(yīng)程序來實現(xiàn)對若干句子的分詞，在記事本（或Word）中顯示出來并比較幾種分詞方法的優(yōu)缺點。
3．主要參考資料
[1] 宗成慶.統(tǒng)計自然語言處理[M].北京：清華大學(xué)出版社.2008：105-143．
[2] 劉件,魏程. 中文分詞算法研究[J]. 微計算機應(yīng)用. 2008, 29(8): 11-16.
[3] 崔彥翔.基于條件隨機場的網(wǎng)絡(luò)研究[D].大連:大連理工大學(xué),2013.
4．進(jìn)度安排
摘 要
本畢業(yè)設(shè)計主要對幾種常見的中文分詞算法的切分結(jié)果進(jìn)行了研究對比。闡述了分詞算法的原理，著重研究了正向最大分詞的原理，分析了分詞算法的思想、數(shù)學(xué)模型及算法的實現(xiàn)。在以上分析研究的基礎(chǔ)上，本畢業(yè)設(shè)計基于機械分詞算法，結(jié)合了N-Gram模型在前人研究的基礎(chǔ)上采用JAVA程序設(shè)計語言，結(jié)合更加優(yōu)良的存儲和匹配方法，設(shè)計出相應(yīng)的分詞程序，最終實現(xiàn)了對若干句子的分詞，并在文本文檔中顯示出切分結(jié)果。同時相應(yīng)的提高了中文分詞的效率和正確率。
本畢業(yè)設(shè)計采用了先進(jìn)的軟件工程的設(shè)計方法，通過研究分析，使用概要設(shè)計、詳細(xì)設(shè)計的方法，運用JAVA程序開發(fā)語言等技術(shù)手段，進(jìn)行了系統(tǒng)化的設(shè)計與實現(xiàn)。本文的最后對本次設(shè)計及論文進(jìn)行了總結(jié)，提出了需要改進(jìn)之處并展望了中文分詞算法的美好前景及應(yīng)用。
關(guān)鍵字：中文分詞，正確率，機械分詞算法，JAVA語言
The Research and Implementation of Chinese Word Segmentation Algorithm
Abstract
The article researched the different of the common types of the results of the Chinese word segmentation ,and illustrated algorithm,especially the principle of forward maximum matching method,what’s more,this article has also analyzed the theory of segmentation algorithm,also the realization of mathematical model and the algorithm has been studied.What’s more,based on the mechanical word segmentation,the paper used the N-gram model,the Java program language,finally realize the segmentation of have been improved.
In a word,by using the advanced design method of software engineering,basically achieved the good of the design and the realization of the system.Besides,I also used the outline design,the detailed design and the Java?http://technology.In?the end of this paper,the needed improvements of the Chinese word segmentation has been pointed out,also presented the prospect and the application of this advanced segmentation.
Keywords :Chinese word segmentation, mechanical segmentation,accuracy,JAVA language
目 錄
1 緒論11
1.1 研究背景11
1.2 研究現(xiàn)狀22
1.3 研究目的及意義22
1.4 設(shè)計思路及實現(xiàn)技術(shù)33
2 中文分詞方法研究44
2.1 中文分詞的概述44
2.2 中文分詞常用算法44
2.2.1 基于詞典的分詞方法44
2.2.2 基于統(tǒng)計的分詞方法66
2.2.3 基于理解的分詞方法77
2.3 中文分詞的難點77
2.3.1 歧義識別77
2.3.2 新詞識別88
2.4 基于詞典的正向最大匹配研究88
2.4.1 算法思想88
2.4.2 正向最大匹配算法實現(xiàn)原理1010
2.4.3 N-Gram數(shù)學(xué)模型1111
2.4.4 Trie樹結(jié)構(gòu)1111
2.4.5 Trie樹與其他結(jié)構(gòu)的比較1313
3 需求分析1515
3.1 可行性分析1515
3.2 中文分詞系統(tǒng)目標(biāo)的分析1515
3.3 系統(tǒng)功能需求分析1616
4 系統(tǒng)的設(shè)計1717
4.1 整體設(shè)計1717
4.2 分詞系統(tǒng)處理流程1818
4.3 系統(tǒng)的詳細(xì)設(shè)計1919
5 系統(tǒng)實現(xiàn)2222
5.1 分詞功能實現(xiàn)2222
5.1.1 優(yōu)化的分詞功能的實現(xiàn)2222
5.1.2 添加分詞算法的實現(xiàn)2424
5.2 顯示功能2525
5.3 時間與內(nèi)存顯示功能2626
6 系統(tǒng)測試2828
6.1 分詞及顯示功能測試2828
6.2 切分時間及內(nèi)存顯示測試3030
6.3 測試結(jié)果分析3131
7 結(jié)論3232
參考文獻(xiàn)3333
致謝3434
緒論
研究背景
詞作為微小的語言成分，在日常的生活中可以獨立活動且具有實際意義。在五千年文化的積淀下，形成了相應(yīng)的漢語書寫習(xí)慣：漢語句子中詞與詞之間沒有明確的自然分界符。中文與被廣泛使用的英語相比，中文沒有明顯的空格來區(qū)分詞與詞之間的具體含義。中文區(qū)分詞義的明顯標(biāo)識是句子之間的符號（如：頓號、逗號、分號、句號等）以及段落與段落之間的重新分割。中文的這些分界標(biāo)識并不能作為中文詞與詞之間的自然分割符來切分文本。換句話說，從形式上來看中文雖然以字為最基本的書寫單位，但單個字卻不能像英文那樣作為詞的單位。如：用英語表達(dá)一句話，I want to go my home.漢語的表達(dá)方式為：我想回我家。我們可以輕易的將用英語表達(dá)的句子詞義通過空格來區(qū)分：I/want/go/my/home 。而同樣的意思在漢語的表達(dá)語句中我們卻不能明顯的通過自然分界符來區(qū)分詞與詞之間的意思?！拔蚁牖匚壹摇卑凑照_的理解可將其劃分為：我想回/我家。我們之所以能夠正確的劃分漢語中的詞義是因為我們具有思維，而電腦等機器是不像人類一樣具有思維的，它們不能用也不會用人類的思維方式將漢語語料進(jìn)行正確的劃分。由于中文中詞和詞語的邊界如此模糊，因此，通常在處理中文語言時，首先處理的是中文文本中的句子，“將句子中的字序列先切分為一個一個的詞序列，之后再對切分出來的次序列進(jìn)行整合分析處理，從而將中文文本的具體含義、關(guān)鍵詞提取出來。[1]”同時，中文分詞涉及到計算機科學(xué)、數(shù)學(xué)、漢語言學(xué)數(shù)學(xué)三大領(lǐng)域運用了語用學(xué)、語義學(xué)的知識。
隨著科學(xué)技術(shù)的進(jìn)步，電腦的普及以及互聯(lián)網(wǎng)的快速發(fā)展，使用網(wǎng)絡(luò)來瀏覽新聞、查閱資料等等行為看似普通卻成為人們?nèi)粘Ｉ钪斜夭豢缮俚囊粋€環(huán)節(jié)。論文的查重、關(guān)鍵字的提取、機器翻譯、語音識別自動摘要、漢字的智能輸入等等越來越多的領(lǐng)域、技術(shù)都需要用到中文分詞這一核心性、基礎(chǔ)性的算法、技術(shù)、系統(tǒng)。
“20世紀(jì)80年代初，自動分詞在中文信息處理領(lǐng)域中被提出，從此，研究相關(guān)方面的眾多專家學(xué)者、科研院所、[2]”商業(yè)機構(gòu)便深入研究實踐中文的自動分詞，在大家的不懈努力下，中文自動分詞在中文系息處理領(lǐng)域甚至其他領(lǐng)域取得了一些重要的進(jìn)展和一些實用性的成果，而且有些成熟的技術(shù)已經(jīng)應(yīng)用于產(chǎn)品當(dāng)中。隨之相適應(yīng)的即為各種中文分詞方法的產(chǎn)生。根據(jù)唯物主義可知，只有運動是絕對的，中文分詞方法也必然是具有前進(jìn)行的，不是完美無缺的，也存在著不足。研究現(xiàn)狀
“中文分詞的研究起始于二十世紀(jì)八十年代左右，八十年代初期，我國在中文自動分詞方面取得了初步的進(jìn)展，與此同時，國內(nèi)的學(xué)者也開始對中文分類自動引標(biāo)技術(shù)的逐步進(jìn)行深入的研究。[3]”1983年北京航天航空大學(xué)梁南元副教授采用主輔結(jié)合，輔助以詞尾字構(gòu)詞糾錯技術(shù)完成并實現(xiàn)了第一個漢語自動分詞系統(tǒng) CDWS( The Modern Printed Chinese Distinguishing Word System)，該系統(tǒng)采用了基于詞典的最大匹配算法，能夠?qū)?500萬字的現(xiàn)代漢語詞頻進(jìn)行統(tǒng)計工作，切分精度約為1/625，基本滿足了詞頻統(tǒng)計及其他一些應(yīng)用的需要。 此后許多科研院校相繼研發(fā)出許多分詞系統(tǒng)：“清華大學(xué)早期研制的SEG分詞系統(tǒng)提出了全切分的概念、[4]”“清華大學(xué)SEGTAG分詞系統(tǒng)著眼于將各種各類的信息進(jìn)行綜合從而提高了切分精讀、復(fù)旦大學(xué)的分詞系統(tǒng)、[5]”山西大學(xué)計算機系研制的ABWS系統(tǒng)、微軟研究院的自然語言研究所研究開發(fā)的能夠處理多國語言的Microsoft Research語法分析器即NLPWwin語法分析器分詞系統(tǒng)、1988年北京航空航天大學(xué)實現(xiàn)的CASS分詞系統(tǒng)哈爾濱工業(yè)大學(xué)研究的基于統(tǒng)計分詞純切詞的統(tǒng)計分詞系統(tǒng)、中國科學(xué)院計算技術(shù)研究所開發(fā)的在973專家組測評中獲得第一名的ICTCLAS漢語分詞系統(tǒng)?，F(xiàn)如今，已經(jīng)可以通過對中文語義所體現(xiàn)的關(guān)鍵詞進(jìn)行自動的提取及篩選，從而實現(xiàn)了語義的自動分離引標(biāo)。
“國外對中文分詞技術(shù)的相關(guān)研究大概也是從1980年初開始的，國外對中文分詞技術(shù)的研究的大致方向是中文分詞技術(shù)的應(yīng)用和評測，國外對中文分詞技術(shù)的研究大多是介紹自動分詞在信息檢索、漢字處理、語音處理、內(nèi)容識別與分析、自然語言理解等方面的應(yīng)用。[6]”同時也相應(yīng)的闡釋了中文分的詞難點及其在信息檢索中的應(yīng)用。國外也有少部分專門針對分詞技術(shù)做研究。Fu lee Wang 采用數(shù)據(jù)庫挖掘的方法解決了中文分詞問題，提出了一種新的分詞規(guī)則，從一方面提高了分詞的效率及準(zhǔn)確率。研究目的及意義
在日常生活工作中，我們可以發(fā)現(xiàn)網(wǎng)站、網(wǎng)頁等信息英文居多，利用互聯(lián)網(wǎng)進(jìn)行信息檢索時英文的檢索要比中文的檢索效率高一些。造成這種結(jié)果的主要原因除了英語是通用的的語言之外，最重要的一個原因是英文不需要分詞即英文在詞的利用上具有先天性的優(yōu)勢，而中文則需要進(jìn)行分詞這一關(guān)鍵性步驟。所以研究中文分詞是非常有必要的，具有非常重要的意義，對個體來說，可以節(jié)約時間從而提高效率；對于企業(yè)來說，研究好中文分詞會給企業(yè)的發(fā)展帶來戰(zhàn)略機遇，因為如果國外的計算機處理技術(shù)如果想要打入中國市場，那么首先他們必須入鄉(xiāng)隨俗，考慮中國國內(nèi)的市場需求，那么就必須擁有中文分詞技術(shù)；對我們國家來說，研究好中文分詞才會為超越英文使中文在信息領(lǐng)域的主導(dǎo)地位，有利于科學(xué)技術(shù)的進(jìn)一步發(fā)展，體現(xiàn)中國作為大國、強國的風(fēng)范。
中文分詞在分詞標(biāo)準(zhǔn)以及在分詞算法上相比起英文分詞來說，都存在著一定的困難，需要通過不停的研究、優(yōu)化，不斷的提高中文分詞的效率和準(zhǔn)確性。本文對中文分詞的常用算法進(jìn)行了比較分析，借用已有的分詞系統(tǒng)對分詞的準(zhǔn)確率進(jìn)行了統(tǒng)計。本畢業(yè)設(shè)計基于機械分詞算法，結(jié)合了N-Gram模型在前人研究的基礎(chǔ)上采用JAVA程序開發(fā)語言，結(jié)合更加優(yōu)良的存儲和匹配方法，做出相應(yīng)的分詞程序，最終實現(xiàn)了對若干句子的分詞，并在文本文檔中顯示出切分結(jié)果。同時相應(yīng)的提高了中文分詞的效率和正確率。
本文的研究成果可以作為中文分詞相關(guān)研究的參考，為中文分詞算法研究提供一種思路和方向。同時在研究中思考問題、解決矛盾的方法能夠為今后無論是在學(xué)習(xí)、生活還是工作中可以提供一種特別的角度。設(shè)計思路及實現(xiàn)技術(shù)
本畢業(yè)設(shè)計采用基于詞典的分詞算法，對算法進(jìn)行實現(xiàn)。在實現(xiàn)的過程中將N-Gram模型應(yīng)與全切分技術(shù)結(jié)合、將正向最大分詞算法與逆向最大分詞算法結(jié)合對詞典進(jìn)行雙向掃描，并引入利基于trie索引樹的分詞詞典機制進(jìn)行詞典優(yōu)化。本畢業(yè)設(shè)計在中文分詞技術(shù)實現(xiàn)過程中采用了典型的軟件工程工作方法，通過調(diào)查研究、需求分析、概要設(shè)計、系統(tǒng)設(shè)計、編碼、測試，在windows7的環(huán)境下采用myeclipse開發(fā)工具，用JAVA程序開發(fā)語言實現(xiàn)中文分詞。
中文分詞方法研究
中文分詞的概述
中文中的基本單位是字，字與字組成了句子，一個句子中有若干個詞語，詞語只能人為的劃分出，所以在九年義務(wù)教育的語文課堂中，會學(xué)習(xí)斷句、劃分句子成分等來識別句子、文段、文章的具體含義。而中文分詞就是通過一定的中文分詞算法將中文文本進(jìn)行切分，將中文句子切分為與原中文文本意思相一致的若干個詞語（即若干個有實際意義的的詞語）。“中文分詞技術(shù)從科學(xué)領(lǐng)域來劃分，它是屬于自然語言處理的技術(shù)范疇。讓電腦能夠準(zhǔn)確的理解中文文本的具體實際意義的處理過程就是對中文進(jìn)行分詞，也叫切詞。[7]”中文分詞常用算法
中文自動分詞系統(tǒng)中現(xiàn)有常用的分詞方法主要有三種：（1）基于詞典的分詞方法；（2）基于統(tǒng)計頻率的分詞方法；（3）基于理解的分詞方法。基于詞典的分詞方法
（1）機械分詞的闡述
基于詞典的分詞方法又被叫做機械分詞方法。這種方法是將中文文本中的字符串與詞典（已有的固定的詞庫）中的字符串（詞條）進(jìn)行匹配，如果在詞典中沒有找到相應(yīng)的字符串，則匹配失敗，按照一定規(guī)則重新進(jìn)行匹配；如果在詞庫中找到該字符串則匹配成功，即成功且分出一個詞?；谧址ヅ涞姆衷~方法可以按照不同的規(guī)則分為正向匹配算法和逆向匹配算法（根據(jù)掃描方向劃分）、最大匹配和最小匹配法（根據(jù)不同長度優(yōu)先匹配原則劃分）、單純分詞方法和分詞與標(biāo)注相結(jié)合的方法（根據(jù)是否與詞性標(biāo)注相結(jié)合原則劃分）。常用的分詞方法除了以上幾種還有最少切分方法。通常情況下根據(jù)排列組合規(guī)律又能夠?qū)⑸鲜龇椒ɑハ嘟Y(jié)合從而得到更多的分詞方法。最常用的機械分詞方法有正向最大匹配法、逆向最大匹配算法、雙向匹配算法（采用最大匹配法并將正向與逆向相結(jié)合的方法）和最少切分法。
“通過對正向最大匹配法及逆向最大匹配法的進(jìn)行了中文分詞的實現(xiàn)，并對分詞結(jié)果進(jìn)行了正確率的統(tǒng)計：正向最大匹配的正確率99.408284%，逆向最大匹配法的正確率是99.591837%。[8]”統(tǒng)計結(jié)果顯示逆向最大匹配算法的正確率高于正向最大匹配算法即逆向最大匹配法優(yōu)于正向最大匹配算法。盡管如此，上文所述要滿足實際需求，準(zhǔn)確率必須在99.9%以上，所以在實際中的中文分詞系統(tǒng)都是把基于字符串的匹配方法作為最基礎(chǔ)的（最初級的）切分方法，在此基礎(chǔ)上用其他方法繼續(xù)提高分詞的準(zhǔn)確率。
現(xiàn)如今主要采用的方法主要有特征掃描。此方法主要是對字符串的掃描方式進(jìn)行了優(yōu)化，將一些具有特殊字或者明顯特征的詞進(jìn)行先切分，在將這些詞抽象為英文中的空格即分界符，再將剩余的字符串進(jìn)行機械分詞進(jìn)而提高分詞的正確率。除此之外還有一種方法是將機械分詞與詞類標(biāo)注相結(jié)合的方法，借助詞類標(biāo)注的多樣性進(jìn)行分詞，反過來又作用于分詞的結(jié)果即又起到檢驗員的作用從而提高分詞的正確率。
機械分詞中的輔助工具（詞典）
①有序線性詞典結(jié)構(gòu)
有序線性詞典顧名思義是一種有序表，該表是以詞為單位的，在初始化時將字符串讀取到內(nèi)存中去然后通過二分法尋找定位。該種詞典結(jié)構(gòu)的算法簡單能夠減少空間存儲率、方便用計算機語言實現(xiàn)。正因為算法的簡單詞典排序的有序性導(dǎo)致分詞過程中掃描查找效率低且詞典不易更新，在更新詞典中需要添新詞或者刪除原有舊詞，此過程就必須移動詞典中原有不動的詞來保證詞典的有序性，從而降低了分詞效率。有序線性詞典結(jié)構(gòu)如表2.1所示。
表2.1有序線性詞典結(jié)構(gòu)
②基于整詞二分的分詞詞典結(jié)構(gòu)
基于整詞二分的分詞詞典結(jié)構(gòu)可以分為三個層次：詞典正文、次索引表及首字表。同有序線性結(jié)構(gòu)相似該結(jié)構(gòu)詞典的正文也是以詞為單位的有序表，詞索引表是一個指針表，該表指向詞典正文中的每個詞，在掃描過程中通過hash定位首字表及指針的詞索引表能夠確定字符串的所在的一個大致的范圍，然后在該范圍中進(jìn)行二分定位?；诖嗽~典的掃描范圍小于線性有序詞典的掃描范圍，從而相對的提高切分效率。有序線性詞典結(jié)構(gòu)如表2.1所示。
表2.2基于整詞二分詞詞典結(jié)構(gòu)首字hash表
入口項個數(shù)
第一項指針
詞典索引表
詞典正文指針
詞典正文
③基于trie索引樹的分詞詞典機制
“Trie索引樹是鍵樹，表示形式為多重鏈表。該詞典分為兩部分：首字表和trie索引樹結(jié)點。該詞典在掃描過程中沿樹鏈逐字進(jìn)行一一匹配。[2]”由于一個詞作為一個樹枝，所以空間占有率大，造成資源浪費。
基于統(tǒng)計的分詞方法
基于統(tǒng)計的分詞方法又稱作統(tǒng)計取詞法或無詞典分詞法。由于漢語中字與字組成了詞，當(dāng)幾個字的經(jīng)常相鄰出現(xiàn)時我們就可以計算其共現(xiàn)率，當(dāng)共現(xiàn)率高于一定值時，我們便可以人為的認(rèn)定該字符串很有可能是一個詞。然后切分出該字符串作為一個詞組。這種方法不需像機械分詞一樣需要詞典，只需要統(tǒng)計文本中字符串的共現(xiàn)率即可。畢竟計算機是機器而不具有思維，所以在取詞的過程中不能很準(zhǔn)確的區(qū)分識別該字符串是否為常用的詞組，如“是的”、“你的”、“有些”、“是以”等。所以該方法的識別精度低而時空開銷大。
在實際的應(yīng)用中該方法一般都會加入基礎(chǔ)的日常詞典，在統(tǒng)計分詞的同時進(jìn)行字符串匹配分詞，將二者相結(jié)合提高分詞的效率和準(zhǔn)確率，同時避免歧義識別。基于理解的分詞方法
計算機作為一種機器不具備人的思維，而給予理解的分詞方法則是模擬了人分析文本的思維方式，讓計算機與人一樣去理解句子，從而對文本進(jìn)行切分識別。該分詞方法在對詞進(jìn)行切分時需要同時對語法、語義進(jìn)行分析，通過分析處理來消除歧義切分文本。該方法需要一個總控系統(tǒng)，在該系統(tǒng)的調(diào)控下同時使用分詞子系統(tǒng)和句法語義子系統(tǒng)來對中文文本進(jìn)行處理。由于該方法需要結(jié)合龐大的漢語系統(tǒng)知識等，所以就目前現(xiàn)狀來看，該系統(tǒng)還不成熟，其成熟實現(xiàn)仍需要繼續(xù)大量深入的研究與實踐。
中文分詞的難點
漢語語言博大精深，人都不可能完完全全的理解漢語，正所謂一千個讀者就有一千個哈姆雷特，所以讓一個沒有思維的計算機來理解漢語是不容易的。從中文分詞系統(tǒng)研究開始到現(xiàn)在，歧義識別和新詞識別仍是中文分詞方法研究課題的兩個難點。歧義識別
對一句話的理解，不同的人可能有不同正確的理解，而在計算機切分時就會出現(xiàn)更多的正確的、不正確的切分方法，這就產(chǎn)生了歧義。歧義主要有交叉歧義、組和歧義。交叉識別就是在切分文本的時候一個字可以同時和前后相鄰的詞組成一個詞組，加上計算機不會像人一樣去分析理解句子的具體含義，從而導(dǎo)致切分結(jié)果多樣化。如：我想回我家。因為“回我家”和“回我”、“我想”和“我想回”這幾個字符串都組成了詞組，所以對于這句話的切分就可以分為“我想回 我家”或者“我想 回我家”或者“我想 回我 家”。
組合歧義就兩個相鄰的詞相結(jié)合在不同的句子中可能切分出來時，正確的表述了句子的意思，也可能出現(xiàn)錯誤切分。如：“這個羽毛球拍賣不賣”中的“拍賣”和“拍賣會”中的“拍賣”，前者以“拍賣”來切分按照語句意思完全是錯誤的，而后者則是正確的切分。新詞識別
在一個分詞系統(tǒng)的詞典中，收錄的詞畢竟是有限的，而那些未收錄進(jìn)詞典的詞組即為新詞。新詞有地名、人名、網(wǎng)絡(luò)語等等一系列時時更新、不斷變化的詞。如山西的運城，對于“運城是一座美麗的城市”和“秦皇島是海上貨運城市”這兩句話中的“運城”“貨運”“城市”，運城是否能算作一個詞，對于計算機而言是很有難度的。
所以新詞識別在中文分詞系統(tǒng)中能夠評價一種分詞系統(tǒng)優(yōu)劣的主要指標(biāo)。
基于詞典的正向最大匹配研究
機械分詞算發(fā)就是在系統(tǒng)中導(dǎo)入或者建一個字典庫，將字符串序列與字典詞庫中的詞組進(jìn)行一一匹配。具體方法是，將待切分的字符串序列i，按照一定的規(guī)則取出字符串序列i的子字符串序列i1，將i1與字典庫中的詞組進(jìn)行匹配，若字典庫中有一個詞組與i1相同，則成功切分出字符串序列i1，繼續(xù)切分其余字符串序列；若字典詞庫中不存在該字符串序列i1，重新按照規(guī)則取出另一個字符串序列進(jìn)行匹配。算法思想
最大正向匹配法的基本思想為：假設(shè)字典庫中最長的字符串有i個漢字字符，則在要被處理的中文文本中選取前i個字符作為一個匹配字符串序列，掃描字典庫，若在字典庫中能夠找到這樣的i個字符的字符串序列則匹配成功，則成功切分出該字符串序列；如果找不到則匹配失敗，去掉i字符串序列中的最后一個漢字字符，對剩下的（i-1）個字符串序列繼續(xù)重新匹配處理。如此循環(huán)直到待處理的中文文本全部處理結(jié)束。正向最大匹配算法實現(xiàn)原理
（1）TrieNode具體實現(xiàn)方法：
建立TrieNode類 ；建立結(jié)點關(guān)鍵字，public char key=(char)0；其值為中文詞中的一個字。如果該字在詞語的末尾，則bound=true，public boolean bound=false;建立指向下一個結(jié)點的指針結(jié)構(gòu)，用來存放當(dāng)前字在詞中的下一個字的位置如：Public HashMap<Character,TrieNode> childs=new 。
在全切分的算法中利用N-Gram模型給每一種切分結(jié)果計算分值。如果多個切分結(jié)果分值相同，則選擇切分出的詞的個數(shù)最少的切分結(jié)果（最少分詞原則）。
（2）假設(shè)詞典中保存了如下詞：
{今天，是，周末，原來}
假設(shè)要進(jìn)行分詞的例句如下：
“原來今天是周末啊！”
我們設(shè)最大詞長為5；
從左邊截取5個字：
原來今天是
原來今天
原來今
原來此時，我們得到一個詞：原來
從“原來”后面繼續(xù)截取5個：
今天是周末
今天是周
今天是
今天此時，我們得到一個詞：今天
是周末啊
是周末
是周
是 此時，我們得到一個詞：是
周末啊
周末此時，我們得到一個詞：周末
最后正向最大匹配的結(jié)果是：原來/今天/是/周末/啊N-Gram數(shù)學(xué)模型
N-Gram是一種語言模型。該模型也是搜狗拼音和微軟拼音的主要思想。在實際的中文分詞系統(tǒng)中不單單采用一種分詞方法，也會采用基于統(tǒng)計頻率的算法。N-Gram模型需要一個假設(shè)前提：第i個詞的出現(xiàn)僅僅與前面（i-1）個詞有關(guān)，與其他的詞都沒有關(guān)系。而該句話的概率就是每個詞出現(xiàn)的概率的乘積。N-Gram模型常用的是二元的Bi-Gram模型和三元Tri-Gram模型。
對于統(tǒng)計序列（漢子字符串序列）C（W1 W2 … Wi …Wn）第i個字符出現(xiàn)的概率只與前（i-1）個字符有關(guān)，其概率為：
由和N-Gram模型可得：
統(tǒng)計序列（漢子字符串序列）C（W1 W2 … Wi …Wn）在要處理文本中出現(xiàn)次數(shù)：C（W1 W2 … Wi …Wn）得：Trie樹結(jié)構(gòu)
（1）Trie樹（字典樹）的結(jié)構(gòu)有三種：標(biāo)準(zhǔn)樹、壓縮樹、后綴樹。Trie樹在中文分詞算法中的應(yīng)用是用來存儲大量的字符串從而提高分詞時掃描的效率。前綴Trie的使用能夠保證在最大匹配時進(jìn)行的下一次掃描是非詞典詞或者不是詞的前綴。
Trie樹中，字符串序列中所有的含有公共前綴的字符串位于同一個結(jié)點。如集合B{bear,bell,bid,bull,buy,sell,stock,stop}的Trie樹圖如圖2.2所示。其中圓形代表內(nèi)部結(jié)點，方形則為外部結(jié)點。Trie樹與其他結(jié)構(gòu)的比較
Trie樹，在生活中比較常見的應(yīng)用就是搜索自動提示，當(dāng)我們在搜索框中輸入字串信息的時候，如“山西”，提示“山西省”；再有就是我們平時使用的輸入法的聯(lián)想功能，也是同樣原理。
（1）Trie樹與二叉搜索樹（binary search tree）的比較
二叉搜索樹具有以下特點：
① “若果任意節(jié)點左子樹不為空，那么左子樹所有節(jié)點的值都小于根節(jié)點的值；[12]”
② “如果任意節(jié)點右子樹不為空，那么右子樹所有節(jié)點的值都大于根節(jié)點的值；[12]”
③ 左右子樹也都是二叉搜索樹；
④ 所有節(jié)點的值都不相同。
其實二叉搜索樹的優(yōu)勢在于查找、插入的時間復(fù)雜度上了，其復(fù)雜度通常只有O(log n)，現(xiàn)實中有很多的集合都是通過二叉樹實現(xiàn)的?！霸诙鏄渖线M(jìn)行插入操作時，實質(zhì)上是給樹添加了新的葉子節(jié)點，不需要節(jié)點移動；[12]”搜索、插入和刪除的復(fù)雜度等于樹的高度，其為O(log n)，最壞情況下整棵樹所有的節(jié)點都只有一個子節(jié)點，完全變成一個線性表，其復(fù)雜度為O(n)。
Trie樹在最壞情況下數(shù)據(jù)查找的速度，也要快過二叉搜索樹的速度，如果搜索字符串長度用m來表示的話，它只有O(m)，通常情況（樹的節(jié)點個數(shù)要遠(yuǎn)大于搜索字符串的長度）下，Trie樹要遠(yuǎn)小于O(n)。
當(dāng)然，Trie樹也存在一個缺點，那就是Trie本身對key的適宜性是有嚴(yán)格要求的，之前我們舉例都是使用的字符串，如果Trie樹的key是浮點數(shù)的話，就很有可能導(dǎo)致整個Trie樹很長，節(jié)點的可讀性也會變的很差，在這種情況下，我們是不適合使用Trie樹來進(jìn)行保存數(shù)據(jù)的；相反二叉搜索樹就不會存在這個問題。
（2）Trie樹與Hash結(jié)構(gòu)比較
Hash結(jié)構(gòu)的首要問題就是表鍵沖突的問題。通常我們說Hash表的復(fù)雜度是O(1)，其實嚴(yán)格意義上來說，這是接近理想的Hash表的復(fù)雜度，現(xiàn)實中我們還需要考慮到hash函數(shù)本身需要遍歷搜索字符串，其復(fù)雜度往往是O(m)。在不同鍵被映射到“同一個位置”（考慮closed hashing，這“同一個位置”可以由一個普通鏈表來取代）的時候，需要進(jìn)行查找的復(fù)雜度，是取決于這“同一個位置”下節(jié)點的個數(shù)。所以在現(xiàn)實中，最壞情況下，Hash表也能作為一張單向鏈表的。
Trie樹可以很容易地以key的字母序排序（整棵樹只需要先序遍歷一次即可），該方法對現(xiàn)實中很多Hash表來說是不一樣的的，因為一般來情況下Hash表對于不同的key來說是無序的。
在理想情況下，Hash表是可以以O(shè)(1)的速度迅找到我們想要的數(shù)據(jù)，但是，如果這張表非常大的時候，而有要放入磁盤，對于Hash表來說，在理想的情況下，其查找訪問進(jìn)行一次即可；但對于Trie樹來說，訪問磁盤的數(shù)目需要等于節(jié)點深度。
在大多數(shù)情況下Trie樹占用的空間要多余Hash表所占空間，如果要在一個節(jié)點放一個中文字符，對于字符串的保存來說，是不能獨立成塊的。但是我們可以利用Trie書的節(jié)點壓縮來彌補此不足。需求分析
可行性分析
對中文分詞算法來說，從二十世紀(jì)八十年代開始國內(nèi)專家學(xué)者就已經(jīng)對中文分詞有了一定深入的研究，所以從中國知網(wǎng)、萬維網(wǎng)等學(xué)術(shù)性網(wǎng)站中可以找到相關(guān)的參考文獻(xiàn)。作為一名即將畢業(yè)的大學(xué)生，也具備了自學(xué)的能力，能夠理解相應(yīng)的算法。目前也有相關(guān)的中文分詞系統(tǒng)，能夠進(jìn)行測試統(tǒng)計，運用邏輯統(tǒng)計整理出幾種常用分詞算法的準(zhǔn)確率，并整理出其優(yōu)缺點。
對中文分詞技術(shù)來說，目前已經(jīng)有了相對成熟的中文技術(shù)，并且已經(jīng)應(yīng)用在了人類實際工作、生活環(huán)境中。這些技術(shù)都可以找到相關(guān)的技術(shù)參考資料，并且能深入研究。并且，截至到目前為止已經(jīng)對軟件工程、數(shù)據(jù)結(jié)構(gòu)、JAVA語言等相關(guān)計算機知識、技術(shù)和計算機語言有了較為深刻的理解，并能夠熟練的運用相關(guān)計算機技術(shù)進(jìn)行設(shè)計、編程、開發(fā)。
另外，從課題研究的時間上來看，從開始到結(jié)束有將近14周到時間可用來工作，時間上也是充足可靠的。從物質(zhì)投入來看也不存在額外的投入，學(xué)校提供免費的圖書資料，所以以目前的條件足以進(jìn)行開發(fā)研究。因此，進(jìn)行中文分詞方法的研究是具備一定可行性的。中文分詞系統(tǒng)目標(biāo)的分析
隨著科學(xué)技術(shù)的不斷發(fā)展、互聯(lián)網(wǎng)的普及越來越多的技術(shù)、軟件需要用到中文分詞技術(shù)，該技術(shù)、系統(tǒng)也越來越受到大家的關(guān)注。近幾年來，人工智能領(lǐng)域、自然語言領(lǐng)以及情報檢索界的專家學(xué)者對中文分詞進(jìn)行了深入的研究與實踐，探索出了多種既可以提保證正確率又能夠提高中文分詞效率的中文分詞的算法和系統(tǒng)。專家學(xué)者們在研究中文分詞系統(tǒng)時在其分詞的速率、準(zhǔn)確率等方面有了進(jìn)一步的研究同時也有了相應(yīng)的提高。目前，在中文分詞常用的算法中，機械分詞的應(yīng)用最為普遍、廣泛。
中文分詞系統(tǒng)的的目標(biāo)：（1）高精確；（2）高效率；（3）適應(yīng)性。
（1）高精確。任何一件事正確率是最基礎(chǔ)的。中文分詞系統(tǒng)也不例外即中文自動分詞系統(tǒng)的核心關(guān)鍵是高準(zhǔn)確率。目前的中文自動分詞系統(tǒng)中有少數(shù)分詞系統(tǒng)的準(zhǔn)確率在98%—99%之間，然而分詞的結(jié)果應(yīng)當(dāng)是高精確的，98%—99%對于中文分詞來說這樣的準(zhǔn)確率是不夠的，準(zhǔn)確率只應(yīng)該降低0.1甚至更少的百分點。只有提高準(zhǔn)確率才能更好的滿足實際需求。在99.9%的準(zhǔn)確率上，即使提高1/1000的百分點對于實際的需求也是具有相當(dāng)大的現(xiàn)實意義。
（2）高效率。由于中文分詞在各個系統(tǒng)中處于最基礎(chǔ)的環(huán)節(jié)，所以能節(jié)約時間盡量節(jié)約時間，減少不必要的時間消耗。一個復(fù)雜繁瑣的大系統(tǒng)必須在各個環(huán)節(jié)都用盡可能少的時間，讓用戶使用時覺得更加方便快捷。而中文分詞作為最基礎(chǔ)的一個部分，在工作時應(yīng)該高速運行達(dá)到5千字/秒—1萬字/秒甚至更快為最佳。
（3）適應(yīng)性。適應(yīng)性包括普遍適用性及多平臺通用。中文分詞系統(tǒng)不是最終的系統(tǒng)也不是最終的上層結(jié)果，而是一種基礎(chǔ)性的方法、手段，是為了其他終極目標(biāo)而打下的地基，為了能夠更加方便的適用于在各種各樣的系統(tǒng)中，所以應(yīng)當(dāng)具有普遍系統(tǒng)能適用的性質(zhì)。中文自動分詞系統(tǒng)在多領(lǐng)域的系統(tǒng)中處于基層環(huán)節(jié)，要具有良好的通用性來適用于各種相關(guān)但又不同的高層次系統(tǒng)，只有具備通用性，支持不同系統(tǒng)、不同地區(qū)文字的處理才能減少不必要的消耗。系統(tǒng)功能需求分析
基于詞典（字符串）的中文分詞系統(tǒng)實現(xiàn)的功能如下：
（1）分詞功能：系統(tǒng)可以調(diào)用機械分詞算法可以對txt格式中的文本進(jìn)行分詞，也可以對標(biāo)準(zhǔn)輸入的文字串進(jìn)行分詞。
（2）顯示功能：系統(tǒng)能夠?qū)⑶蟹纸Y(jié)果、切分時間在標(biāo)準(zhǔn)輸出中顯示出來；也能夠?qū)xt格式中的文本處理后的結(jié)果以txt格式返回到指定的目錄下。
（3）時間顯示功能：在切分結(jié)果完成后，可以對切分所用時間進(jìn)行顯示。
（4）內(nèi)存顯示功能：在切分結(jié)果完成后，可以對切分過程中程序運行所占內(nèi)存大小進(jìn)行顯示。系統(tǒng)的設(shè)計
整體設(shè)計
系統(tǒng)各功能模塊、算法模塊相互獨立，能夠提供功能全面的接口供其它應(yīng)用系統(tǒng)調(diào)用，而不僅限于本系統(tǒng)使用。分詞系統(tǒng)的框架圖如圖4.1所示。
圖4.1分詞系統(tǒng)框架圖
該框架分成三部分：第一部分由詞頻信息統(tǒng)計、更新、語料庫、語料學(xué)習(xí)構(gòu)成的字典管理，實現(xiàn)字典的更新功能；第二部分是由待分詞文本、預(yù)處理、詞匯切分組成的分詞器，實現(xiàn)對中文的切分功能；第三部分是由輸出和最終分詞結(jié)果組成的顯示器，實現(xiàn)顯示功能。分詞系統(tǒng)處理流程
預(yù)處理：預(yù)處理操作將讀入的文本進(jìn)行去標(biāo)點符號操作，并把整個文本切分成一個字符串序列，并對其進(jìn)行編碼轉(zhuǎn)換。
分詞：對預(yù)處理完成的字符串進(jìn)行正向逐字匹配劃分和逆向逐字匹配劃分，將兩個結(jié)果進(jìn)行對比，如果不同，就進(jìn)行消除歧義處理。
中文分詞系統(tǒng)處理流程如圖4.2所示：
（2）若大小為b的字母表中存在s個字符串的集合B，其存儲長度是l，該集合B的Trie樹具有如下性質(zhì)：
① Trie樹中每個內(nèi)部結(jié)點最多有b個子結(jié)點。
② Trie樹中有s個外部結(jié)點。
③ Trie樹的高度與集合B中最長串的長度相同。
④ 樹中的結(jié)點數(shù)為O(l)。
（3）Trie樹的基本性質(zhì)可以歸納為：
① 根節(jié)點不包含字符，除根節(jié)點以外的每個結(jié)點有且只有一個字符。
② “字符串是將路徑上的字符連接起來的，從根節(jié)點到某一個節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。[9]”
③ 每個節(jié)點的所有子節(jié)點包含的字符串不相同。
④ 如果字符的種數(shù)為n，則每個結(jié)點的出度為n，這也是空間換時間的體現(xiàn)，浪費了很多的空間。
⑤ 插入查找的復(fù)雜度為O(l)，l為字符串長度。
（4）Trie樹結(jié)構(gòu)的數(shù)據(jù)搜索方法如下：
① 首先由根結(jié)點開始；
② “取得要查找關(guān)鍵詞的第一個字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索；[9]”
③ “在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個字母,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。[10]”
④ 迭代以上搜索過程……
⑤ “在某個結(jié)點處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點上的信息，從而完成查找。[11]”
系統(tǒng)的詳細(xì)設(shè)計
該中文分詞系統(tǒng)的設(shè)計主要核心類有：CorpusTools該類是語料庫工具類，用于構(gòu)建二元模型和三元模型并做進(jìn)一步的分析處理，同時把語料庫中的新詞加入詞典。主要方法有：process和analyzeCorpus方法用于分析語料庫，constructNGram用戶建模型，processBiGram分析二元模型，processTriGram分析三元模型，processWords分析處理并存儲不重復(fù)詞，mergeWordsWithOldDic和舊的詞典進(jìn)行合并，processPhrase用于生成短語結(jié)構(gòu)。CorpusTools類圖如圖4.3所示。
圖4.3 CorpusTools類圖
DictionaryTools類是詞典工具類，用于把多個詞典合并為一個并規(guī)范清理，移除詞典中的短語結(jié)構(gòu)。主要方法有：removePhraseFromDic用于移除詞典中的短語結(jié)構(gòu)，merge把多個詞典合并為一個。
DictionaryTools類圖如圖4.4所示。
圖4.4DictionaryTools類圖
recognitionTool類是詞典工具類，用于把分詞特殊情況識別。主要方法有：recog用于識別文本，isFraction用于小數(shù)和分?jǐn)?shù)識別，isEnglishAndNumberMix用戶英文和字母混合識別，isEnglish用于英文字母識別，isQuantifier用于數(shù)量詞識別，isNumber用于數(shù)字識別，isChineseNumber用戶中文數(shù)字識別。
recognitionTool類圖如圖4.5所示。
圖4.5recognitionTool類圖
WordConfTools類是詞典工具類，用于獲取配置信息。該類中的方法都是用于獲取配置文件的，具體方法名在類圖中顯示。WordConfTools類如圖4.6所示。
圖4.6WordConfTools類圖系統(tǒng)實現(xiàn)
分詞功能實現(xiàn)
優(yōu)化的分詞功能的實現(xiàn)
系統(tǒng)可以調(diào)用機械分詞算Ian法可以對txt格式中的文本進(jìn)行分詞，也可以對標(biāo)準(zhǔn)輸入的文字串進(jìn)行分詞。
進(jìn)入系統(tǒng)之后，首先會有一個選擇的界面，這個選擇界面是通過switch...case...語句實現(xiàn)的，每一個case語句后都會有一個選擇的標(biāo)識，在標(biāo)識后面，是用戶選擇了該標(biāo)識之后會執(zhí)行的函數(shù)體，這樣就實現(xiàn)了用戶可以選擇的效果，用戶通過自己需要的選擇進(jìn)入到系統(tǒng)之后，會執(zhí)行不同的函數(shù)體，當(dāng)用戶選擇了對txt格式中文本進(jìn)行分詞的選項之后，系統(tǒng)會首先在主函數(shù)中調(diào)用機械分詞的算法，然后通過讀取文件的語句讀取到文件中的信息，保存在一條字符串中，這個字符串中現(xiàn)在保存的是從txt文件中讀取出來的文件，這時候，系統(tǒng)會將從txt中保存的字符串傳入到該機械分詞算法函數(shù)的參數(shù)中，該函數(shù)執(zhí)行完畢之后會返回一條同樣是String類型的字符串，保存到一個string變量中，然后將這條字符串保存到新的txt文檔中，這樣就實現(xiàn)了對txt格式中的 文本進(jìn)行分詞的功能。
同樣，當(dāng)用戶選擇了對標(biāo)準(zhǔn)輸入的文字串進(jìn)行分詞的功能之后，會之后該選擇后的函數(shù)體，首先，系統(tǒng)同樣會調(diào)用系統(tǒng)的機械分詞的算法函數(shù)，該函數(shù)需要傳入一個String字符串作為參數(shù)，返回一個新的String字符串，在這個函數(shù)體中，因為需要接收用戶輸入的信息，所以會用到Scanner，這樣系統(tǒng)就能接收到用戶輸入的信息了，在系統(tǒng)接收到用戶輸入的信息之后，會將該用戶的信息保存在一個String字符串中，然后將該String字符串傳入到函數(shù)中作為參數(shù)，在函數(shù)執(zhí)行結(jié)束之后，系統(tǒng)會將結(jié)果返回的字符串保存到一個新的string字符串中，輸出，這樣，就完成了該功能流程。
在實現(xiàn)分詞算法前,首要解決的問題是機器詞典的選擇和加載方式。本系統(tǒng)使用核心詞典為年1998年人民日報1月份語料經(jīng)加工后統(tǒng)計出的詞條，共有10456個詞。為了便于調(diào)用和提高算法整體性能,先將詞典文件進(jìn)行詞條排序，并抽象成JAVA類,然后通過JAVA序列化成*.dct格式的文件將其保存。當(dāng)系統(tǒng)啟動加載詞典時，通過JAVA反序列化將*.dct文件轉(zhuǎn)化成Dictionay對象,完成加載過程。詞典序列化結(jié)構(gòu)中漢字字符編碼集為utf-8。
基于詞典的正向最大匹配算法的分詞功能實現(xiàn)圖如圖5.1所示。
圖4.2中文分詞系統(tǒng)處理流程
圖5.1基于詞典的最大匹配算法的分詞功能模塊實現(xiàn)圖
基于詞典的最大匹配算法的分詞功能實現(xiàn)圖如圖5.2所示。
圖5.2
添加分詞算法的實現(xiàn)
在包中新建一個類，在類中新建一個方法把別人的方法添加進(jìn)去
然后在主函數(shù)新建一個該類的對象用對象點出方法，直接調(diào)用已有的分詞算法。
雙向最大最小匹配算法的分詞實現(xiàn)圖如圖5.3所示。
基于詞典的最大匹配算法的分詞功能實現(xiàn)圖
- 圖5.3雙向最大最小匹配算法的分詞實現(xiàn)圖
正向最小匹配算法的分詞實現(xiàn)圖如圖5.4所示。
圖5.4正向最小匹配算法的分詞實現(xiàn)圖
基于詞典的全切分算法的分詞實現(xiàn)圖如圖5.5所示。
圖5.5
基于詞典的全切分算法的分詞實現(xiàn)圖
基于逆向最大匹配算法的實現(xiàn)圖如圖5.6所示。
基于逆向最大匹配算法的實現(xiàn)圖
顯示功能
系統(tǒng)能夠?qū)⑶蟹纸Y(jié)果、切分時間在標(biāo)準(zhǔn)輸出中顯示出來；也能夠?qū)xt格式中的文本處理后的結(jié)果以txt格式返回到指定的目錄下。
這個功能的實現(xiàn) 流程大概描述如下，首先使用Date date=new Date（）；獲取當(dāng)前系統(tǒng)的時間，然后通過SimpleDataFormat的format方法，在方法中傳入yyyy-MM-dd hh：mm：SS來獲取當(dāng)前系統(tǒng)的時間，形式就是前面的樣子，這個樣子就是時間顯示的模版，當(dāng)系統(tǒng)執(zhí)行切分函數(shù)的時候，會通過上述的方法來記錄當(dāng)前函數(shù)執(zhí)行的時間，然后通過System.out.println()的方式輸出當(dāng)前的時間。切分的方法會返回一個String類型的字符串，這個字符串會在函數(shù)執(zhí)行結(jié)束之后，被保存在一個String類型的字符串中，然后同樣是通過System.out.println()的方法來輸出這個字符串，這樣，就實現(xiàn)了系統(tǒng)可以將切分結(jié)果和切分函數(shù)執(zhí)行的時候標(biāo)準(zhǔn)輸出了。
將txt格式中的文本處理后的結(jié)果以txt格式返回到指定的目錄下的這個功能，首先將通過流inputStreamReader讀取到程序中，在程序中，使用一個String類型的 字符串接收到txt文本中的內(nèi)容，然后將這個內(nèi)容傳入到需要處理的函數(shù)中，在函數(shù)執(zhí)行結(jié)束之后，同樣會返回一個String字符串，這個字符串，通過OutputStreamWriter寫入到指定的txt文件中，這樣，就實現(xiàn)了這個功能。顯示功能如圖5.7所示。
圖5.7txt格式顯示圖
時間與內(nèi)存顯示功能
在WordSegmenter.java類的主函數(shù)中：
long cost = System.currentTimeMillis() - start；float rate = textLength/cost語句實現(xiàn)對切分時間的顯示。
在WordSegmenter.java類的主函數(shù)中：使用String pre="執(zhí)行之前剩余內(nèi)存:"+max+"-"+total+"+"+free+"="+(max-total+free)；String post="執(zhí)行之后剩余內(nèi)存:"+max+"-"+total+"+"+free+"="+(max-total+free)語句實現(xiàn)對內(nèi)存的計算及顯示。
時間及內(nèi)存占用大小顯示如圖5.8所示。
系統(tǒng)測試
分詞及顯示功能測試
本中文分詞系統(tǒng)中可以調(diào)用多種算法，在不同算法下對中文文本進(jìn)行切分，可以直接顯示，也可以在文本文檔中顯示。
將記事本中的內(nèi)容如圖6.1所示分別進(jìn)行正向最大分詞、正向最小分詞、雙向最大分詞、全切分。
圖6.1待切分的中文文本
正向最大分詞切分結(jié)果如圖6.2所示。
圖6.2正向最大匹配算法的分詞結(jié)果
正向最小匹配分詞切分結(jié)果如圖6.3所示。
圖6.3正向最小匹配算法分詞結(jié)果
雙向最大分詞切分結(jié)果如圖6.4所示。
圖6.4雙向最大匹配算法的切分結(jié)果
全切分的分詞切分結(jié)果如圖6.5所示。
圖6.5全切分的切分結(jié)果
切分時間及內(nèi)存顯示測試
（1）正向最大匹配分詞：
字符數(shù)目：155
分詞耗時：63701 毫秒
執(zhí)行之前剩余內(nèi)存:259.52255-16.252928+10.72676=253.99638
執(zhí)行之后剩余內(nèi)存:259.52255-173.20346+99.0102=185.32928
（2）正向最小匹配分詞：
字符數(shù)目：155
分詞耗時：58390 毫秒
執(zhí)行之前剩余內(nèi)存:259.52255-16.252928+10.733336=254.00296
執(zhí)行之后剩余內(nèi)存:259.52255-173.20346+99.010185=185.32928
（3）雙向最大匹配分詞：
字符數(shù)目：155
分詞耗時：70654 毫秒
執(zhí)行之前剩余內(nèi)存:259.52255-16.252928+10.726304=253.99593
執(zhí)行之后剩余內(nèi)存:259.52255-259.52255+26.046408=26.046408
（4）全切分算法
字符數(shù)目：155
分詞耗時：67812 毫秒
執(zhí)行之前剩余內(nèi)存:259.52255-16.252928+10.726544=253.99617
執(zhí)行之后剩余內(nèi)存:259.52255-259.52255+24.919064=24.919064測試結(jié)果分析
最大匹配分詞和最小匹配的切分結(jié)果中，對“最大瓶頸”、“這一對”均出現(xiàn)了歧義切分，而雙向最大匹配中避免了該問題。在正向最小匹配的切分結(jié)果中將“中文分詞”切分為“中文 分詞”，“正確率”切分為“正確 率”，“自然語言”切分為“自然 語言”。在多次的中文文本切分中，雙向最大匹配相對其他兩種分詞算法來說正確率是相對比較高的。在全切分中切分得此基于N-Gram模型進(jìn)行頻率統(tǒng)計，所以切分的結(jié)果詞是不穩(wěn)定的，如“中文分詞”第一次被切分為“中文分詞”，第二次則被切分為“中文 分詞”。
通過比較分析，正向最小匹配算法正確率低耗時短，運行過程中所占內(nèi)存比較?。浑p向最大匹配算法正確率高耗時長，運行過程中所占內(nèi)存比較大。
結(jié)論
本畢業(yè)設(shè)計對基于詞典的分詞算法、基于統(tǒng)計的分詞算法和基于理解分詞算法進(jìn)行了研究。重點對基于詞典的分詞算法的切分結(jié)果進(jìn)行了研究對比。闡述了此算法的原理，著重研究了正向最大分詞原理，分析了分詞算法的思想、數(shù)學(xué)模型計算法的實現(xiàn)。本畢業(yè)設(shè)計主要使用JAVA程序設(shè)計語言，設(shè)計實現(xiàn)了一個中文分詞系統(tǒng)，實現(xiàn)了分詞功能、顯示功能及切分消耗時間及所占內(nèi)存的顯示功能。通過該系統(tǒng)的功能驗證算法的正確率及分詞速度。
本設(shè)計目前存在的不足有：（1）只能顯示待切分的字符數(shù)、消耗時間、運行前后內(nèi)存剩余，沒有正確的顯示對分詞速度；（2）只能在myeclipse中運行，通用性不強；（3）只能用JAVA程序設(shè)計語言調(diào)用、修改該程序，平臺單一，對JAVA語言不熟悉的用戶不能很好的使用該程序完成中文檢索、語音識別等其他上層系統(tǒng)。在設(shè)計研究中還不能很好的完成分詞算法的明顯優(yōu)化，對算法的數(shù)學(xué)模型也不能靈活使用，希望通過今后繼續(xù)努力研究能夠研究出更優(yōu)化的算法及更高效的分詞程序，并針對不足做出改進(jìn)。
參考文獻(xiàn)
[1] 陳曉霞. 中文信息處理在動態(tài)幾何軟件領(lǐng)域的應(yīng)用研究[J]. 浙江科技學(xué)院學(xué)報,2012,01:30-34.
[2] 曹衛(wèi)峰. 中文分詞關(guān)鍵技術(shù)研究[D].南京理工大學(xué),2009.
[3] 李宏波. 綜合字典和統(tǒng)計分析的中文分詞系統(tǒng)的研究與實現(xiàn)[D].武漢理工大學(xué),2010.
[4] 劉婷. 中文自動分詞法在全文檢索中的研究及應(yīng)用[D].南京航空航天大學(xué),2007.
[5] 普布旦增. 藏文自動分詞技術(shù)方法研究[D].西藏大學(xué),2010.
[6] 許榮榮. 中文文本自動分詞技術(shù)與算法研究[D].鄭州大學(xué),2010.
[7] 余戰(zhàn)秋. 中文分詞技術(shù)及其應(yīng)用初探[J]. 電腦知識與技術(shù),2004,32:81-83.
[8] 趙雙柱. 用鏈棧存儲搜索關(guān)鍵字提高中文搜索引擎中分詞的速度與精確度[J]. 福建電腦,2010,01:86+90.
[9] 代明壯,馬燕,李順寶. 一種新型整數(shù)集上的動態(tài)統(tǒng)計數(shù)據(jù)結(jié)構(gòu)——Irie[J]. 軟件導(dǎo)刊,2009,07:14-16.
[10] 孫為,趙永精,宋健. 一種基于Trie的IPv6路由查找方案[J]. 計算機應(yīng)用與軟件,2008,07:35-36+50.
[11] 趙永精. 基于trie的路由查找算法研究[D].蘭州理工大學(xué),2007.
[12] 徐翠霞,崔玲玲,張家明. 利用二叉排序樹改進(jìn)結(jié)構(gòu)化P2P模型[J]. 計算機工程與應(yīng)用,2009,36:101-104.
[13] Schubert Foo,Hui Li.Chinese word segmentation and its effect on information retrieval. Information Processing and Management. 40(2004) 161-190 .
[14] Fu Lee Wang,Christopher C.Yang.Mining Web Data for Chinese Segmentation.JOURNAL OF THE AMERICAN SOCIETY INFORMATION SCIENCE AND ECHNOLOGY. 2007,58(12):1820-1837.
[15] Yunting Tang,Yan Wu. RESEARCH AND IMPLEMENTATION ON CHINESE WORD SEGMENTATION[A]. 寧波大紅鷹學(xué)院.Proceedings of 2007 International Symposium on Computer Science and Technology（ISCST'2007）[C].寧波大紅鷹學(xué)院:,2007:3.
[16] S. Maosong, and Z. Jiayan, "A critical appraisal of the research on Chinese word segmentation," Contemporary Linguistics, Vol.3, pp. 22-32, February 2001.
[17] 劉件,魏程. 中文分詞算法研究[J]. 微計算機應(yīng)用. 2008, 29(8): 11-16.
[18] 崔彥翔.基于條件隨機場的網(wǎng)絡(luò)研究[D].大連:大連理工大學(xué),2013.
致謝
短短幾個月的畢業(yè)設(shè)計,使我從中受到很大的教育和啟迪，不僅將大學(xué)所學(xué)的知識進(jìn)行了實際應(yīng)用，還學(xué)到了很多書本上學(xué)不到的知識。開闊了視野，增長了知識，積累了經(jīng)驗。充分鍛煉了自己的動手和應(yīng)用能力，真正做到了理論聯(lián)系實際。我能有今天的成績，是因為身后有那么多的人在關(guān)心著我，鼓勵著我，不管是同學(xué)還是長輩！
本文是在指導(dǎo)導(dǎo)師楊喜旺老師，周曉青老師的悉心指導(dǎo)下完成的。從開題、分析到撰稿和修改等整個論文撰寫過程中，導(dǎo)師都給予了細(xì)心的建議和指導(dǎo)。導(dǎo)師對本人的學(xué)習(xí)等各個方面都給予了無微不至的關(guān)懷與幫助。在此，我向?qū)煴磉_(dá)崇高的敬意和衷心的感激!
其次要感謝我們的班主任傅宏智老師，四年來，是您孜孜不倦的教導(dǎo)我們，關(guān)心我們的學(xué)習(xí)，照顧我們的生活，教會了我們認(rèn)識事物的方法和做人的原則。還要感謝孔令德老師，刑敏老師以及所有曾經(jīng)教過我們知識的老師們，正是你們的無私奉獻(xiàn)才有了我們的今天。我們每一點知識的積累都與您們辛勤的幫助密不可分，您們的人格魅力和治學(xué)態(tài)度令我十分欽佩。我們能看的更遠(yuǎn)，走的更好，是因為我們站在了您們的肩膀上。
最后，再次向所有關(guān)心、幫助、理解和支持我的老師和朋友們致以深深的謝意。謝謝你們給我的無私幫助。
