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

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

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

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

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

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

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

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

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

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

10、述1 假設(shè)P(i,j)是頂點(diǎn)集N中ni到nj的路徑集合(i,j=0,2,n)，L(p)是某兩點(diǎn)間路徑長度，其值等于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-最短路徑結(jié)果集，RS=w1w2wm|wi是p的第i個頂點(diǎn)對應(yīng)的詞，i=1,2,m，其中pNSP。RS是NSP對應(yīng)的分詞結(jié)果，即為所求的結(jié)果集。這樣，N-最短路徑方法轉(zhuǎn)化為：如何求解無

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

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