【文章內(nèi)容簡介】 k 中的 _C1C2_，會被認(rèn)為是正確的。我們接受這個詞，并向前重復(fù)這個過程從漢字 C3，直到字符串的最后一個詞被識別。除了最 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 6 大匹配算法，許多其它消除歧義的算法也已經(jīng)被得出。在消除歧義的過程中使用了各種各樣的信息，例如，概率和統(tǒng)計，語法，還有詞語形態(tài)學(xué)，它們當(dāng)中的大部份需要一個構(gòu)建良好，擁有漢字和詞組頻率信息的字典，單詞的語法分類，以及一個語法或形態(tài)學(xué)的集合（例如，漢語知識信息處理小組 ）。 雖然有各種各樣的消除歧義的算法，但是到目前為止并沒有一種十分完美的消除歧義的算法。 未登錄詞及其處理 方法 未登錄詞大致包含兩大類： 1）新涌現(xiàn)的通用詞或?qū)I(yè)術(shù)語等； 2）專有名詞，如中國人名、外國譯名、地名、機構(gòu)名（泛指機關(guān)、團體和其它企事業(yè)單位）等。前一種未登錄詞理論上是可預(yù)期的，能夠人工預(yù)先添加到詞表中（但這也只是理想狀態(tài)，在真實環(huán)境下并不易做到）；后一種未登錄詞則完全不可預(yù)期，無論詞表多么龐大，也無法囊括 [4]。 未登錄詞的處理是中文分詞的一大難題，對于歧義識別問題中出現(xiàn)的第一種， 我們只有擁有龐大的上下文資料才能處理，而對于第二種歧義問題，目前已經(jīng)出現(xiàn)了許多消除歧義的算法，第三種歧義問題實際上就是未登錄詞導(dǎo)致的歧義，對于現(xiàn)有的詞典來說，所有不在詞典里的詞語可以說都是未登錄詞。對于未登錄詞，將未登錄詞進行分類，讓用戶自己選擇自己需要的專業(yè)詞匯，這是一種很人性化的解決辦法。 主要的分詞算法 從開始研究中文分詞算法到現(xiàn)在，雖然沒有出現(xiàn)非常完美的分詞算法，但是也還是出現(xiàn)了許多比較好的分詞算法，目前的分詞算法主要包含基于字典的分詞算法，基于統(tǒng)計的分詞算法和基于理解的分詞算法，下面簡要介 紹一下這些算法。 基于字典的分詞算法 基于字典的分詞算法又叫機械分詞算法， 這種方法按照一定策略將待分析的漢字串與一個 “ 充分大的 ” 機器詞典中的詞條進行匹配，若在詞典中找到某個字符串，則匹配成功 (識別出一個詞 )。根據(jù)掃描方向的不同分為正向匹配和逆向匹配 。根據(jù)不同長度優(yōu)先匹配的情況，分為最大 (最長 )匹配和最小 (最短 )匹配 。根據(jù)與詞性標(biāo)注過程是否相結(jié)合，又可以分為單純分詞方法和分詞與標(biāo)注相結(jié)合的一體化方法。常用的方法如下 [3]: 正向最大匹配法 (Maximum Matching Method)通常簡稱為 MM法。其基本思想為 :設(shè) D為 詞典， MAX表示 D中的最大詞長， string 為待切分的字串。 MM法是每次從 string中取長度為MAX的子串與 D中的詞進行匹配。若成功，則該子串為詞，指針后移 MAX個漢字后繼續(xù)匹配，否則子串逐次減一進行匹配。 逆向最大匹配法 (Reverse Maximum Matching Method)通常簡稱為 RMM法。 RMM法的 基本原理與 MM法相同，不同的是分詞的掃描方向，它是從右至左取子串進行匹配。統(tǒng)計結(jié)果表明，單純使用正向最大匹配的錯誤率為 1/169，單純使用逆向最大匹配的錯誤率為 1/245，顯然 RMM法在切分的準(zhǔn)確率上比 MM法有很大提高?；谠~典的分詞算法，對于在詞典中的詞分詞的精確度很高，但是不能很好的解決歧義問題，經(jīng)常和其它分詞算法結(jié)合在一起應(yīng)用。 基于統(tǒng)計的分詞算法 [6] 該方法的主要思想：詞是穩(wěn)定的組合，因此在上下文中，相鄰的字同時出現(xiàn)的次數(shù)越多，就越有可能構(gòu)成一個詞。因此字與字相鄰出現(xiàn)的概率或頻率能較好反映成詞的可信度?？梢詫τ?xùn)練文本中相鄰出現(xiàn)的各個字的組合的頻度進行統(tǒng)計，計算它們之間的互現(xiàn)信息?；ガF(xiàn)信 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 7 息體現(xiàn)了漢字之間結(jié)合關(guān) 系的緊密程度。當(dāng)緊密程度高于某一個閾值時，便可以認(rèn)為此字組可能構(gòu)成了一個詞。該方法又稱為無字典分詞。 該方法所應(yīng)用的主要的統(tǒng)計模型有： N元文法模型、隱 Markov 模型和最大熵模型等。在實際應(yīng)用中一般是將其與基于詞典的分詞方法結(jié)合起來，既發(fā)揮匹配分詞切分速度快、效率高的特點，又利用了無詞典分詞結(jié)合上下文識別生詞、自動消除歧義的優(yōu)點。 基于理解的分詞算法 該方法又稱基于人工智能的分詞方法，其基本思想就是在分詞的同時進行句法、語義分析，利用句法信息和語義信息來處理歧義現(xiàn)象。它通常包括三個部分 ：分詞子系統(tǒng)、句法語義子系統(tǒng)和總控部分。在總控部分的協(xié)調(diào)下，分詞子系統(tǒng)可以獲得有關(guān)詞、句子等的句法和語義信息來對分詞歧義進行判斷，即它模擬了人對句子的理解過程。這種分詞方法需要使用大量的語言知識和信息。目前基于理解的分詞方法主要有專家系統(tǒng)分詞法和神經(jīng)網(wǎng)絡(luò)分詞法等。由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段。 小結(jié) 無論是哪一種分詞算法都不是完美的，都有各自的優(yōu)缺點：基于詞典的分詞算法的優(yōu)點是簡單，易于實現(xiàn)，缺點是匹配速度 慢，不能很好的解決歧義問題，并且也不能很好的解決未登錄詞的問題；基于統(tǒng)計的分詞算法的優(yōu)點是可以發(fā)現(xiàn)所有的歧義切分，缺點是統(tǒng)計語言的精度和決策算法在很大程度上決定了解決歧義的方法，并且速度較慢，需要一個長期的學(xué)習(xí)過程才能達到一定的程度；由于漢語語言知識的籠統(tǒng)、復(fù)雜性，難以將各種語言信息組織成機器可直接讀取的形式，因此目前基于理解的分詞系統(tǒng)還處在試驗階段。 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 8 3 雙向匹配算法和子字典機制 通過第二章對中文分詞的簡介，我們知道在現(xiàn)有中文分詞算法中，沒有一個是百分之百完美 的算法，本文主要是將基于字典的最大正向匹配算法和最大逆向匹配算法進行了結(jié)合，組成了雙向匹配算法，本章主要是對雙向匹配的算法思想和算法步驟流程進行了講解，此外，本章還對基于詞典的幾種詞典機制進行了講解，比較了其優(yōu)缺點，在此的基礎(chǔ)上提出了本文采用的詞典機制并且進行了詳細(xì)的講解。 雙向匹配算法 雙向匹配算法簡要說來就是對待切分的文字分別進行最大正向匹配和最大逆向匹配，然后在此基礎(chǔ)上對切分結(jié)果進行比較，然后根據(jù)不同的結(jié)果采用不同的分詞策略。首先，本小節(jié)先介紹最大正向匹配和最大逆向匹配，在兩者的基礎(chǔ)上介紹雙向匹 配算法。 最大正向匹配算法（ MM） 最大正向匹配算法的算法思想是：設(shè) D為詞典， MAX表示算法采用的最大詞長， string 為待切分的字串。 MM法是每次從 string中取長度為 MAX的子串與 D中的詞進行匹配。若成功，則該子串為詞，指針后移 MAX個漢字后繼續(xù)匹配，否則子串逐次減一進行匹配。我們在具體實現(xiàn)時提出了一種改進算法，經(jīng)典的算法在實現(xiàn)的時候，最大長度詞 MAX是人工定的，這種方法由于不科學(xué)且因為個人的原因造成分詞系統(tǒng)的不準(zhǔn)確，我們在這里將最大長度詞由程序自己獲取，從子字典的最大長度來得到最大匹配的長 度。根據(jù)算法的具體的思想，我們能夠很清楚的得到 MM算法的流程： 1）輸入經(jīng)過預(yù)處理后的待切分的句子 ,并初始化 Index = 0； 2）獲得字典數(shù)據(jù)庫內(nèi)各個子字典的長度； 3）獲得分詞單詞的長度，并和字典數(shù)據(jù)庫內(nèi)最長的子字典比較，如果子字典的最大長度大于要分詞的長度，則取剩于要分詞的字符串為最大長度，否則則以最大長度切分； 4）用二分法查找與當(dāng)前最大匹配長度相同的子字典，如果找到該字典則轉(zhuǎn) 5，否則最大長度減一轉(zhuǎn) 4； 5）取得要分詞的字符串 SubStr，在字典里找該字符串，如果找到則將該字符串添加到 List內(nèi)， 如果沒有找到則判斷 SubStr是否大于 1，如果大于 1，則刪除 SubStr最后一個字轉(zhuǎn) 5，否則置切分標(biāo)志，轉(zhuǎn) 6； 6)判斷 Index是否小于 STR，如果小于則轉(zhuǎn) 3否則保存 List,退出。 具體的算法流程如圖 31。 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 9 否 是 否 否 獲得預(yù)處理的待分句子 ( STR)初始化 Index=0 開始 獲得子字典最大長度并將其設(shè)為最大 長度 MaxLength 取 STR 為字符串 SubStr 將 SubStr 在字典庫中按最大長度搜索 比較 STR 長度是否大于 MaxLength Index 位取 MaxLength 長字符串（ SubStr） 是否搜索成功 切分位置加 SubStr 是否 SubStr 大于 1 切分標(biāo)志加 1(Index+1) 刪除 SubStr 最后一個字 將 str 在標(biāo)志位 Index 切分，保存分詞結(jié)果到 list 判斷 Index 是否小于 STR 的長度 返回結(jié)果集 List 結(jié)束 是 是 圖 31最大正向匹配算法 是 否 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 10 最大逆向匹配算法（ RMM） 最大逆向匹配算法的算法思想是：最大逆向匹配的算法跟最大正向匹配類似，不同的是掃描的方向，它是從右往左取子串進行匹配。根據(jù)算法的具體的思想，我們能夠很清楚的得到 MM算 法的流程： 1)輸入經(jīng)過預(yù)處理后的待切分的句子 STR,并初始化 Index = ； 2)獲得字典數(shù)據(jù)庫內(nèi)各個子字典的長度； 3)獲得分詞單詞的長度，并和字典數(shù)據(jù)庫內(nèi)最長的子字典比較，如果子字典的最大長度大于要分詞的長度，則取剩于要分詞的字符串為最大長度，否則則以最大長度切分； 4)用二分法查找與當(dāng)前最大匹配長度相同的子字典，如果找到該字典則轉(zhuǎn) 5，否則最大長度減一轉(zhuǎn) 4； 5)取得要分詞的字符串 SubStr，在字典里找該字符串，如果找到則將該字符串添加到 List內(nèi)，如果沒有找到 則判斷 SubStr是否大于 1，如果大于 1，則刪除 SubStr最后一個字轉(zhuǎn) 5，否則置切分標(biāo)志，轉(zhuǎn) 6； 6)判斷 Index 是否大于 1，如果小于則轉(zhuǎn) 3 否則保存 List,退出。 具體的算法流程如圖 32。 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 11 圖 32最大逆向匹配算法 是 否 是 否 否 處理的待分句子 ( STR) 初始化 Index= 開始 獲得子字典最大長度并將其設(shè)為最大長度 MaxLength 取 STR 為字符串 SubStr 將 SubStr 在字典庫中按最大長度搜索 比較 STR 長度是否大于 MaxLength Index 位取 MaxLength 長字符串（ SubStr） 是否搜索成功 切分位置加 SubStr 是否 SubStr 大于 1 切分標(biāo)志加 1(Index1) 刪除 SubStr 最前一個字 將 str 在標(biāo)志位 Index 切分，保存分詞結(jié)果到 list 判斷 Index 是否大于 1 返回結(jié)果集 List 結(jié)束 是 是 否 石家莊經(jīng)濟學(xué)院本科生畢業(yè)論文 12 雙向匹配算法（ DMM） 雙向匹配算法的算法思想是：將正向匹配與逆向匹配算法相結(jié)合起來，對于待分字符串，首先分別用最大正向匹配和最大逆向匹配算法進行分詞，對于分詞 結(jié)果進行比較， 比較正向和反向兩個最大匹配，返回分詞結(jié)果，當(dāng)兩個方向的分詞結(jié)果一致，返回字符串，當(dāng)不一致，返回長度小的，當(dāng)長度一致，返回反向的。 這是因為統(tǒng)計表明，統(tǒng)計結(jié)果表明，單純使用正向最大匹配的錯誤率為 1/169，單純使用逆向最大匹配的錯誤率為 1/245，顯然 RMM法在切分的準(zhǔn)確率上比 MM法有很大提高。 [2]同時本算法可以分別打出正向分詞和逆向分詞的結(jié)果供用戶實驗，還能夠發(fā)現(xiàn)出現(xiàn)歧