【正文】 算法的 分詞程序設(shè)計(jì) ................................................................. 24 六、結(jié)論 .......................................................................................................................... 35 參 考 文 獻(xiàn) .................................................................................................................... 36 致 謝 .............................................................................................................................. 37 1 漢 語(yǔ)分詞技術(shù)初探 一、 引言 在自然語(yǔ)言處理中，詞是最小的能夠獨(dú)立活動(dòng)的有意義的語(yǔ)言成分。 特此聲明 畢業(yè)論文（設(shè)計(jì)）作者簽名： 年 月 日 I 漢語(yǔ)分詞技術(shù)初探 摘 要 所謂漢語(yǔ)分詞，就是將中文語(yǔ)句中的詞匯切分出來(lái)的過程。這就要求信息處理技術(shù)必須跟上信息發(fā)展的速度，在速度與性能方面具備更高的指標(biāo)。 第二章 中文分詞簡(jiǎn)介。而中文中，是以字為基本書寫單位，只有段與段、句語(yǔ)句之間有分隔符，而詞匯之間沒有分隔符。如 Google、 Baidu、 Yahoo 等檢索工具。） 變聲 —— 如：好酒（ hǎojiuh225。當(dāng)然，就當(dāng)今的現(xiàn)狀來(lái)說，完全的通用性很難達(dá)到。 ④非詞語(yǔ)素問題：現(xiàn)代的書面漢語(yǔ)并非純粹的“現(xiàn)代漢語(yǔ)”，其中夾雜著不少文言成分，如“為民除害”、“以逸待勞”、“幫困濟(jì)窮”等等。 （ 2）組合型歧義 對(duì)于漢字串 AB, A, B, AB 皆可獨(dú)立成詞。 三、基本中文分詞算法 自從 1983 年，背景航空航天大學(xué)實(shí)現(xiàn)了我國(guó)第一個(gè)實(shí)用性的自動(dòng)分詞系統(tǒng)到現(xiàn)在，國(guó)內(nèi)外的研究者在中文分詞領(lǐng)域進(jìn)行了廣泛的研究，提出了許多有效的算法?？梢园褭C(jī)械分詞作為初步的處理手段，然后再通過進(jìn)一步工作提高結(jié)果的正確率?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。對(duì)于上面這個(gè)例子，我們采取組織兩個(gè)詞典的措施：一個(gè)為專業(yè)詞典，一個(gè)為普通詞典。 那么，在實(shí)際的應(yīng)用中，我們就可以把 三種分詞方法全部利用上，以求達(dá)到最好的效果。鍵樹的深度 h 則 19 取決于關(guān)鍵字中字符或數(shù)位的個(gè)數(shù)。 （一） 正向 最大匹配算法 在第三章中對(duì)現(xiàn)今的中文分詞算法進(jìn)行了介紹，其中介紹了基于字符串匹配的分詞算法，又叫機(jī)械分詞算法，機(jī)械分詞算法里又包含了一 種正向最大匹配算法，正向最大匹配算法里又有兩個(gè)分支： 增字匹配法和減字匹配法。假設(shè)詞典中最長(zhǎng)的詞有 i個(gè)漢字字符，先對(duì)輸入文本長(zhǎng)度進(jìn)行判定，若輸入文本長(zhǎng)度小于或等于 i，則 只在最大詞長(zhǎng)范圍內(nèi)進(jìn)行處理就行了，若輸入文本長(zhǎng)度大于 i， 則用輸入文本的當(dāng)前字符串中的前 i個(gè)字作為匹配字段，與字典進(jìn)行匹配，若字典中存在這樣一個(gè) i個(gè)字的詞， 則匹配字段就被切分出來(lái)。 圖 4 文件分詞對(duì)話框 27 圖 5 文件分詞成功提示對(duì)話框 編輯選項(xiàng)中 包含了一些可以對(duì)文檔進(jìn)行簡(jiǎn)單編輯操作的選項(xiàng)，如圖 6所示。 //修改查找區(qū)間下界 } return 1。 sb=bp。 j=1。 } else //如果查不到 { A： if(i==1){ //若還剩 2個(gè)字節(jié)，則判斷第一個(gè)字節(jié)，若大于 0， 說明不是漢字，輸出一個(gè)字節(jié) buffer[2]=0。 strcat(scrres,buffer)。 if(c==EOF) break。由于個(gè)人能力有限，論文中難免出現(xiàn)一些錯(cuò)誤，忘大家給予指正。MuWFA5ux^Gjqv^$UE9wEwZQcUE% amp。 MuWFA5ux^Gj qv^$UE9wEwZQcUE%amp。849Gx^Gj qv^$UE9wEwZQcUE%amp。 6a*CZ7H$dq8Kqqf HVZFedswSyXTyamp。ksv*3。gTXRm 6X4NGpP$vSTTamp。ksv*3t nGK8!z89Am YWpazadNuKNamp。 gTXRm 6X4NGpP$vSTTamp。 gTXRm 6X4NGpP$vSTTamp。 六、結(jié)論 本文對(duì)漢語(yǔ)分詞技術(shù)進(jìn)行了詳細(xì)的介紹，并對(duì)一些方面進(jìn)行了分析，最后嘗試實(shí)現(xiàn)正向最大匹配算法，最終設(shè)計(jì)出了采用正向最大匹配算法的程序， 在測(cè)試中，對(duì)于此程序的分詞速度和分詞結(jié)果還是比較滿意的，但是此程序 也存在著很大的 缺陷，例如對(duì)于歧義字段和未登錄詞無(wú)法有效的識(shí)別和切分，分詞的效率和準(zhǔn)確性受到詞庫(kù)容量的約束等。 //所以要減去回車的次數(shù) while(1) { c=fgetc(fp1)。 break。 bp=bp+k。i=0。rp=0。 //查找成功 else if(strcmp(tt[mid],aidkey)0) high=mid1。 26 圖 3 程序主面板 點(diǎn)擊“分詞”菜單中的“文件分詞”選項(xiàng)后會(huì)彈出如圖 4所示的對(duì)話框，點(diǎn)擊“輸入文件”后的“瀏覽”按鈕，可以選擇待分析的文件，點(diǎn)擊“輸出文件”后的“瀏覽”按鈕可以選擇分詞結(jié)果文件的保存位置。那么實(shí)例的整個(gè)匹配過程如下表 2 所示： 表 2 實(shí)例的匹配步驟 步驟 操作的句子 操作 分詞結(jié)果 1 我們是中華人民共和國(guó)的公民 只取 7個(gè)字 2 我們是中華人民 詞典匹配失敗 3 我們是中華人 詞典匹配失敗 ?? ?? ?? 我們 詞典匹配成功 我們 是中華人民共和 減詞并取前 7個(gè)字 是中華人民共和 詞典匹配失敗 我們 ?? ?? ?? 是 詞典匹配成功 我們 \是 中華人民共和國(guó) 減詞并取前 7個(gè)字 中華人民共和國(guó) 詞典匹配成功 我們 \是 \中華人民共和國(guó) ?? ?? ?? NULL 減詞 我們 \是 \中華人民共和國(guó) \的 \公民 24 （ 二 ） 采用正向最大算法的分詞程序設(shè)計(jì) 從表 2 可以很清晰的看出減字法工作的過程，我們現(xiàn)在開始用 C 語(yǔ)言實(shí)現(xiàn)這個(gè)算法。 ?? 。例如，若關(guān)鍵字是數(shù)值，則結(jié)點(diǎn)中只包含一個(gè)數(shù)位；若關(guān)鍵字是英文單詞，則結(jié)點(diǎn)中只包含 一個(gè)英文字母。同樣，二元分詞就是將“ ABCDE” 切分成“ AB＼ BC＼ CD＼ DE”，在這個(gè)例子中，就是將一個(gè)詞拆成兩兩相連的詞。同理，假設(shè)檢索系統(tǒng)不對(duì)用戶輸入的詞進(jìn)行切分，如果用第二種方法分詞，當(dāng)一個(gè)用戶想要查找包含“搜索引擎”這個(gè)關(guān)鍵字的相關(guān)資源時(shí)，同樣也找不到結(jié)果。因此字與字相鄰共現(xiàn)的頻率或概率能夠較好的反映成詞的可信度 [4]，可以對(duì)語(yǔ)料中相鄰共現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們的互現(xiàn)信息。如果將上述各種方法相互組合，例如，可以將正向最大匹配算法和逆向最大匹配算法相結(jié)合來(lái)構(gòu)成雙向匹配法。在真實(shí)的文檔和語(yǔ)料庫(kù)中，專有名詞和術(shù)語(yǔ)占了很大比例，詞典在多數(shù)情況下很難包括這些詞。 例：他說的 /確實(shí) /在理。依據(jù)這個(gè)標(biāo)準(zhǔn)，“開發(fā)中國(guó)第一個(gè)操作系統(tǒng)軟件者 ” 、“做出了巨大個(gè)人財(cái)產(chǎn)和精神犧牲者”、“克 9 服許多困難而最終獲得成功者”內(nèi)部也不能切開，這樣復(fù)雜的結(jié)構(gòu)在本質(zhì)上就與詞的定義相矛盾。為了做到足夠通用又不過分龐大，必須做到在詞表和處理功能、處理方式上能靈活組合裝卸，有充分可靠和方便的維護(hù)能力，有標(biāo)準(zhǔn)的開發(fā)接口。 由于漢語(yǔ)中的多音字、一些發(fā)音習(xí)慣使得語(yǔ)音識(shí)別和合成過程中需要一個(gè)可靠地中文分詞作為基礎(chǔ)。這方面主要包括拼音輸入法、手寫識(shí)別、簡(jiǎn)繁轉(zhuǎn)換等。 什么是 中文分詞 分詞就是利用計(jì)算機(jī)識(shí)別出文本中詞匯的過程。 相對(duì)于研究?jī)?nèi)容，本文的結(jié)構(gòu)安排為： 第一章 引言。自 20世紀(jì) 80年代初，中文信息處理領(lǐng)域提出自動(dòng)分詞以來(lái)，相關(guān)方面的眾多專家學(xué)者、科研院所、業(yè)機(jī)構(gòu)為之付出了不懈的努力，取得了一些重要的進(jìn)展和一些實(shí)用性的成果，提出了許多中文分詞方法，有些成熟的技術(shù)已經(jīng)應(yīng)用于產(chǎn)品當(dāng)中。因本畢業(yè)論文（設(shè)計(jì)）引起的法律結(jié)果完全由本人承擔(dān)。中文和英文比起來(lái)，有其自身的特點(diǎn)，就是中文以字為基本書寫單位，句子和段落通過分界符來(lái)劃界，但是詞語(yǔ)之間沒有一個(gè)形式上分界符。 (2)對(duì)中文分詞技術(shù)進(jìn)行了簡(jiǎn)介，簡(jiǎn)單介紹了中文分詞、中文分詞的應(yīng)用、中文分詞系統(tǒng)的目標(biāo)、中文分詞的基本問題。此部分總結(jié)論文的所有工作，分析論文中存在的不足和一些未解決的問題。詞是漢語(yǔ)中最小的有 意義的獨(dú)立單位，但是這最小的單位卻是沒有顯式分割的。究其根本原因就是因?yàn)橹形姆衷~技術(shù)的滯后和一些多義詞匯選義的把握。由此可見，分詞系統(tǒng)的準(zhǔn)確率應(yīng)當(dāng)達(dá)到 99． 9％以上，這樣才能基本滿足上層的使用要求，換句話說，即使提高千分之一的準(zhǔn)確度，對(duì)實(shí)際應(yīng)用都是非常有意義的。但是應(yīng)該將哪些詞組收入到核心詞典中去，雖然已經(jīng)提出各種收詞的條件，但是對(duì)每個(gè)詞組按照這些條件的進(jìn)行判斷卻難以 操作，因此目前還沒有合理的可操作的理論和標(biāo)準(zhǔn)。事實(shí)上，許多中文信息處理系統(tǒng)，都是根據(jù) 10 自己服務(wù)目的制定適合自己需要的分詞系統(tǒng)。 未登錄詞 在文本處理過程中，會(huì)遇到很多詞典中未囊括的詞語(yǔ)。整句句子重復(fù)這些流程，直到句子全部分解成詞匯為止。它通常包括三個(gè)部分：分詞子系統(tǒng)、句法語(yǔ)義子系統(tǒng)、總控部分。 混合分詞的原理就是“先用專業(yè)詞典進(jìn)行一遍分詞，再用普通詞典進(jìn)行一遍分詞”，我們用一個(gè)實(shí)例對(duì)為何要進(jìn)行兩次分詞進(jìn)行說明。那么即使兩次切分階段錯(cuò)誤，但最后相同錯(cuò)誤卻使匹配成功，使得仍然可以正確檢索到結(jié)果。根據(jù) Hash函數(shù)的定義可知， Hash 函數(shù)一般都無(wú)法避免沖突，所以通常還要有相應(yīng)的沖突處理方法， 因此對(duì)于詞組中的剩余字串最快的只能通過二分查找來(lái)進(jìn)行查找。 20 首字 hash 表 入口項(xiàng)個(gè)數(shù) 第一項(xiàng)指針 詞索引表 詞典正文指針 詞典正文 圖 1 基于整詞二分的分詞詞典結(jié)構(gòu) 基于 TRIE 索引樹的分詞詞典機(jī)制 TRIE 索引樹是一種以樹的多重鏈表形式表示的鍵樹。比如在“我們是中華人民共和國(guó)的公民”這句話中，我們可以清楚地判斷，如果在字典中進(jìn)行匹配， 只要匹配成功就切分出來(lái)，那么這句話可能被切分成“我們＼是＼中華＼人民＼共和國(guó)＼的＼公民”，該結(jié)果中一共包含 7 個(gè)詞。屏幕分詞只允許打開字節(jié)數(shù)在 32768 以下的文章，結(jié)果直接顯示在屏幕上， 而且可以對(duì)其進(jìn)行輸出保存；文件分詞的結(jié)果并不在屏幕上進(jìn)行顯示，而是直接將結(jié)果保存成一個(gè)文本文檔， 文檔名默認(rèn)為源文件名后加 _pos。} 對(duì)詞典進(jìn)行比較時(shí)查找方法使用折半查找算法，也就是二分查找，此算法的代碼為： int binsearch(int Len,char *aidkey){ int low,high,mid。 //遇到不能識(shí)別字符則標(biāo)記為 1，否則為 0 int bp,sb,rp。 ch[0]=scrbuf[sb]。 rp+=k。 strcat(scrres,buffer)。 char c。 先對(duì)屏幕分詞功能進(jìn)行測(cè)試，使用“文件”菜單下的“打開”選項(xiàng)，打開一個(gè)文本文檔，然后點(diǎn)擊“分詞”菜單中的“屏幕分詞”選項(xiàng)進(jìn)行分詞，結(jié)果如圖 7所示。 qYpEh5pDx2zVkumamp。 qYpEh5pDx2zVkum amp。 QA9wkxFyeQ^! djsXuyUP2kNXpRWXm Aamp。 qYpEh5pDx2zVkum amp。 gTXRm 6X4NGpP$vSTTamp。 gTXRm6X4NGpP$vSTTamp。 qYpEh5pDx2zVkum amp。 qYpEh5pDx2zVkum amp。 qYpEh5pDx2zVkum amp。 在此我還要特別感謝我的家人，是他們的無(wú)私的支持和鼓勵(lì)，使我在四年的學(xué)習(xí)和生活里能夠?qū)Ｐ闹轮荆粸閷W(xué)費(fèi)而煩惱，順利完成學(xué)業(yè)。 } 34 rewind(fp1)。 break。bp=bp+2。|39。i==0) { end=1。 //對(duì)字典進(jìn)行排序 return 1。 //定義兩個(gè)文件指針 long filelen。 (3) 從當(dāng)前指針 Pi 處起取 m 個(gè)漢字作為詞 Wi ，并進(jìn)行判斷： ○ 1 如果 Wi 是詞典中的詞，則在 Wi 后添加一個(gè)切分標(biāo)志，轉(zhuǎn)到 ○ 3 ； ○ 2 如果 Wi 不是詞典中的詞且長(zhǎng)度大于 1，則將 Wi 從右端去掉一個(gè)字轉(zhuǎn) 25 到 ○ 1 ；若 Wi 的長(zhǎng)度等于 1，則在 Wi 后添加一個(gè)切分標(biāo)志，將 Wi 作為單字詞添加到詞典中，然后轉(zhuǎn)到 ○ 3