《漢語分詞技術(shù)初探計(jì)算機(jī)科學(xué)與技術(shù)畢業(yè)論文》由會(huì)員分享，可在線閱讀，更多相關(guān)《漢語分詞技術(shù)初探計(jì)算機(jī)科學(xué)與技術(shù)畢業(yè)論文（42頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、 蘭 州 商 學(xué) 院 本科生畢業(yè)論文（設(shè)計(jì)） 論文（設(shè)計(jì)）題目： 漢語分詞技術(shù)初探 學(xué) 院、 系： 信息工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系 專 業(yè) (方 向)： 計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí)、 班： 學(xué) 生 姓 名： 指 導(dǎo) 教 師：

2、 2011年5月18日 2 聲 明 本人鄭重聲明：所呈交的畢業(yè)論文（設(shè)計(jì)）是本人在導(dǎo)師的指導(dǎo)下取得的成果。對(duì)本論文（設(shè)計(jì)）的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。因本畢業(yè)論文（設(shè)計(jì)）引起的法律結(jié)果完全由本人承擔(dān)。 本畢業(yè)論文（設(shè)計(jì)）成果歸蘭州商學(xué)院所有。 特此聲明 畢業(yè)論文（設(shè)計(jì)）作者簽名： 年 月 日 漢語分詞技術(shù)初探 摘 要 所謂漢語分詞，就是將中文語句中的詞匯切分出來的過程。由

3、于漢語的書寫習(xí)慣，漢語語句中詞與詞之間的標(biāo)志是隱含的，英文的單詞與單詞之間有空格，所以不存在分詞問題。而中文的每一句中，詞與詞之問是沒有空格的，因而必須采用某種技術(shù)將其分開。 分詞技術(shù)作為自然語言處理的基礎(chǔ)環(huán)節(jié)，同時(shí)也是關(guān)鍵環(huán)節(jié)之一，它的質(zhì)量好壞直接影響到后續(xù)處理步驟的效果。漢語分詞工作看似細(xì)微，但作為計(jì)算機(jī)自然語言處理的第一步，它的關(guān)鍵作用是不容忽視的。如今漢語分詞己成為自然語言處理的研究熱點(diǎn)與難點(diǎn)。 本文討論了中文分詞的概念、目標(biāo)及其所面臨的一些基本問題，詳細(xì)介紹了三種基本中文分詞算法，并對(duì)中文分詞詞典的索引及常用詞典結(jié)構(gòu)進(jìn)行了介紹，最后說了正向最大算法的實(shí)現(xiàn)及測試結(jié)果。 [關(guān)

4、鍵詞]中文分詞 最大匹配 分詞詞典 自然語言處理 ABSTRACT Chinese word segmentation，is to cut the sentence in the Vocabulary sub—out process． Since the writing habits of Chinese，Chinese sentence symbol between words is implied．the English words have the spaces between the words，So there is easy to separate．The Chinese w

5、ord for each sentence，there is no space between words，and therefore must be some kind of technology to separate sentence． Chinese sentence segmentation algorithm from the 20th century，since the 80’S has been a research focus，due to the complexity of the Chinese language has been in a stage of develo

6、pment． Segmentation of natural language processing technology as the basic link，but also one of the key links，and its direct impact on the quality of the subsequent processing steps results．Chinese word segmentation the first step in natural language processing，and its importance can not be ignore

7、d． [Key Words] Chinese Word Segmentation，Maximum match，Segmentation Dictionary， Chinese Information Processing 目 錄 一、引言 1 二、中文分詞簡介 3 （一）中文分詞的概念 3 1、什么是中文分詞 3 2、中文分詞的應(yīng)用 4 （二）中文分詞的目標(biāo) 5 1、準(zhǔn)確性 6 2、運(yùn)行效率 6 3、通用性 6 4、適用性 7 （三）中文分詞的基本問題 7 1、分詞規(guī)范 8 2、歧義識(shí)別 10 3、未登錄詞 1

8、1 三、基本中文分詞算法 12 （一）中文分詞算法介紹 12 1、基于字符串匹配的分詞算法 12 2、基于理解的分詞算法 14 3、基于統(tǒng)計(jì)的分詞算法 14 （二）根據(jù)具體應(yīng)用使用合適的分詞算法 15 1、混合分詞 15 2、基于字的切分法 17 四、中文分詞詞典 17 （一）詞典的索引 18 1、Hash索引 18 2、Trie樹 18 （二）常用詞典結(jié)構(gòu) 19 1、有序線性詞典結(jié)構(gòu) 19 2、基于整詞二分的分詞詞典結(jié)構(gòu) 19 3、基于TRIE索引樹的分詞詞典機(jī)制 20 五、正向最大匹配算法的實(shí)現(xiàn) 21 （一）正向最大匹配算法 21 （二）采用正向最大算

9、法的分詞程序設(shè)計(jì) 24 六、結(jié)論 35 參 考 文 獻(xiàn) 36 致　謝 37 36 漢語分詞技術(shù)初探 一、引言 在自然語言處理中，詞是最小的能夠獨(dú)立活動(dòng)的有意義的語言成分。我們知道，在英文文本中，單詞之間是以空格作為自然分界符的。中文和英文比起來，有其自身的特點(diǎn)，就是中文以字為基本書寫單位，句子和段落通過分界符來劃界，但是詞語之間沒有一個(gè)形式上分界符。也就是說，從形式上看，中文沒有“詞”這個(gè)單位。 因此，進(jìn)行中文的自然語言處理通常都是先將中文文本中的字序列切分為合理的詞序列，然后再在此基礎(chǔ)上進(jìn)行其它分析處理。將中文連續(xù)的字序列按照一定的規(guī)則重新組合成詞序列的過程，就叫

10、做中文分詞。 作為中文信息處理基礎(chǔ)的中文分詞技術(shù)，己經(jīng)被廣泛應(yīng)用于中文信息領(lǐng)域的信息檢索、自動(dòng)摘要、中文校對(duì)、漢字的智能輸入、漢字簡繁體轉(zhuǎn)換、機(jī)器翻譯、語音合成等技術(shù)中。自20世紀(jì)80年代初，中文信息處理領(lǐng)域提出自動(dòng)分詞以來，相關(guān)方面的眾多專家學(xué)者、科研院所、業(yè)機(jī)構(gòu)為之付出了不懈的努力，取得了一些重要的進(jìn)展和一些實(shí)用性的成果，提出了許多中文分詞方法，有些成熟的技術(shù)已經(jīng)應(yīng)用于產(chǎn)品當(dāng)中。但這些分詞方法或多或少都存在著不足之處，比如對(duì)于檢索系統(tǒng)，由于近年來信息的多元化、復(fù)雜化，對(duì)信息處理技術(shù)的研究、發(fā)展、應(yīng)用提出了新的挑戰(zhàn)，跨越了單純文本的檢索，例如問答系統(tǒng)必須對(duì)關(guān)鍵字進(jìn)行語義分析與處理。這就要求

11、信息處理技術(shù)必須跟上信息發(fā)展的速度，在速度與性能方面具備更高的指標(biāo)。 要讓計(jì)算機(jī)能夠自動(dòng)地處理信息就必須借助分詞技術(shù)讓計(jì)算機(jī)理解自然語言。分詞技術(shù)作為自然語言處理的基礎(chǔ)環(huán)節(jié)，同時(shí)也是關(guān)鍵環(huán)節(jié)之一，它的質(zhì)量好壞直接影響到后續(xù)處理步驟的效果。其中，中文分詞由于中文結(jié)構(gòu)的特點(diǎn)，與西方國家文字相比更難于處理。漢語的詞匯與詞匯之間沒有顯式的邊界，漢語的分詞需要通過計(jì)算機(jī)對(duì)文字內(nèi)容的分析，來達(dá)到切分詞匯的目的。中文分詞已成為計(jì)算機(jī)處理漢語面臨的首要基礎(chǔ)性工作。只有提高中文分詞系統(tǒng)[2]的準(zhǔn)確率和工作效率，才能使自然語言處理系統(tǒng)穩(wěn)定高效地工作。 本文的主要目標(biāo)是通過對(duì)目前中文分詞關(guān)鍵技術(shù)的研究，設(shè)計(jì)并實(shí)

12、現(xiàn)最大正向匹配算法。本文的主要研究內(nèi)容為： (1)分析了當(dāng)前中文分詞的研究背景，介紹了中文分詞的研究意義。 (2)對(duì)中文分詞技術(shù)進(jìn)行了簡介，簡單介紹了中文分詞、中文分詞的應(yīng)用、中文分詞系統(tǒng)的目標(biāo)、中文分詞的基本問題。 (3)研究了三類基本的分詞算法：基于字符串匹配的分詞方法，基于統(tǒng)計(jì)的分詞方法，基于知識(shí)理解的分詞方法。舉例說明了實(shí)際應(yīng)用中如何使用合適的分詞算法。 (4) 介紹了目前中文分詞技術(shù)中常用的索引方法和詞典機(jī)制。 (5)對(duì)正向最大匹配算法進(jìn)行了實(shí)現(xiàn)與測試。 相對(duì)于研究內(nèi)容，本文的結(jié)構(gòu)安排為： 第一章 引言。本章首先介紹了本文的研究背景和研究意義，然后介紹了本文的主要工作

13、和論文的結(jié)構(gòu)安排。 第二章 中文分詞簡介。本章首先介紹了中文分詞的基本概念、中文分詞的應(yīng)用，接著介紹了中文分詞系統(tǒng)的目標(biāo)、中文分詞的基本問題等。 第三章 基本中文分詞算法。本章首先介紹了常用的中文分詞算法，包括基于字符串匹配的分詞方法，基于統(tǒng)計(jì)的分詞方法，基于知識(shí)理解的分詞方法；然后舉例說明了實(shí)際應(yīng)用中如何使用合適的分詞算法。 第四章 中文分詞詞典。本章首先介紹了中文分詞技術(shù)中的索引方法，然后又介紹了目前中文分詞技術(shù)中常用的詞典機(jī)制。 第五章 正向最大匹配算法的實(shí)現(xiàn)。本章根據(jù)正向最大匹配算法的流程，編寫了采用正向最大匹配算法的分詞程序，并對(duì)程序進(jìn)行介紹和測試。 第六章 結(jié)論。此部分

14、總結(jié)論文的所有工作，分析論文中存在的不足和一些未解決的問題。 二、中文分詞簡介 中文分詞是中文信息處理技術(shù)中最基礎(chǔ)、最關(guān)鍵的一個(gè)環(huán)節(jié)。所謂分詞，就是把一個(gè)句子中的詞匯按照使用時(shí)的意義切分出來。 （一）中文分詞的概念 將連續(xù)的字序列按照一定的規(guī)范重新組合成詞序列的過程被稱為分詞；中文分詞就是把中文的漢字序列分成有意義的詞。分詞只是中文信息處理的一部分，分詞本身并不是目的，而是后續(xù)處理過程的必要階段，是中文信息處理的基礎(chǔ)技術(shù)。 1、什么是中文分詞 分詞就是利用計(jì)算機(jī)識(shí)別出文本中詞匯的過程。在英文中，詞匯之間一般會(huì)有空格等比較明顯的分隔符。而中文中，是以字為基本書寫單位，只有段與段、句語

15、句之間有分隔符，而詞匯之間沒有分隔符。所以，雖然在英語中也存在分詞問題，但遠(yuǎn)沒有中文分詞那么復(fù)雜苦難。 比如：The table tennis bat is sold out。中文意思就是乒乓球拍 賣完了。對(duì)于通過空格和標(biāo)點(diǎn)來切分的英語例句，一般不會(huì)產(chǎn)生歧義。但是在中文中，“乒乓球拍賣完了”則因?yàn)槠古仪蚝推古仪蚺?、賣與拍賣都是詞語而又沒有明顯分隔而產(chǎn)生了：“乒乓球/拍賣/完了”和“乒乓球拍/賣/完了”兩種完全不同的意義。所以，要讓計(jì)算機(jī)完成上述過程，相對(duì)于英語，難度有質(zhì)的不同。 中文分詞的過程，就是要把一句話中有意義的詞匯都切分出來，并給出所有正確結(jié)果。由于中文詞匯中間是有分隔符的，所以對(duì)

16、中文詞組的正確識(shí)別就顯得很重要。詞是漢語中最小的有意義的獨(dú)立單位，但是這最小的單位卻是沒有顯式分割的。若要使計(jì)算機(jī)與人類達(dá)到自由無障礙的語言交互，就必須讓計(jì)算機(jī)能理解自然語言。只有當(dāng)漢字串組成的句子被準(zhǔn)確地轉(zhuǎn)化為詞之后，才能繼續(xù)進(jìn)一步工作。比如一個(gè)中英翻譯系統(tǒng)，如果連詞匯都不能正確切分，翻譯得到的英文是不可能符合原義的。 2、中文分詞的應(yīng)用 互聯(lián)網(wǎng)絕大部分需要分詞，其中典型的實(shí)例有： （1）漢字處理。這方面主要包括拼音輸入法、手寫識(shí)別、簡繁轉(zhuǎn)換等。 （2）信息檢索。如Google、Baidu、Yahoo等檢索工具。 雅虎中文網(wǎng)頁搜索技術(shù)部總監(jiān)張勤認(rèn)為：中文分詞是中文搜索技術(shù)的基礎(chǔ)，只

17、有做好了分詞，才能有好的搜索?？梢?，掌握了優(yōu)秀的分詞技術(shù)就可以在中文搜索中占有一席之地。 眾多優(yōu)秀的搜索引擎都有自己的分詞技術(shù)。如雅虎、百度，都是使用自己開發(fā)的分詞技術(shù)。谷歌也是采用的美國Basis technology提供的中文分詞技術(shù)。 （3）內(nèi)容分析。這方面主要包括了機(jī)器翻譯、廣告推薦、內(nèi)容監(jiān)控等。 現(xiàn)在的翻譯技術(shù)，無論是在線的還是單機(jī)的，在翻譯句子或段落的時(shí)候總會(huì)讓我們不知所措，語法錯(cuò)誤明顯，詞不達(dá)意等等。究其根本原因就是因?yàn)橹形姆衷~技術(shù)的滯后和一些多義詞匯選義的把握。 中文分詞的其中一個(gè)重要功能就是為詞語的計(jì)量分析，詞頻的統(tǒng)計(jì)提供可靠的依據(jù)，比如漢語中最常用的詞是哪個(gè)。這使我

18、們可以做一些廣告推薦（哪些廣告被更多次的提起）等。 （4）語音處理。 語音識(shí)別、語音合成等。 由于漢語中的多音字、一些發(fā)音習(xí)慣使得語音識(shí)別和合成過程中需要一個(gè)可靠地中文分詞作為基礎(chǔ)。比如： 發(fā)音的不同——如：的（dē），目的（d） 變聲——如：好酒（hǎojiu-->hojiu） 輕聲——如：桌子（zi） 要處理這些中文特有的由于發(fā)音習(xí)慣而引起的分詞問題，一個(gè)好的分詞技術(shù)顯然是必不可少的。 （二）中文分詞的目標(biāo) 中文分詞系統(tǒng)的目標(biāo)為達(dá)到信息處理的需求，達(dá)到所要求的相應(yīng)水平，具體來說，主要是準(zhǔn)確、高效、通用及適用四個(gè)方面。 1、準(zhǔn)確性 準(zhǔn)確率是分詞系統(tǒng)性能中最重要的核心

19、指標(biāo)?，F(xiàn)有的分詞系統(tǒng)中，有些準(zhǔn)確率已達(dá)到98％一99％，光從數(shù)據(jù)上看似乎已經(jīng)相當(dāng)高了，其實(shí)不然。這樣的分詞系統(tǒng)如果被用來支持中外文翻譯系統(tǒng)，現(xiàn)在假設(shè)平均每句語句有10個(gè)漢語單詞，那么以直前的概率來計(jì)算，10句語句中就會(huì)切分錯(cuò)1-2個(gè)詞，含有錯(cuò)誤分詞的1-2句就不可能被正確翻譯。于是僅僅因?yàn)榉衷~系統(tǒng)的準(zhǔn)確率欠佳，中外文翻譯系統(tǒng)的翻譯準(zhǔn)確率就降低了10-20個(gè)百分點(diǎn)。進(jìn)一步分析，對(duì)自動(dòng)分詞來說，其更大的作用是對(duì)大規(guī)模語料庫進(jìn)行加工，從而為上層應(yīng)用系統(tǒng)提供統(tǒng)計(jì)數(shù)據(jù)和各種知識(shí)。如果分詞產(chǎn)生錯(cuò)誤則會(huì)在最后的統(tǒng)計(jì)結(jié)果中累積起不可忽視的“垃圾”，從而給上層的應(yīng)用系統(tǒng)帶來相當(dāng)嚴(yán)重的影響。由此可見，分詞系統(tǒng)的準(zhǔn)

20、確率應(yīng)當(dāng)達(dá)到99．9％以上，這樣才能基本滿足上層的使用要求，換句話說，即使提高千分之一的準(zhǔn)確度，對(duì)實(shí)際應(yīng)用都是非常有意義的。 2、運(yùn)行效率 分詞是各種漢語處理應(yīng)用系統(tǒng)中共同的、基礎(chǔ)性的工作，這步工作消耗的時(shí)間應(yīng)盡量少，應(yīng)只占上層處理所需時(shí)間的一小部分，并應(yīng)使用戶沒有等待的感覺，在普遍使用的平臺(tái)上大約每秒鐘處理l萬字或5千詞以上為宜。 3、通用性 隨著互聯(lián)網(wǎng)的普及應(yīng)用，中文平臺(tái)的處理能力不能僅限于我國，僅限于字處理，僅限于日常應(yīng)用領(lǐng)域。作為各種高層次中文處理的共同基礎(chǔ)，自動(dòng)分詞系統(tǒng)必須具有很好的通用性。 （1)中文自動(dòng)分詞系統(tǒng)應(yīng)支持不同地區(qū)(包括中國香港、澳門、臺(tái)灣，以及新加坡和澳洲、

21、歐洲、美洲的華語社區(qū))的中文字符處理； （2)中文自動(dòng)分詞系統(tǒng)應(yīng)能適應(yīng)不同地區(qū)的不同用字、用詞，不同的語言風(fēng)格，不同的專名構(gòu)成方式(如港澳臺(tái)地區(qū)一些婦女名前冠夫姓，外國人名地名的漢譯方式與我國人名地名很不一樣)等； （3)中文自動(dòng)分詞系統(tǒng)應(yīng)能支持不同的應(yīng)用目標(biāo)，包括各種輸入方式、簡繁轉(zhuǎn)換、語音合成、校對(duì)、翻譯、檢索、文摘等等：支持不同領(lǐng)域的應(yīng)用，包括社會(huì)科學(xué)、自然科學(xué)和技術(shù)，以及日常交際、新聞、辦公等等； （4)中文自動(dòng)分詞系統(tǒng)應(yīng)當(dāng)同現(xiàn)在的鍵盤輸入系統(tǒng)一樣成為中文平臺(tái)的組成部分。為了做到足夠通用又不過分龐大，必須做到在詞表和處理功能、處理方式上能靈活組合裝卸，有充分可靠和方便的維護(hù)能力，

22、有標(biāo)準(zhǔn)的開發(fā)接口。同時(shí)，系統(tǒng)還應(yīng)該具有良好的可移植性，能夠方便地從一個(gè)系統(tǒng)平臺(tái)移植到另一個(gè)系統(tǒng)平臺(tái)上而無需很多的修改。當(dāng)然，就當(dāng)今的現(xiàn)狀來說，完全的通用性很難達(dá)到。 4、適用性 中文自動(dòng)分詞只是手段而不是最終目的，任何分詞系統(tǒng)產(chǎn)生的結(jié)果都是為某個(gè)具體的應(yīng)用服務(wù)的。好的分詞系統(tǒng)具有良好的適用性，可以方便地集成在各種各樣的漢語信息處理系統(tǒng)中。 （三）中文分詞的基本問題 我們可以看出，中文分詞技術(shù)必然是以后計(jì)算機(jī)發(fā)展必不可少的一項(xiàng)技術(shù)。但現(xiàn)在此技術(shù)在經(jīng)過了近30年的研究，仍存在諸多不足。而這主要是由于中文分詞有很多難點(diǎn)難以兼顧，總體歸納起來，中文分詞主要有三大困難：分詞規(guī)范、歧義識(shí)別以及未登

23、錄詞。 1、分詞規(guī)范 (1)“詞”是否有清晰的定義? 在每本漢語語法教科書中，我們都可以找到對(duì)“詞”的這樣一條定義：語言中有意義的能單說或用來造句的最小單位。這個(gè)定義相當(dāng)抽象，從計(jì)算的層面上講，這種模棱兩可的定義是不可計(jì)算的，即不可操作的。而產(chǎn)生如此定義涉及多個(gè)方面[3]： ①核心詞典問題：在進(jìn)行分詞時(shí)需要有一個(gè)核心(通用的、與領(lǐng)域無關(guān)的)詞典，即普通詞典，凡在該詞典中存在的詞，在分詞時(shí)就應(yīng)該切分出來。但是應(yīng)該將哪些詞組收入到核心詞典中去，雖然已經(jīng)提出各種收詞的條件，但是對(duì)每個(gè)詞組按照這些條件的進(jìn)行判斷卻難以操作，因此目前還沒有合理的可操作的理論和標(biāo)準(zhǔn)。 ②詞的變形結(jié)構(gòu)問題：漢語中的

24、動(dòng)詞和形容詞有些可以產(chǎn)生變形結(jié)構(gòu)，例如“打牌”、“開心”、“看見”、“相信”可能變形為“打打牌”、“開開心”、“看沒看見”、“相不相信”等。在對(duì)變形結(jié)構(gòu)進(jìn)行切分時(shí)，如果切分出“打打＼牌”、“開開＼心”就不怎么合理，“看＼沒＼看見”還說得過去，但“相＼不＼相信”就說不過去了。在進(jìn)行中文分詞時(shí)，對(duì)這些變形結(jié)構(gòu)的切分缺少可操作的、合理的規(guī)范。 ③詞綴的問題：例如語素“者”在現(xiàn)代漢語中單獨(dú)使用是沒有意義的，因此“作者”、“成功者”、“開發(fā)者”內(nèi)部不能切開。依據(jù)這個(gè)標(biāo)準(zhǔn)，“開發(fā)中國第一個(gè)操作系統(tǒng)軟件者”、“做出了巨大個(gè)人財(cái)產(chǎn)和精神犧牲者”、“克服許多困難而最終獲得成功者”內(nèi)部也不能切開，這樣復(fù)雜的結(jié)構(gòu)

25、在本質(zhì)上就與詞的定義相矛盾。又如職務(wù)名稱“外交部長”，語義上理解為“外交部之長”，切成“外交＼部長”、“外交部＼長”、“外交＼部＼長”或不予切分，都會(huì)有人提出異議。 ④非詞語素問題：現(xiàn)代的書面漢語并非純粹的“現(xiàn)代漢語”，其中夾雜著不少文言成分，如“為民除害”、“以逸待勞”、“幫困濟(jì)窮”等等。探尋白話文中夾雜文言成分的規(guī)律，是中文信息處理需要解決的一大問題。 (2)詞頻對(duì)領(lǐng)域有一定的敏感性。即使一些統(tǒng)計(jì)信息是從精心挑選的“平衡語料庫”中計(jì)算而來，將之應(yīng)用于不同領(lǐng)域也會(huì)產(chǎn)生偏移，從而導(dǎo)致切分過程中切分的精度下降。而且不同目標(biāo)的應(yīng)用對(duì)詞的切分規(guī)范的要求又有所不同，理論上講漢語自動(dòng)分詞規(guī)范，作為規(guī)

26、范，那么必須支持各種不同目標(biāo)的應(yīng)用，但不同目標(biāo)的應(yīng)用對(duì)詞的要求是不同的，甚至是有矛盾的。 ①以詞為單位的鍵盤輸入系統(tǒng)，為了提高輸入速度，一些互現(xiàn)頻率高的相互鄰接的幾個(gè)字也常常作為輸入的單位，比如：“每一”、“再不”、“這就”、“也就”等。 ②檢索系統(tǒng)，檢索系統(tǒng)的詞典注重術(shù)語和專名，并且一些檢索系統(tǒng)傾向于分詞單位較小化。比如，在構(gòu)造倒排文檔及創(chuàng)建索引時(shí)把“分布式計(jì)算”切成“分布式＼計(jì)算”，使得無論用“分布式計(jì)算”還是用“分布式”檢索，都能查到。 上述的兩個(gè)實(shí)例，前者把不是詞的幾個(gè)字放在了一起組成了“詞”，而后者把是詞的卻切分開了。事實(shí)上，許多中文信息處理系統(tǒng)，都是根據(jù)自己服務(wù)目的制定適合自

27、己需要的分詞系統(tǒng)。因此分詞系統(tǒng)的通用性、適應(yīng)性普遍不足，其分詞結(jié)果很難采用統(tǒng)一的通用的分詞標(biāo)準(zhǔn)來評(píng)價(jià)。 2、歧義識(shí)別 歧義是漢語中普遍存在的問題，因此切分歧義詞也是漢語分詞中的一大難題。形式上相同的一段文字，在不同的場景或語境中，可以切分出不同的結(jié)果，有不同的含義。 （1）交集型歧義 對(duì)于漢字串AJB, AJ, JB同時(shí)成詞。 例：他說的/確實(shí)/在理。他說/的確/實(shí)在/理。 （2）組合型歧義 對(duì)于漢字串AB, A, B, AB皆可獨(dú)立成詞。 例：門/把手/壞/了，請/把/手/拿/開。 將來， 學(xué)生會(huì) （3）混合型歧義 同時(shí)包含交集型和組合型歧義。 這些歧義有的會(huì)產(chǎn)

28、生不同的分詞結(jié)果，這些結(jié)果有時(shí)都有含義，這種情況就是真歧義；有時(shí)，只有一種結(jié)果是在所有真實(shí)語境中是有實(shí)在意義的。這種情況叫作偽歧義。 （4）真歧義 歧義字段在不同的語境中確實(shí)有多種分隔形式 例：地面積 這塊/地/面積/還真不小。 地面/積/了厚厚的雪。 （5）偽歧義 歧義字段單獨(dú)拿出來看有歧義，但在所有真實(shí)語境中，僅有一種分隔形式可接受。 例： 挨批評(píng) 挨/批評(píng)（√） 挨批/評(píng)（X） 對(duì)于交集型歧義字段，真實(shí)文本中偽歧義現(xiàn)象遠(yuǎn)多于真歧義現(xiàn)象。 3、未登錄詞 在文本處理過程中，會(huì)遇到很多詞典中未囊括的詞語。如：人名等。這些不斷增加的詞匯沒有可能和

29、必要都加入到詞典中。所以，分詞中遇到未登錄詞匯是不能避免的。 例如： 實(shí)體名詞和專有名詞 -人名：張三、李四 -地名：三義廟、白洋淀 -機(jī)構(gòu)名：方正、聯(lián)想 專業(yè)術(shù)語和新詞語 -專業(yè)術(shù)語：萬維網(wǎng)、主機(jī)板 -縮略詞：三個(gè)代表、掃黃打非 未登錄詞和歧義現(xiàn)象是影響中文分詞準(zhǔn)確率的兩大因素，兩者之中，未登錄詞造成的影響更為嚴(yán)重。在真實(shí)的文檔和語料庫中，專有名詞和術(shù)語占了很大比例，詞典在多數(shù)情況下很難包括這些詞。分詞算法能否對(duì)新詞進(jìn)行有效識(shí)別對(duì)應(yīng)用來說十分重要，目前新詞識(shí)別的準(zhǔn)確率已經(jīng)成為一個(gè)評(píng)價(jià)分詞系統(tǒng)好壞的重要指標(biāo)。 三、基本中文分詞算法 自從1983年，背景航空

30、航天大學(xué)實(shí)現(xiàn)了我國第一個(gè)實(shí)用性的自動(dòng)分詞系統(tǒng)到現(xiàn)在，國內(nèi)外的研究者在中文分詞領(lǐng)域進(jìn)行了廣泛的研究，提出了許多有效的算法。 （一）中文分詞算法介紹 現(xiàn)在最常用的中文分詞系統(tǒng)主要采用以下3種算法： 1、基于字符串匹配的分詞算法 這種方法又叫做機(jī)械分詞算法，機(jī)械分詞法按照一定策略將待切分字符串與機(jī)器里預(yù)先準(zhǔn)備的詞條進(jìn)行匹配，然后找出一個(gè)最長的結(jié)果。按照掃描方向的不同，串匹配分詞算法可以分為正向匹配和逆向匹配;按照不同長度優(yōu)先匹配的情況，可以分為最大(最長)匹配和最小(最短)匹配；按照是否與詞性標(biāo)注過程相結(jié)合，又可以分為單純分詞算法和分詞與標(biāo)注相結(jié)合的一體化算法。常用的幾種機(jī)械分詞算法如下：

31、 （1）正向最大匹配法(由左到右的方向)； 正向最大匹配分詞是基于詞典的分詞系統(tǒng)。所謂最大匹配，就是要求每一句的分詞結(jié)果中的詞匯總量要最少。正向最大匹配分詞又分為增字和減字匹配法[4]。增字匹配法需要一種特殊的詞典結(jié)構(gòu)支持，能夠達(dá)到較高的分詞效率。 減字法的流程為：首先讀入一句句子，取出標(biāo)點(diǎn)符號(hào)，這樣句子就被分成相應(yīng)的若干段，然后對(duì)每一段進(jìn)行詞典的匹配，如果沒有匹配成功就從段末尾減去一個(gè)字，再進(jìn)行匹配，重復(fù)上述過程，直到匹配上某一個(gè)單詞。整句句子重復(fù)這些流程，直到句子全部分解成詞匯為止。如果事先知道詞典中最長詞的長度，那么在一開始的匹配中，不用將分割出來的整段語句與詞典匹配，只需要以最長詞

32、的長度為最大切分單位進(jìn)行切分就可以了。 （2)逆向最大匹配法(由右到左的方向)； 逆向最大匹配分詞與正向最大匹配分詞相反，從句子結(jié)尾開始進(jìn)行分詞。 （3)最少切分(使每一句中切出的詞數(shù)最小)。 這種算法使每一句中切出的詞數(shù)最小。如果將上述各種方法相互組合，例如，可以將正向最大匹配算法和逆向最大匹配算法相結(jié)合來構(gòu)成雙向匹配法。由于漢語單字成詞的特點(diǎn)，正向最小匹配和逆向最小匹配一般很少使用?？梢园褭C(jī)械分詞作為初步的處理手段，然后再通過進(jìn)一步工作提高結(jié)果的正確率。 實(shí)際使用中還可以將上述各種算法相互組合，例如，可以將正向最大匹配算法和逆向最大匹配算法結(jié)合起來構(gòu)成雙向匹配法。由于漢語單字成詞

33、的特點(diǎn)，正向最小匹配和逆向最小匹配一般很少使用。一般說來，逆向匹配的切分精度略高于正向匹配，遇到的歧義現(xiàn)象也較少。統(tǒng)計(jì)結(jié)果表明[5]，單純使用正向最大匹配的錯(cuò)誤率為 1/169，單純使用逆向最大匹配的錯(cuò)誤率為1/245。但這種精度還遠(yuǎn)遠(yuǎn)不能滿足實(shí)際的需要。實(shí)際使用的分詞系統(tǒng)，都是把機(jī)械分詞作為一種初分手段，然后通過利用各種其它的語言信息來進(jìn)一步提高切分的準(zhǔn)確率。 2、基于理解的分詞算法 這種分詞算法是通過讓計(jì)算機(jī)模擬人對(duì)句子的理解，達(dá)到識(shí)別詞的效果。其基本思想就是在分詞的同時(shí)進(jìn)行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括三個(gè)部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。

34、在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對(duì)分詞歧義進(jìn)行判斷，即它模擬了人對(duì)句子的理解過程。這種分詞方法需要使用大量的語言知識(shí)和信息。由于漢語語言知識(shí)的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機(jī)器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗(yàn)階段。 3、基于統(tǒng)計(jì)的分詞算法 從形式上看，詞是穩(wěn)定的字的組合，因此在上下文中，相鄰的字同時(shí)出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個(gè)詞。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反映成詞的可信度[4]，可以對(duì)語料中相鄰共現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們的互現(xiàn)信息。定義兩個(gè)字的互現(xiàn)信息，計(jì)算兩個(gè)漢字X、Y的相鄰共現(xiàn)概率。

35、互現(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當(dāng)緊密程度高于某一個(gè)閾值時(shí)，便可認(rèn)為此字組可能構(gòu)成了一個(gè)詞。這種方法只需對(duì)語料中的字組頻度進(jìn)行統(tǒng)計(jì)，不需要切分詞典，因而又叫做無詞典分詞法或統(tǒng)計(jì)取詞方法。但這種方法也有一定的局限性，會(huì)經(jīng)常抽出一些共現(xiàn)頻度高、但并不是詞的常用字組，例如“這一”、“之一”、“有的”、“我的”、“許多的”等，并且對(duì)常用詞的識(shí)別精度差，時(shí)空開銷大。它的優(yōu)點(diǎn)在于可以發(fā)現(xiàn)所有的切分歧義，但是統(tǒng)計(jì)語言模型的精度和決策算法在很大程度上決定了解決歧義的方法，需要大量的標(biāo)注語料，并且分詞速度也因搜索空間的增大而有所緩慢。實(shí)際應(yīng)用的統(tǒng)計(jì)分詞系統(tǒng)都要使用一部基本的分詞詞典(常用詞詞典)進(jìn)行串

36、匹配分詞，同時(shí)使用統(tǒng)計(jì)方法識(shí)別一些新的詞，即將串頻統(tǒng)計(jì)和串匹配結(jié)合起來，既發(fā)揮匹配分詞切分速度快、效率高的特點(diǎn)，又利用了無詞典分詞結(jié)合上下文識(shí)別生詞、自動(dòng)消除歧義的優(yōu)點(diǎn)。 （二）根據(jù)具體應(yīng)用使用合適的分詞算法 在實(shí)際應(yīng)用中，對(duì)于某一具體的應(yīng)用系統(tǒng)，并不是單純使用某種分詞算法就能解決問題，我們可以根據(jù)具體應(yīng)用的所需滿足條件使用不同的方法。在此以中文信息檢索中所用到的分詞算法為例進(jìn)行說明。 1、混合分詞 對(duì)于實(shí)際應(yīng)用中的中文信息檢索系統(tǒng)來說，當(dāng)弄不清楚使用哪種分詞算法更好的話，可以試著合并使用多種方法，混合分詞就是一種簡單且容易實(shí)現(xiàn)的方法，也是大型檢索系統(tǒng)中常用的一種方法，使用混合分詞方法

37、能夠涵蓋更多的詞匯。 混合分詞的原理就是“先用專業(yè)詞典進(jìn)行一遍分詞，再用普通詞典進(jìn)行一遍分詞”，我們用一個(gè)實(shí)例對(duì)為何要進(jìn)行兩次分詞進(jìn)行說明。例如，對(duì)“搜索引擎知識(shí)”這句話進(jìn)行分詞，如果我們的詞典中含有“搜索引擎”這個(gè)詞，那么這句話的切分結(jié)果就是“搜索引擎＼知識(shí)”。如果詞典中沒有“搜索引擎”這個(gè)詞，而只含有“搜索”，“引擎”，“知識(shí)”這三個(gè)詞，那么這句話的切分結(jié)果就是“搜索＼引擎＼知識(shí)”。因此我們可以得到這樣一個(gè)結(jié)論，對(duì)同一文本進(jìn)行切分，如果使用的詞典不同，會(huì)導(dǎo)致不同的分詞結(jié)果。顯然，如果用第一種方法分詞，當(dāng)一個(gè)用戶想要查找包含“搜索”這個(gè)關(guān)鍵字的相關(guān)資源時(shí)，他就不會(huì)搜索到結(jié)果。同理，假設(shè)檢索

38、系統(tǒng)不對(duì)用戶輸入的詞進(jìn)行切分，如果用第二種方法分詞，當(dāng)一個(gè)用戶想要查找包含“搜索引擎”這個(gè)關(guān)鍵字的相關(guān)資源時(shí)，同樣也找不到結(jié)果。所以，只進(jìn)行一遍分詞必然有一定得局限性，如果采用兩遍、甚至多遍分詞，便會(huì)解決上述問題。對(duì)于上面這個(gè)例子，我們采取組織兩個(gè)詞典的措施：一個(gè)為專業(yè)詞典，一個(gè)為普通詞典。其中，專業(yè)詞典放置一些比較專業(yè)的詞組，比如名人人名、專有名詞、地點(diǎn)名、機(jī)構(gòu)名等，普通詞典就是我們常 用的詞組。那么我們可以將“搜索引擎”放入專業(yè)詞典，將“搜索”、“引擎”放入普通詞典。先用專業(yè)詞典進(jìn)行一遍分詞，再用普通詞典進(jìn)行一遍分詞，最后將結(jié)果合并到一起，那么結(jié)果如“搜索引擎＼搜索＼引擎＼知識(shí)”。這樣既

39、滿足了查詢“搜索引擎”的要求，又滿足了查詢“搜索”的要求。 據(jù)了解[6]，百度的分詞采取了至少兩個(gè)詞典，一個(gè)是普通詞典，一個(gè)是專用詞典。而且是專用詞典先切分，然后將剩余的片斷交由普通詞典來切分。一般專業(yè)的搜索引擎對(duì)分詞速度要求要達(dá)到1M／s以上，因此為了提高處理速度，百度的普通詞典切分采用雙向最大匹配算法，這種分詞算法舍棄了一定得精度來達(dá)到極快的切分速度。因?yàn)閷?duì)于搜索引擎來說，在查詢切分和文檔切分時(shí)采用相同的分詞算法，如果有一些文檔切分是分詞是錯(cuò)誤，在查詢切分時(shí)也產(chǎn)生相同的切分錯(cuò)誤。那么即使兩次切分階段錯(cuò)誤，但最后相同錯(cuò)誤卻使匹配成功，使得仍然可以正確檢索到結(jié)果。 2、基于字的切分法 現(xiàn)

40、實(shí)中，無論一個(gè)詞典所包含的詞組有多么齊全，其還是包含不了一些新出現(xiàn)的詞組，所以有些詞在沒有更新新詞的詞典中是分不出來的，尤其在如今的互聯(lián)網(wǎng)中，新詞每天都在出現(xiàn)，數(shù)量更是每天都在增長。想對(duì)這些分不出來的新詞進(jìn)行處理，就需要采用多元切分的混合分詞方法。 一元分詞和二元分詞是比較流行的非詞典式分詞方法。一元分詞就是將“ABCDE”切分成“A＼B＼C＼D＼E”，這個(gè)例子中，就是將一個(gè)詞拆成一個(gè)個(gè)獨(dú)立的字，這稱之為一元分詞。同樣，二元分詞就是將“ABCDE”切分成“AB＼BC＼CD＼DE”，在這個(gè)例子中，就是將一個(gè)詞拆成兩兩相連的詞。在實(shí)際應(yīng)用中，對(duì)分不出來的新詞我們也可以不分詞，比如將“ABCDE”

41、切分成“ABCDE”，這樣，我們就較好的保持了新詞的完整性。 那么，在實(shí)際的應(yīng)用中，我們就可以把三種分詞方法全部利用上，以求達(dá)到最好的效果。如下一個(gè)詞條“ABCDEFGHIJ”，假設(shè)這個(gè)詞條首先通過詞典分割成“ABCDE＼FGH＼IJ”。假設(shè)FGH與IJ是出現(xiàn)在詞典中的字條，ABCDE是分不出來的詞， 那么對(duì)ABCDE 進(jìn)行三遍混合分詞， 最終結(jié)果便為“A＼B＼C＼D＼E＼AB＼BC＼CD＼DE＼ABCDE＼FGH＼IJ”。 四、中文分詞詞典 詞典是中文分詞技術(shù)中重要組成部分，其實(shí)詞典就是各種詞的集合，詞典告訴計(jì)算機(jī)什么樣的才是一個(gè)詞，程序分詞時(shí)自動(dòng)與詞典進(jìn)行對(duì)比。 （一）詞典的

42、索引 使用索引來組織數(shù)量龐大的文件是一種高效的方法。目前在各種中文處理系統(tǒng)中常用于組織詞典的索引方法主要有兩種：一種是Hash索引、一種是Tile索引樹。 1、Hash索引 Hash函數(shù)是一個(gè)映像，其將關(guān)鍵字的集合映射到某個(gè)地址的集合。用Hash表的方法構(gòu)造詞典就是將關(guān)鍵字與表項(xiàng)的存儲(chǔ)位置建立一個(gè)對(duì)應(yīng)的函數(shù)關(guān)系。以首字Hash詞典機(jī)制的原理為例，據(jù)漢字機(jī)內(nèi)碼的編碼規(guī)律可知，我們就可以通過一對(duì)一映射的Hash函數(shù)實(shí)現(xiàn)詞首字的快速查找。根據(jù)Hash函數(shù)的定義可知，Hash函數(shù)一般都無法避免沖突，所以通常還要有相應(yīng)的沖突處理方法，因此對(duì)于詞組中的剩余字串最快的只能通過二分查找來進(jìn)行查找。我們的

43、思想是基于Hash索引的詞典機(jī)制就是構(gòu)造一種Hash函數(shù)來計(jì)算詞語的Hash值，將Hash值相同的詞組放入一個(gè)通常稱之為“桶”的集合內(nèi)。匹配時(shí)先計(jì)算待查詞的Hash值，得到首字的存儲(chǔ)位置，然后再進(jìn)入相應(yīng)的Hash桶內(nèi)再進(jìn)行二分查找。 2、Trie樹 鍵樹[7]又稱數(shù)字查找樹。它是一棵度>=2的樹，樹中的每個(gè)結(jié)點(diǎn)中不是包含一個(gè)或幾個(gè)關(guān)鍵字，而是只含有組成關(guān)鍵字的符號(hào)。例如，若關(guān)鍵字是數(shù)值，則結(jié)點(diǎn)中只包含一個(gè)數(shù)位；若關(guān)鍵字是英文單詞，則結(jié)點(diǎn)中只包含一個(gè)英文字母。鍵樹中每個(gè)結(jié)點(diǎn)的最大度d和關(guān)鍵字的“基”有關(guān)，若關(guān)鍵字是英文單詞，則d=27，若關(guān)鍵字是數(shù)值，則d=11。鍵樹的深度h則取決于關(guān)鍵字中

44、字符或數(shù)位的個(gè)數(shù)。若以樹的多重鏈表表示鍵樹，則樹的每個(gè)結(jié)點(diǎn)中應(yīng)含有d個(gè)指針域，此時(shí)的鍵樹稱為Trie樹。 （二）常用詞典結(jié)構(gòu) 常用的主要詞典結(jié)構(gòu)主要有以下3種[8]： 1、有序線性詞典結(jié)構(gòu) 如表1所示，這是最簡單的詞典結(jié)構(gòu)，詞典正文是以詞為單位的有序表，初始化時(shí)讀取到內(nèi)存中，詞典正文中通過整詞二分進(jìn)行定位。無論用正向還是逆向最大匹配分詞方法，都可以使用有序線性詞典結(jié)構(gòu)。這種詞典結(jié)構(gòu)算法簡單、易于實(shí)現(xiàn)、有效空間使用率高，缺點(diǎn)是查找效率低，而且更新代價(jià)高。在添加新詞時(shí)需要移動(dòng)詞典中的詞條來保證有序性，在詞典相當(dāng)大時(shí)，需要花費(fèi)相當(dāng)長的時(shí)間。 表1 有序線性詞典結(jié)構(gòu) 一一 一一說明

45、一一對(duì)應(yīng) 一一道來 一丁不視 …… 2、基于整詞二分的分詞詞典結(jié)構(gòu) 如圖1所示，該機(jī)制的詞典結(jié)構(gòu)分為詞典正文、詞索引表、首字散列表等三級(jí)。詞典下文是以詞為單位的有序表，詞索引表是指向詞典正文中每個(gè)詞的指針表。通過首字散列表的哈希定位和詞索引表很容易確定指定詞在詞典正文中的可能位置范圍，進(jìn)而在詞典正文中通過整詞二分進(jìn)行定位。 啊 阿 …… 大 …… 004 089 …… 794 …… 。 。 …… 。 …… 首字hash表 入口項(xiàng)個(gè)數(shù) 第一項(xiàng)指針 …… 詞索引表 詞典正文指針 啊 啊哈

46、 啊呀 啊喲 阿 啊Q …… 詞典正文 圖1 基于整詞二分的分詞詞典結(jié)構(gòu) 3、基于TRIE索引樹的分詞詞典機(jī)制 TRIE索引樹是一種以樹的多重鏈表形式表示的鍵樹?；赥RIE索引樹的分詞詞典機(jī)制由首字散列表和TRIE索引樹結(jié)點(diǎn)兩部分組成。TRIE索引樹的優(yōu)點(diǎn)是在對(duì)被切分語句的一次掃描過程中，不需預(yù)知待查詢詞的長度，沿著樹鏈逐字匹配即可；缺點(diǎn)是它的構(gòu)造和維護(hù)比較復(fù)雜，而且都是單詞樹枝(一條樹枝僅代表一個(gè)詞)，浪費(fèi)了一定的空間。 五、正向最大匹配算法的實(shí)現(xiàn) 本章研究如何實(shí)現(xiàn)正向最大匹配算法，根據(jù)算法的流程，介紹了重點(diǎn)步

47、驟的實(shí)現(xiàn)原理與方法，最后進(jìn)行實(shí)驗(yàn)與分析。 （一）正向最大匹配算法 在第三章中對(duì)現(xiàn)今的中文分詞算法進(jìn)行了介紹，其中介紹了基于字符串匹配的分詞算法，又叫機(jī)械分詞算法，機(jī)械分詞算法里又包含了一種正向最大匹配算法，正向最大匹配算法里又有兩個(gè)分支：增字匹配法和減字匹配法。這里要研究的是用減字匹配法實(shí)現(xiàn)正向最大匹配。 這種方法存在如下缺陷：首先，詞典詞長限制，詞長過短，長詞就會(huì)被切錯(cuò)；詞長過長，查找匹配效率就會(huì)比較低。其次，掩蓋分詞歧義，不能發(fā)現(xiàn)交叉型歧義。最后，最大的匹配并不一定是想要的分詞結(jié)果。但這種方法的優(yōu)點(diǎn)在于實(shí)現(xiàn)簡單，而且切分速度快。 減字法的流程為：首先讀入一句句子，取出標(biāo)點(diǎn)符號(hào)，這樣

48、句子就被分成相應(yīng)的若干段，然后對(duì)每一段進(jìn)行詞典的匹配，如果沒有匹配成功就從段末尾減去一個(gè)字，再進(jìn)行匹配，重復(fù)上述過程，直到匹配上詞典上的某個(gè)詞組或只剩下一個(gè)字符，接著將句子剩余的部分重復(fù)上述流程，直到將句子全部分解成原子或詞典中存在的詞組。流程圖如圖2所示。 匹配 讀入詞典文件 讀入一個(gè)句子 分詞結(jié)果 詞典 開 始 結(jié)束 待切分的臨時(shí)變量 匹配失敗，句子減一字，繼續(xù)匹配 匹配成功 圖2 減字分詞法過程 上圖就是減字法的分詞過程，為了說明該方法是如何分詞的，我們利用減字法進(jìn)行最大匹配分詞，之所以稱為最大匹配，就是要

49、求每一句的切分結(jié)果中詞組的總數(shù)最少。比如在“我們是中華人民共和國的公民”這句話中，我們可以清楚地判斷，如果在字典中進(jìn)行匹配，只要匹配成功就切分出來，那么這句話可能被切分成“我們＼是＼中華＼人民＼共和國＼的＼公民”，該結(jié)果中一共包含7個(gè)詞。但是，為了實(shí)現(xiàn)最大匹配，我們將把“中華人民共和國”作為一個(gè)整體的詞進(jìn)行處理。因此就要求將上面這句話切分為“我們＼是＼中華人民共和國＼的＼公民”，一共是5個(gè)詞，根據(jù)最大匹配的原則，我們選擇第二種分詞結(jié)果。以“我們是中華人民共和國的公民”為例，如果事先知道詞典的最長詞長，那么將減少很多步驟，從而提高分詞速度。這里假設(shè)詞典中最長詞長為7。那么實(shí)例的整個(gè)匹配過程如下表

50、2所示： 表2 實(shí)例的匹配步驟 步驟 操作的句子 操作 分詞結(jié)果 1 我們是中華人民共和國的公民 只取7個(gè)字 2 我們是中華人民 詞典匹配失敗 3 我們是中華人 詞典匹配失敗 …… …… …… 我們 詞典匹配成功 我們 是中華人民共和 減詞并取前7個(gè)字 是中華人民共和 詞典匹配失敗 我們 …… …… …… 是 詞典匹配成功 我們\是 中華人民共和國 減詞并取前7個(gè)字 中華人民共和國 詞典匹配成功 我們\是\中華人民共和國 …… …… …… NULL 減

51、詞 我們\是\中華人民共和國\的\公民 （二）采用正向最大算法的分詞程序設(shè)計(jì) 從表2可以很清晰的看出減字法工作的過程，我們現(xiàn)在開始用C語言實(shí)現(xiàn)這個(gè)算法。 對(duì)于減字法實(shí)現(xiàn)正向最大匹配，其基本思想是：先從網(wǎng)絡(luò)中下載一個(gè)詞典，統(tǒng)計(jì)詞典的總大小和詞典中最長的詞的字符數(shù)。假設(shè)詞典中最長的詞有i個(gè)漢字字符，先對(duì)輸入文本長度進(jìn)行判定，若輸入文本長度小于或等于i，則只在最大詞長范圍內(nèi)進(jìn)行處理就行了，若輸入文本長度大于i，則用輸入文本的當(dāng)前字符串中的前i個(gè)字作為匹配字段，與字典進(jìn)行匹配，若字典中存在這樣一個(gè)i個(gè)字的詞，則匹配字段就被切分出來。如果沒有找到這樣一個(gè)

52、詞，則將字段中的最后一個(gè)字刪除，對(duì)剩下的字重新進(jìn)行匹配，以此類推，直到匹配成功或剩余字串長度為零為止，然后取下一個(gè)i個(gè)字的字串重復(fù)以前的操作，直到輸入文本被掃描完為止。 設(shè)有句子S = C1C2C3…Cn, 詞Wi =W1W2W3…Wm , 其中m 為詞典中最長詞的字?jǐn)?shù),對(duì)算法的描述如下： (1) 初始化i,賦值為0，指針Pi指向輸入字串的初始位置。 (2) 統(tǒng)計(jì)當(dāng)前指針Pi 到字串末端的長度n。如果n等于1，則直接跳轉(zhuǎn)到第三步，若不等于1則將詞典中最長詞的字?jǐn)?shù)賦予m,然后比較n與m的大小，若n

53、 如果Wi 是詞典中的詞，則在Wi 后添加一個(gè)切分標(biāo)志，轉(zhuǎn)到； 如果Wi 不是詞典中的詞且長度大于1，則將Wi 從右端去掉一個(gè)字轉(zhuǎn)到；若Wi 的長度等于1，則在Wi 后添加一個(gè)切分標(biāo)志，將Wi 作為單字詞添加到詞典中，然后轉(zhuǎn)到； 根據(jù)Wi 的長度修改指針Pi 的位置，如果Pi 指向字串的末端，則直接轉(zhuǎn)到（4），否則i=i+1，返回1； （4）輸出結(jié)果，結(jié)束任務(wù)。 通過上述設(shè)計(jì)思想對(duì)程序進(jìn)行編寫，本程序使用C語言，開發(fā)環(huán)境為Visual Studio 6.0中Win32 SDK平臺(tái)。程序功能實(shí)現(xiàn)對(duì)TXT文本使用正向最大匹配算法進(jìn)行分詞且輸出結(jié)果，實(shí)現(xiàn)對(duì)文本的簡單的編輯功能。其中分詞

54、功能分為屏幕分詞和文件分詞兩種方式。屏幕分詞只允許打開字節(jié)數(shù)在32768以下的文章，結(jié)果直接顯示在屏幕上，而且可以對(duì)其進(jìn)行輸出保存；文件分詞的結(jié)果并不在屏幕上進(jìn)行顯示，而是直接將結(jié)果保存成一個(gè)文本文檔，文檔名默認(rèn)為源文件名后加_pos。 程序主面板如圖3所示，其中“分詞”選項(xiàng)中可以選擇是使用屏幕分詞還是使用文件分詞。使用屏幕分詞時(shí)先點(diǎn)擊“文件”菜單下的“打開”按鈕，打開某一文檔，默認(rèn)后綴是txt文本文檔。打開后再點(diǎn)擊“屏幕分詞”按鈕，程序便開始對(duì)打開文檔進(jìn)行分詞，結(jié)果直接輸出到程序主面板的空白處。點(diǎn)擊菜單“文件”中的“保存”按鈕可以對(duì)輸出的結(jié)果進(jìn)行保存，程序自動(dòng)輸出一個(gè)文本文檔。

55、 圖3 程序主面板 點(diǎn)擊“分詞”菜單中的“文件分詞”選項(xiàng)后會(huì)彈出如圖4所示的對(duì)話框，點(diǎn)擊“輸入文件”后的“瀏覽”按鈕，可以選擇待分析的文件，點(diǎn)擊“輸出文件”后的“瀏覽”按鈕可以選擇分詞結(jié)果文件的保存位置。當(dāng)兩項(xiàng)選擇好之后，點(diǎn)擊“分詞”按鈕程序就會(huì)開始分詞，分詞成功后會(huì)彈出提示對(duì)話框，如圖5所示。 圖4 文件分詞對(duì)話框 圖5 文件分詞成功提示對(duì)話框 編輯選項(xiàng)中包含了一些可以對(duì)文檔進(jìn)行簡單編輯操作的選項(xiàng)，如圖6所示

56、。 圖6 程序編輯選項(xiàng) 下邊對(duì)分詞的實(shí)現(xiàn)部分進(jìn)行介紹，首先，聲明變量： extern char tt[][40]; char * source,* result; //文件暫存數(shù)組 int sum; //字典長度 FILE *fp1,*fp2; //定義兩個(gè)文件指針 long filelen; //輸入文件的長度 char scrbuf[MD]; //屏幕文件緩沖區(qū) char scrres[SD];

57、 //屏幕文件結(jié)果區(qū) 最大正向匹配算法是離不開詞典的，分詞時(shí)需要對(duì)詞典內(nèi)的詞進(jìn)行比較，定義比較函數(shù)為： int compare(const void* a,const void* b) {return strcmp((char*)a,(char*)b);} 對(duì)詞典進(jìn)行比較時(shí)查找方法使用折半查找算法，也就是二分查找，此算法的代碼為： int binsearch(int Len,char *aidkey){ int low,high,mid; low=0;high=Len-1; while(low<=high){ mid=(low+hi

58、gh)/2; if(strcmp(aidkey,tt[mid])==0) return mid; //查找成功 else if(strcmp(tt[mid],aidkey)>0) high=mid-1; //修改查找區(qū)間上界 else low=mid+1; //修改查找區(qū)間下界 } return -1; //查找失敗 } 下面對(duì)分詞功能進(jìn)行實(shí)現(xiàn)，由于所采用的屏幕控件所能容納的大小有限，最多為65535個(gè)字節(jié)，所以，考慮到極端情況，為了使分詞結(jié)果能在屏幕上完全的顯示出來，本程序只允

59、許打開字節(jié)數(shù)在32768以下的文章，如果超出，給出警告信息，同時(shí)只顯示其前面32768個(gè)字節(jié)。在實(shí)際應(yīng)用中難免會(huì)碰到一些較大的文檔，使用屏幕分詞的話需要進(jìn)行多次操作，這樣很不方便，所以本程序又添加了一種文件分詞功能，可以進(jìn)行不限大小的分詞，此功能直接對(duì)文件進(jìn)行分詞操作，并不直接顯示在屏幕上，而是生成一個(gè)文檔，生成的文檔名默認(rèn)為源文件名+_pos。 首先初始化函數(shù)： int initialize(){ sum=53335; //字典來自網(wǎng)絡(luò)，文件名為wordlist qsort(tt,sum,40*sizeof(char),compare);

60、//對(duì)字典進(jìn)行排序 return 1; } 屏幕分詞函數(shù)： void scrposcutword(){ int i,j,k; //普通變量 int end; //為1標(biāo)示已經(jīng)掃描完待分析文件，反之為0 int mask=0; //遇到不能識(shí)別字符則標(biāo)記為1，否則為0 int bp,sb,rp; //bp為字符串已識(shí)別指針，sb為臨時(shí)用指針,sp為結(jié)果數(shù)組指針 char ch[2],buffer[37]; filelen=strlen(scrbuf); strcpy(scrres,""); //詞典中最長的詞組為36個(gè)字符，所

61、以每次從待分詞文本中讀取36個(gè)詞組然后與詞典進(jìn)行比較，以下是采用正向最大匹配算法的分詞主程序部分： bp=0;rp=0; while(1){ buffer[0]=0; sb=bp; for(i=0;i<36;i++) //從源數(shù)組中讀入36個(gè)字符 { if(sb==filelen&&i==0) { end=1; break; } //讀到的第一個(gè)字符為文件尾，于是退出 if(sb==filelen) //遇到文件尾，跳出循環(huán) break; ch[1]=0; ch[0]=scrbuf[sb]; strcat(buffer,ch); sb++; }

62、if(end==1)break; for(i=i-1;i>=0;i--) { k=strlen(buffer); j=-1; if(strcmp(buffer,"0")==0||strcmp(buffer,"1")==0|| strcmp(buffer,"2")==0||strcmp(buffer,"3")==0||strcmp (buffer,"4")==0||strcmp(buffer,"5")==0||strcmp(buffer,"6")==0||strcmp(buffer,"8")==0||strcmp(buffer,"7")==0 ||strcmp(buff

63、er,"9")==0) goto A; j=binsearch(sum,buffer); if(j!=-1){ //如果查找到，則輸出查找到的內(nèi)容，并將bp指針往前移相應(yīng)位置 if(mask==1) { mask=0; scrres[rp]=|; rp++; scrres[rp]=0; } strcat(scrres,buffer); rp+=k; scrres[rp]=|; rp++; scrres[rp]=0; bp=bp+k; break; } else //如果查不到 { A： if

64、(i==1){ //若還剩2個(gè)字節(jié)，則判斷第一個(gè)字節(jié)，若大于0，說明不是漢字，輸出一個(gè)字節(jié) buffer[2]=0; //若小于0，說明該漢字不在此庫中，輸出該字。并將bp指針往前移相應(yīng)位置 if(buffer[0]<0) {strcat(scrres,buffer); rp+=2; scrres[rp]=0;bp=bp+2; mask=1; break;} else{ buffer[1]=0; strcat(scrres,buffer); rp+=1; scrres[rp]=0; bp=bp+1; mask=1; break; } } if(i==

65、0)//若還剩1個(gè)字節(jié)，說明肯定是不能識(shí)別字符，則 直接輸出這個(gè)字節(jié)，并將bp指針往前移1個(gè)字節(jié) { buffer[1]=0; strcat(scrres,buffer); rp++; scrres[rp]=0; bp=bp+1;mask=1; break; } buffer[i]=0; //將buffer最后一位去掉，再進(jìn)行匹配 } } } scrres[rp]=0; } 以上的是屏幕分詞的主程序部分，文件分詞主程序部分與其基本相同，現(xiàn)只列出文件分詞初始化函數(shù)： int prep

66、oscutword() { int i,j; char c; i = fseek(fp1,0,SEEK_END); //確定待分析文件的長度，用ftell函數(shù) filelen = ftell( fp1 ); rewind(fp1); //計(jì)算回車的個(gè)數(shù)，因?yàn)槲募僮鲿r(shí)回車只算一個(gè)字符，而之前的統(tǒng)計(jì)認(rèn)為回車是2個(gè)字符 j=0; //所以要減去回車的次數(shù) while(1) { c=fgetc(fp1); if(c==10) j++; if(c==EOF) break; } filelen-=j; source = (char *)malloc( filelen*sizeof(char) ); //動(dòng)態(tài)為待分析文件分配內(nèi)存 if( source == NULL ) //如果內(nèi)存分配失敗，則返回 return 0; { MessageBox(hWnd,"內(nèi)存分配失??！","錯(cuò)誤",MB_OK); } rewind(fp1); //將文件指