【正文】 理 [3]” 。與西方語言文字處理所不同的是，計(jì)算機(jī)在對中文的處理上總是遇到很多的難題： (1)中文不像英文等語言有空格這個(gè)天然的分詞符號； (2)中文的同意詞、同音字等非常之多，由于地域廣闊，各地的用詞習(xí)慣也有不同，不同地域的人輸入的文章和句子都存在著很大的不同； (3)大量虛詞的存在，增加大了智能識別和分詞的難度。但對于中文文本來說，正如上段文字所列舉的種種原因，需要因循一個(gè)特定的規(guī)則對中文文本進(jìn)行切分或分詞。 中文分詞技術(shù)的發(fā)展現(xiàn)狀 計(jì)算機(jī)對中文語言和西文語言的理解原理和方式基本相同， 但由于漢 語本身的特點(diǎn)，必須引入對于中文語言的處理技術(shù)，而漢語自動(dòng)分詞技術(shù)就是其中很關(guān)鍵的部分。中文分詞的準(zhǔn)確與否，常常直接影響到對搜索結(jié)果的相關(guān)度排序。因此對于搜 索引擎來說，分詞的準(zhǔn)確性和速度，二者都需要達(dá)到很高的要求。圍繞這些基本問題，十幾年來產(chǎn)生了各種漢語分詞方法 [5]。 基于字典的方法 又叫機(jī)械分詞方法，它是按照一定的策略將待分析的漢語字串與一個(gè)“充分大的”機(jī)器詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè) 字符串，則匹配成功（識別出一個(gè)詞）。常用的幾種機(jī)械分詞方法有正向最大匹配、逆向最大匹配、最少切分（使每一句中切出的詞數(shù)最?。?。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好 的反映成詞的可信度。互現(xiàn)武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 4頁 信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。這種方法只需對語料中的字組頻度進(jìn)行統(tǒng)計(jì)，不需要切分詞典，因而又叫做無詞典分詞法或統(tǒng)計(jì)取詞方法。 在實(shí)際應(yīng)用中，還可以將上述各種方法相互組合。 因此，實(shí)際使用的分詞系統(tǒng)，都是把機(jī)械分詞作為一種初分手段，然后利用各種其它的語言信息來進(jìn)一步提高切分的準(zhǔn)確率。它通常包括三個(gè)部分：分詞子系統(tǒng)、句法語義子系統(tǒng)、總控部分。但是這種分詞方法需要使用大量的語言知識和信息，而由 于漢語語言知識的籠統(tǒng)、復(fù)雜，難以將各種語言信息組織成機(jī)器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗(yàn)階段。目前比較優(yōu)秀的中文自動(dòng)分詞系統(tǒng)主要有 [6]： 武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 5頁 清華大學(xué) SEG 分詞系統(tǒng) 此系統(tǒng)提供了帶回溯的正向、反向、雙向最大匹配法和全切分 評價(jià)切分算法，由用戶來選擇合適的切分算法。 清華 大學(xué) SEGTAG 系統(tǒng) 此系統(tǒng)著眼于將各種各類的信息進(jìn)行綜合，以便最大限度地利用這些信息提高切分精度。通過實(shí)驗(yàn)，該系統(tǒng)可以達(dá)到一個(gè)較高的切分精度，能夠處理未登錄詞比較密集的文本 ,切分速度約為 30 字 /秒。切詞過程考慮到了所有的切分可能，并運(yùn)用漢語句法等信息從各種切分可能中選擇出合理的切分結(jié)果。一、預(yù)處理模塊，利 用特殊的標(biāo)記將輸入的文本分割成較短的漢字串，這些標(biāo)記包括標(biāo)點(diǎn)符號、數(shù)字、字母等非漢字符，還包括文本中常見的一些字體、字號等排版信息。最后，此系統(tǒng)還包括一個(gè)未登錄詞識別模塊，實(shí)驗(yàn)過程中，對中文姓氏的自動(dòng)辨別達(dá)武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 6頁 到了 70%的準(zhǔn)確率。 哈工大統(tǒng)計(jì)分詞 系統(tǒng) 此系統(tǒng)能夠利用上下文識別大部分生詞，解決一部分切分歧義。 杭州大學(xué)改進(jìn)的 MM 分詞系統(tǒng) 系統(tǒng)的詞典采用一級首字索引結(jié)構(gòu)，詞條中包括了“非連續(xù)詞”（形如C1? *Cn）。 Microsoft Research 漢語句法分析器中的自動(dòng)分詞 微軟研究院的自然語言研究所在從 90 年代初開始開發(fā)了一個(gè)通用型的多國語言處理平臺 NLPWin。實(shí)驗(yàn)結(jié)果表明，系統(tǒng)可以正確處理 85%的歧義切分字段，在 Pentium 200 PC上的速度約 600900 字 /秒。系統(tǒng)的分詞連同標(biāo)注的速度在 Pentium 133Hz/16MB 內(nèi)存機(jī)器上的達(dá)到了每秒 3 千詞以上，而在 Pentium II/64MB 內(nèi)存機(jī)器上速度高達(dá)每秒 5千詞。 1998 年 3 月，國家科武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 7頁 委又組織了第二次評測，結(jié)果與第一次差不多。 應(yīng)該來說，相對于中文分詞存在的客觀困難，這些工作已經(jīng)奠定了中文分詞的良好基礎(chǔ)。這就給廣大從事漢語分詞研究的工作者提出了新的努力方向和目標(biāo)。力圖通過良好的數(shù)據(jù)存儲與組織方式來實(shí)現(xiàn)一個(gè)比較快速，詞典又比較全面的分詞系統(tǒng)。 論文主要研究了中文搜索引擎中漢語自動(dòng)分詞系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，從目前中文搜索引擎的發(fā)展現(xiàn)狀出發(fā)，引出中文搜索引擎的關(guān)鍵技術(shù) 漢語自動(dòng)分詞系統(tǒng)的設(shè)計(jì)。第二章針對課題的具體應(yīng)用領(lǐng)域，明確要解決的問題和系統(tǒng)需要實(shí)現(xiàn)的功能，對系統(tǒng)進(jìn)行了總體設(shè)計(jì)，并分析了實(shí)現(xiàn)過程中的關(guān)鍵技術(shù)和難點(diǎn)。第四章對系統(tǒng)從分詞速度和分詞準(zhǔn)確性方面進(jìn)行了性能評價(jià)，并對下一步的工作和努力方向進(jìn)行了展望。 武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 9頁 第二章 總體設(shè)計(jì) 功能分析 根據(jù)課題任務(wù)，本系統(tǒng)需要實(shí)現(xiàn)的功能主要有： (1)組織詞典并有效存儲；(2)設(shè)計(jì)核心分詞算法并實(shí)現(xiàn)中文自然語言的分詞； (3)設(shè)計(jì)系統(tǒng)界面以及用戶接口，為用戶提供相關(guān)信息反饋。 圖 21 系統(tǒng)功能 為實(shí)現(xiàn)本設(shè)計(jì)中基于字典的中文分詞系統(tǒng)，本文的實(shí)現(xiàn)思路和大致過 程將如下規(guī)劃： 首先應(yīng)該建立 比較完善的 詞典，詞典的組織方式主要有整詞二分， TRIE 樹二分，逐字二分三種 [7]。同時(shí)，詞典不能過大也不能太小，過大則使復(fù)雜度增加，過小則影響分詞的準(zhǔn)確率。本文所使用的字典詞條數(shù)目在 200,000 到 300,000 條之間，經(jīng)過計(jì)算 20,000 到 30,000 條的詞匯放入內(nèi)存中所占用的空間約為 到 之間，這在現(xiàn)在的計(jì)算機(jī)系統(tǒng)上是很容易被接受的。對字典來說條目有明顯的順序，而且可以根據(jù)首字母來索引相應(yīng)的條目， 在本設(shè)計(jì)中擬選用 STL 中 set 關(guān)聯(lián)容器來實(shí)現(xiàn)對詞典的存儲，由于 set 高效的實(shí)現(xiàn)結(jié)構(gòu)，其查找具有非常 好的性能。 最后要確定的是一個(gè)好的 匹配 算法，這個(gè)算法應(yīng)當(dāng)把時(shí)間復(fù)雜度控制在根據(jù)要分割文本的大小線性變化的范圍內(nèi)。 功能框架 根據(jù) 前 面 的 功能分析，整個(gè)系統(tǒng) 的實(shí)現(xiàn) 也可 以 分為詞典加載模塊 、 文本匹配與分割模塊 以及 后期處理與輸出模塊這三個(gè) 模塊 。 文本匹配模塊 則讀入 用戶指定的 文本，并 設(shè)計(jì) 匹配算法對文本進(jìn)行分詞 ，在分詞過程中針對歧義進(jìn)行一些必要的修正 。 在上述三個(gè)模塊實(shí)現(xiàn)過程中，針對主要要實(shí)現(xiàn)的功能，擬 選用的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)有 vector， set，擬 定義的關(guān)鍵 數(shù)據(jù) Mprev_pos，擬定義的主要 函數(shù)有：LoadFile， WCompare， SCompare， processing， output。filename) 核心匹配 的部分 算法 + int WCompare(stringamp。st) + void Processing () 后處理 的部分 函數(shù) +CString outputing()。filename) int WCompare(stringamp。st) 對 5 個(gè)漢字單位的小串進(jìn)行分詞 void Processing () 對句子進(jìn)行分詞處理 CString outputing() bool LoadDict(stringamp。file_name) 為 函數(shù)加載詞典， void Processing()， int SCompare(stringamp。st)。 CString outputing()。分詞的結(jié)果儲存在 vectorstring DSDone 中。 武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 13 頁 對于匹配算法，在程序代碼中占比較大的比重，應(yīng)該考慮到運(yùn)行時(shí)間的問題，盡量的減少匹配次數(shù)，以 降低程序的整體運(yùn)行時(shí)間復(fù)雜度，當(dāng)然，影響速度的因素還有詞典的組織和數(shù)據(jù)結(jié)構(gòu)等。 為實(shí)現(xiàn)用戶交互，輸入要匹配的文件，輸出匹配之后的結(jié)果，本設(shè)計(jì)選用了 VC++ 作為系統(tǒng)主界面設(shè)計(jì)工具。 為開發(fā)和實(shí)現(xiàn)系統(tǒng)的核心算法，本設(shè)計(jì)選用了 C++語言來設(shè)計(jì)關(guān)鍵的一些算法 、類等 功能， 同時(shí) 為 便于 今后系統(tǒng)功能擴(kuò)展， 生成 相應(yīng)的動(dòng)態(tài)鏈接庫（ DLL） ，因此選用 了這種流行的面向?qū)ο蟪绦蛟O(shè)計(jì)語言。 C++ STL 中標(biāo)準(zhǔn)關(guān)聯(lián)容器 set, multiset, map, multimap 內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹：紅黑樹，也 稱 為 RB 樹 (RedBlack Tree)。 紅黑樹能夠以 O(log2n)的時(shí)間復(fù)雜度進(jìn)行搜索、插入、刪除操作。 雖然 還有一些更好的 、但實(shí)現(xiàn)起來更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)能夠做到一步旋轉(zhuǎn)之內(nèi)達(dá)到平衡，但紅黑樹能夠給我們一個(gè)比較 “ 便宜 ” 的解決方案。 關(guān)鍵技術(shù)與難點(diǎn)分析 本系統(tǒng)設(shè) 計(jì)中 要解決的關(guān)鍵技術(shù)和難點(diǎn) 主要有三個(gè)：分詞的效率和準(zhǔn)確度；詞典的組織；切分歧義。不能運(yùn)行太長的時(shí)間而使用戶產(chǎn)生等待的感覺，也不能錯(cuò)誤太多導(dǎo)致分詞的結(jié)果無法理解。 從算法方面考慮，對于機(jī)械分詞方法，可以建立一個(gè)一般的模型，形式地表示為 ASM(d, a, m)，即 Automatic Segmentation Model[8]。 例如， ASM(+, , +)就是正向減字最大匹配法（即 MM方法）， ASM(,,+)就是逆向減字最大匹配法 (即 RMM 方法 )等等。用這種模型可以對各種方法的復(fù)雜度進(jìn)行比較，假設(shè)在詞典的匹配過程都使用順序查找和相同的計(jì)首字索引查找方法，則在不記首字索武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 15 頁 引查找次數(shù)（最小為 log漢字總數(shù) 187。 對于給定的文檔 D，其長度為 N，給定詞典 Z，詞典的詞條數(shù)目為 T，在詞典中查找某一字串的復(fù)雜度為 f（ T），則使用最大匹配算法分詞需要進(jìn)行 O（ N）次的詞典查找，故其時(shí)間復(fù)雜度為 O（ N*f（ T））。設(shè)計(jì)好的算法也應(yīng)該同時(shí)考慮單次查找的復(fù)雜度與遍歷次數(shù)。由于查詢詞 t 已確定，所以稱“確定詞條查詢”。由于最長詞的長度往往無法預(yù)知，通常的做法是常識始于位置 i 的所有可能長度的詞。 目前組織分詞詞典主要有整詞、 TRIE、逐字二分等方法。 武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 16 頁 切分歧義 最后考慮到歧義的問題，中文分詞 的最大難題在于漢語中眾多的歧義性詞組的存在。如一個(gè)句子：“王校長基本沒有同學(xué)生會(huì)面的時(shí)間。但是仍然存在許多象第一個(gè)例子一樣需要參考上下文語境才能正確分詞的語句。解決這類問題通常需要從其他的方面入手。 它 們都在一個(gè)類中共同實(shí)現(xiàn)。 設(shè)計(jì) 概述 1．詞典的編撰 作為一個(gè)基于 字典的中文分詞系統(tǒng)，首先應(yīng)該具備的就是一個(gè)完整的，有一定組織規(guī)則的字典，本系統(tǒng)根據(jù)漢語詞典，專有名詞詞典，人名地名詞典制作了詞典，并利用大量的資料添加了常用的連續(xù)詞。 3．詞典的存儲 詞典在使用是加載到內(nèi)存，這樣做的考慮是為了明顯的提高運(yùn)行速度，而且詞典占用的內(nèi)存大小是可以允許的。 5．未登錄詞的 處理 武漢工程大學(xué)設(shè)計(jì)（論文）說明書 第 18 頁 系統(tǒng)對未登錄詞的處理采用把未登錄的連續(xù)詞分成子詞，把未登錄的非連續(xù)詞分成單字。 主要界面 系統(tǒng) 操作 的主 界面如下圖 所示。在文件路徑編輯框中顯示要分詞的文件，后面的按鈕應(yīng)用 MFC 標(biāo)準(zhǔn)文件操作框選