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