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

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

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

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

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

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

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

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

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

9、語(yǔ)意對(duì)象或者詞；求得構(gòu)詞集Vr=vr1,vr2,vrn； 對(duì)與的構(gòu)詞集Vd與Vr按照本論文算法進(jìn)行疊加運(yùn)算，連同語(yǔ)句中所有的單字集Vs取得無(wú)負(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，邊的長(zhǎng)度值為L(zhǎng)k，邊對(duì)應(yīng)的詞默認(rèn)為vk(k=1,2,n)； 若w=vivi+1vj是一個(gè)在V中的詞，則在節(jié)點(diǎn)Ni-1，Nj之間建立有向邊Ni-1,Nj，邊的長(zhǎng)度為L(zhǎng)w，邊對(duì)應(yīng)的詞為w(0ijn)。 在本論文中，邊的長(zhǎng)度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)間路徑長(zhǎng)度，其值等于p中所有邊的長(zhǎng)度之和。LS是G中所有n0到nn路徑的長(zhǎng)度集合，LS=len|len=L(p),pP(1,n)。NLS為n0到nn的N-最短路徑長(zhǎng)度集合，|NLS|=min(|LS|)； ，bNLSab。NSP為n0到nn的N-最短路徑集合，NSP=p| pP(1,n),L(p)NLS。而RS是最終的N-最短路徑結(jié)果集，RS=w1w2wm|wi是p的第i個(gè)頂點(diǎn)對(duì)應(yīng)的詞，i=1,2,m，其中pNSP。RS是NSP對(duì)應(yīng)的分詞結(jié)果，即為所求的結(jié)果集。這樣，N-最短路徑方法轉(zhuǎn)化為：如何求解無(wú)

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

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