基于一種粗切分的最短路徑中文分詞研究

1、基于一種粗切分的最短路徑中文分詞研究 摘 要 本論文在分析現(xiàn)有的分詞算法并比較各種算法優(yōu)缺點的基礎上，提出了將正向匹配算法與逆向匹配算法所得到的結果集進行疊加，生成粗分結果集的新觀點，再對生成的粗分結果集構造非負權有向圖，然后應用最短路徑算法求解有向圖。本文提出的疊加算法著重考慮粗分結果的準確性、包容性以及粗分結果的長度。經過實驗驗證，該算法有效提高了漢語切分的準確性以及切分速度，同時部分解決了交集型歧義切分問題。 關鍵字 中文分詞；最短路徑；疊加運算1 引言 中文分詞是中文自然語言理解和處理的重要環(huán)節(jié)，也是一個比較復雜和困難的問題。它是自動翻譯、文本檢索、語音識別、文本校對以及搜索技術中的重

2、要組成部分。分詞就是將連續(xù)的字符串或序列按照一定的規(guī)范重新組合成詞序列的過程1。本論文定義的分詞(text segmentation或者word segmentation)就是對計算機不能直接理解的字符串或者序列按照一定的規(guī)則裁分并最終組合成計算機可以理解的詞序列的過程。西文的行文中，空格是天然的分界符。因此，對于西文的各種處理比較直觀和方便。而中文只有最簡單的句與句之間的劃界（比如標點符號之類），詞與詞之間沒有明顯分界符。例如一個最簡單的例子，英語：I call her sister；譯文：我叫她姐姐。在西文處理中，計算機可以通過空格和標點符號確定“sister”為一個獨立語意單位，獨自構成

3、一個詞。但是在譯文中，由于沒有明顯標點符號分界，在沒有一定規(guī)則的前提下，計算機很難理解“姐”和“姐”共同構成一個語意單位。2 中文分詞技術概述2.1 中文分詞技術中存在的難題 如引言中所述，中文自然語言的理解和處理遠比西文語言復雜得多，主要體現(xiàn)在以下幾個方面1： (1)分詞的規(guī)范問題：詞的確切概念難以標準化，詞的應用領域不同，使得分詞規(guī)范難以統(tǒng)一，需要達到的分詞效果也有很大區(qū)別。 (2)歧義切分：對于特定的句子或字符串可能存在多種切分方法，不同的切分方法具有不同的含義，因此會導致組合型歧義和交集型歧義。 (3)新詞識別：漢字系統(tǒng)是一個開放性系統(tǒng)，可能不斷有新詞產生，最典型的比如：人名、地名以及

4、各類術語，分詞系統(tǒng)必須不斷更新分詞詞典。 (4)分詞理解的先與后：由于計算機需要靠詞的信息來理解文章，因此它只能采用先分詞后理解的方法，而分詞需要以理解為基礎，理解必須先分詞。由此產生的邏輯問題決定了不可能有百分之百正確的分詞方法。2.2 中文分詞技術發(fā)展現(xiàn)狀 目前，已經有很多比較成熟的漢語分詞技術。鄒海山等在現(xiàn)有分詞技術的基礎上提出了一種基于詞典的正向最大匹配和逆向最大匹配相結合的漢語分詞方案，可以高效準確的實現(xiàn)中文文檔的主題詞條抽取和詞頻統(tǒng)計；應志偉等基于一個實際的文語轉換系統(tǒng)，改進最大匹配算法，從實用角度解決多音字的異讀問題和中文姓名自動識別問題；歐振猛、余順爭采用基于自動建立詞庫的最佳

5、匹配方法進行中文分詞；韓客松等主要從知識的自動獲取出發(fā)，介紹了研究中的漢語語言無詞典分詞模型系統(tǒng)。2.3 中文分詞算法綜述 中文詞語分詞采取的主要步驟是：先采取最大匹配、最短路徑、概率統(tǒng)計、全切分等方法，得到一個相對較好的粗分結果，然后進行排歧、未登錄詞識別，最后標注詞性。例如：北大計算語言所分詞系統(tǒng)采用了統(tǒng)計方法進行詞語粗分，北航1983年的CDWS系統(tǒng)則采用了正向或逆向最大匹配方法，而清華大學的SEGTAG系統(tǒng)采用的是全切分方法。在實際的系統(tǒng)中，這三個過程可能相互交叉、反復融合，也可能不存在明顯的先后次序。3 粗切分的最短路徑中文分詞 本論文的疊加算法著重為了減少粗分結果集，同時針對歧義切

6、分中存在的問題，提出基于非負權圖最短路徑分詞算法，本算法高效、快速的解決了交集型歧義以及多切分問題。預處理過程產生的粗切分結果是后續(xù)過程的處理對象，粗分結果的準確性與包容性（即必須涵蓋正確結果）直接影響系統(tǒng)最終的準確率、召回率。預處理得到的粗分結果一旦不能成功召回正確的結果，后續(xù)處理一般很難補救，最終的詞語分析結果必然會導致錯誤，粗分結果的召回率往往是整個詞語分析召回率的上限。同時，粗分結果集的大小也決定了后續(xù)處理的搜索空間與時間效率，最終會影響整個系統(tǒng)的運行效率。 因此，詞語粗分是后續(xù)處理的基礎和前提，其關鍵在于如何以盡量高的效率尋找數(shù)量少、涵蓋最終結果的粗分結果集。3.1 疊加算法描述 由

7、于正向與逆向最大匹配算法結果集之間難免存在包含與被包含關系，如果把這兩種結果直接疊加可能出現(xiàn)切分錯誤，而且會增加歧義切分現(xiàn)象。例如：輸入“ABCDEFGHIJK LMN”，其中每一個字母代表一個字。采用正向匹配算法的切分結果為：AB/CD/EF/GH/I/JKL/MN；采用逆向匹配算法的切分結果為：ABC/DE/F/GH/IJ/KLM/N。如果按照常規(guī)方法疊加，可能在有向圖的頂點中同時存在AB與ABC，這樣構成的有向圖會嚴重影響整個切分效率和準確性。 本文采用的疊加方法避免了上述情況的發(fā)生，如下描述：正向切分按照切分結果順序排列Lz，逆向切分按照切分結果倒序排列Lr。對于Lz與Lr，從某一個切

8、分詞Wi（i=0，1，2，n,其中n=minlength（Lz），length （Lr）開始比較，保留詞W應該是兩者中長度最大的。根據(jù)保留詞從Lz和Lr中取得下一個比較詞的開始字符，重復上述過程直到Lz與Lr中長度最小的結果集比較完畢。這樣就能保證有向圖中的頂點唯一，頂點個數(shù)最少。3.2 構造非負權圖 用給定的字符串構造非負權圖的方法如下所述： 對于給定語句S（從構成來看由許多單字組成，而表達的意義是由多個語義單位構成）； 根據(jù)提供的統(tǒng)一分詞詞典，按照正向最大匹配算法找出字符串中所有可能的語意對象或者詞，求得構詞集Vd=vd1,vd2,vdn； 如同，按照反向最大匹配算法找出字符串中所有可能的

9、語意對象或者詞；求得構詞集Vr=vr1,vr2,vrn； 對與的構詞集Vd與Vr按照本論文算法進行疊加運算，連同語句中所有的單字集Vs取得無負權圖所有構詞集V=v1,v2,vn，邊權值定義為wij=1(i,j=1,2,n)； 在相鄰節(jié)點Nk-1，Nk之間建立有向邊Nk-1,Nk，邊的長度值為Lk，邊對應的詞默認為vk(k=1,2,n)； 若w=vivi+1vj是一個在V中的詞，則在節(jié)點Ni-1，Nj之間建立有向邊Ni-1,Nj，邊的長度為Lw，邊對應的詞為w(0ijn)。 在本論文中，邊的長度Lk(k=1,2,n)統(tǒng)一賦值為1。由上述方法構造的非負 權圖如圖1所示。3.3 求解非負權圖的算法描

10、述1 假設P(i,j)是頂點集N中ni到nj的路徑集合(i,j=0,2,n)，L(p)是某兩點間路徑長度，其值等于p中所有邊的長度之和。LS是G中所有n0到nn路徑的長度集合，LS=len|len=L(p),pP(1,n)。NLS為n0到nn的N-最短路徑長度集合，|NLS|=min(|LS|)； ，bNLSab。NSP為n0到nn的N-最短路徑集合，NSP=p| pP(1,n),L(p)NLS。而RS是最終的N-最短路徑結果集，RS=w1w2wm|wi是p的第i個頂點對應的詞，i=1,2,m，其中pNSP。RS是NSP對應的分詞結果，即為所求的結果集。這樣，N-最短路徑方法轉化為：如何求解無

11、負權有向圖G的集合NSP。在每一個節(jié)點處記錄下最短路徑值，并記錄相應路徑上當前節(jié)點的前驅。如果同一長度對應多條路徑，必須同時記錄這些路徑上當前節(jié)點的前驅，最后通過回溯即可求出NSP。 以上求解算法借鑒了文獻1最短路徑匹配算法的求解模式。而本文所提出的算法與文獻1有明顯不同，在最短路徑匹配算法中根據(jù)分詞詞典找出所有可能的詞，直接構造有向無環(huán)圖G，每一個詞對應圖中的一條有向邊。本論文是根據(jù)疊加算法求解的構詞集以及語句中所有單字作為圖中邊對應的詞。4 實驗驗證 整個算法實驗過程中，正向與逆向所用數(shù)據(jù)字典是segmenter程序提供的一個基本詞典，共有詞量195580條。經過對含有漢字串：“我是中國人

12、民的兒子”與“我是一個深深愛著祖國和人民的好兒子”進行實驗，以及一個大小為6kb的文本文件進行實驗，結果 對于漢字串1：正向正大匹配算法結果集我，是，中國人民，的，兒子；逆向最大匹配算法結果集我，是中國，人民的，兒子。 疊加算法求得結果集我，是中國，人民的，兒子。 最終構造的有向圖，如圖2。 求得最終結果：我/是中國/人民的/兒子。 程序運行結果如圖3。 采用同樣方法對漢字串2和文本文件(6kb)進行實驗，驗證結果如表1所示。圖3 漢字串1實驗結果表1 實驗結果對比表測試對象本算法實驗時間(ms)文獻1最短路徑算法實驗時間(ms)漢字串11517漢字串22326文本文件(6kb)1481565 結論 本論文提出的對正向與逆向匹配算法所得到的結果集進行疊加的算法，高效、快速的解決了交集型歧義以及多切分問題。在一定程度上減小了算法的時間復雜度，但是空間復雜度沒有太大變化，在今后的學習中我會向這方面努力。參考文獻1 朱巧明，李培峰中文信息處理技術教程北京：清華大學出版社，2005：183-184嚴蔚敏，吳偉民數(shù)據(jù)結構M北京：清華大學出版社，1997：187-188現(xiàn)代數(shù)學手冊