基于詞典的有向圖生成的最短路徑算法

1自適應(yīng)的分詞漢語(yǔ)段是漢語(yǔ)自然景觀理解和處理的重要組成部分，也是一個(gè)相對(duì)復(fù)雜、困難的問(wèn)題。它是自動(dòng)翻譯、文本檢索、語(yǔ)音識(shí)別、文本校對(duì)以及搜索技術(shù)中的重要組成部分。分詞就是將連續(xù)的字符串或序列按照一定的規(guī)范重新組合成詞序列的過(guò)程。本文定義的分詞(TextSegmentation或者WordSegmentation)就是對(duì)計(jì)算機(jī)不能直接理解的字符串或者序列按照一定的規(guī)則裁分并最終組合成計(jì)算機(jī)可以理解的詞序列的過(guò)程。西文的行文中,空格是天然的分界符。因此,對(duì)于西文的各種處理比較直觀和方便。而中文只有最簡(jiǎn)單的句與句之間的劃界(比如標(biāo)點(diǎn)符號(hào)之類),詞與詞之間沒(méi)有明顯分界符。例如一個(gè)最簡(jiǎn)單的例子,英語(yǔ):Icallhersister;譯文:我叫她姐姐。在西文處理中,計(jì)算機(jī)可以通過(guò)空格和標(biāo)點(diǎn)符號(hào)確定“sister”為一個(gè)獨(dú)立語(yǔ)意單位,獨(dú)自構(gòu)成一個(gè)詞。但是,在譯文中由于沒(méi)有明顯標(biāo)點(diǎn)符號(hào)分界,在沒(méi)有一定規(guī)則的前提下,計(jì)算機(jī)很難理解“姐”和“姐”共同構(gòu)成一個(gè)語(yǔ)意單位。2中文分詞技術(shù)的總結(jié)2.1漢字部曲線分詞的應(yīng)用如引言中所述,中文自然語(yǔ)言的理解和處理遠(yuǎn)比西文復(fù)雜,主要體現(xiàn)在以下幾個(gè)方面:(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)生,最典型的如人名、地名以及各類術(shù)語(yǔ),分詞系統(tǒng)必須不斷更新分詞詞典。(4)分詞理解的先與后:由于計(jì)算機(jī)需要靠詞的信息來(lái)理解文章,因此它只能采用先分詞后理解的方法,而分詞需要以理解為基礎(chǔ),理解必須先分詞。由此產(chǎn)生的邏輯問(wèn)題決定了不可能有百分之百正確的分詞方法。2.2基于匹配相結(jié)合的分詞方案目前,已經(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ù)的最佳匹配方法進(jìn)行中文分詞;韓客松等主要從知識(shí)的自動(dòng)獲取出發(fā),介紹了研究中的漢語(yǔ)語(yǔ)言無(wú)詞典分詞模型系統(tǒng)。2.3計(jì)算機(jī)關(guān)的識(shí)別中文詞語(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é)果的準(zhǔn)確性本文的疊加算法著重為了減少粗分結(jié)果集,同時(shí)針對(duì)歧義切分中存在的問(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融合模型的切分結(jié)果由于正向與逆向最大匹配算法結(jié)果集之間難免存在包含與被包含關(guān)系,如果把這兩種結(jié)果直接疊加可能出現(xiàn)切分錯(cuò)誤,而且會(huì)增加歧義切分現(xiàn)象。例如,輸入“ABCDEFGHIJKLMN”,其中每一個(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è)切分詞Wi(i=0,1,2,…,n,其中n=min{length(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)建用給定的字符串構(gòu)造非負(fù)權(quán)圖的方法如下所述:(1)對(duì)于給定語(yǔ)句S(從構(gòu)成來(lái)看由許多單字組成,而表達(dá)的意義由多個(gè)語(yǔ)義單位構(gòu)成)。(2)根據(jù)提供的統(tǒng)一分詞詞典,按照正向最大匹配算法找出字符串中所有可能的語(yǔ)意對(duì)象或者詞,求得構(gòu)詞集Vd={vd1,vd2,…,vdn};(3)如同(2),按照反向最大匹配算法找出字符串中所有可能的語(yǔ)意對(duì)象或者詞,求得構(gòu)詞集Vr={vr1,vr2,…,vrn};(4)對(duì)(2)與(3)的構(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);(5)在相鄰節(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);(6)若w=vivi+1…vj是一個(gè)在V中的詞,則在節(jié)點(diǎn)Ni-1、Nj之間建立有向邊<Ni-1,Nj>,邊的長(zhǎng)度為L(zhǎng)w,邊對(duì)應(yīng)的詞為w(0<i<j≤n)。在本文中,邊的長(zhǎng)度Lk(k=1,2,…,n)統(tǒng)一賦值為1。由上述方法構(gòu)造的非負(fù)權(quán)圖如圖1所示。對(duì)漢字串“我是中國(guó)人民的兒子”進(jìn)行有向圖構(gòu)造,其結(jié)果如圖2所示。3.3n-最短路徑方法的轉(zhuǎn)化假設(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),p∈P(1,n)}。NLS為n0到nn的N-最短路徑長(zhǎng)度集合,NLS?LS,|NLS|=min(|LS|);?a∈LS-NLS,b∈NLS←a<b。NSP為n0到nn的N-最短路徑集合,NSP={p|p∈P(1,n),L(p)∈NLS}。而RS是最終的N-最短路徑結(jié)果集,RS={w1w2…wm|wi是p的第i個(gè)頂點(diǎn)對(duì)應(yīng)的詞,i=1,2,…,m,其中p∈NSP}。RS是NSP對(duì)應(yīng)的分詞結(jié)果,即為所求的結(jié)果集。這樣,N-最短路徑方法轉(zhuǎn)化為如何求解無(wú)負(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。4實(shí)驗(yàn)證實(shí)對(duì)上述漢字串用百度和谷歌進(jìn)行實(shí)驗(yàn),驗(yàn)證結(jié)果如表1所示。5個(gè)大型網(wǎng)站的分布情況本文提出的對(duì)正向與逆向匹