基于N－最短路徑的中文分詞技術(shù)研究

吳曉倩，胡學(xué)鋼

(1.合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 合肥 230009;2.安徽醫(yī)學(xué)高等專(zhuān)科學(xué)校公共衛(wèi)生與衛(wèi)生管理系，安徽合肥 230061)

中文分詞是信息處理的基礎(chǔ)，中文信息是由句子組成的，句子又是由詞組成的，詞是最小的能夠獨(dú)立活動(dòng)的有意義的語(yǔ)言成分，但漢語(yǔ)是以字為基本的書(shū)寫(xiě)單位，詞語(yǔ)之間沒(méi)有明顯的區(qū)分標(biāo)記。如何在這些由連續(xù)的文字組成的語(yǔ)句中把一個(gè)具有獨(dú)立意義的詞匯切分出來(lái)就是一個(gè)很有挑戰(zhàn)的問(wèn)題。

1 現(xiàn)有的分詞算法及難點(diǎn)

1.1 現(xiàn)有的分詞算法

現(xiàn)有的分詞算法分為三大類(lèi):基于詞典的分詞方法、基于統(tǒng)計(jì)的分詞方法和基于理解的分詞方法。

1)基于詞典的分詞。這種方法要事先有一個(gè)詞典，詞典盡量囊括所有的詞匯，然后將待切分的句子按照一定的規(guī)則掃描，與詞典中的詞條進(jìn)行匹配，如果匹配成功，則將該詞條切分出來(lái)，否則進(jìn)行其他處理。按照掃描方向和不同長(zhǎng)度優(yōu)先匹配的情況，基于字符串匹配分詞方法又分為正向最大匹配法、逆向最大匹配法、最少切分法和雙向最大匹配法四種。大多數(shù)的系統(tǒng)是以該方法為主來(lái)實(shí)現(xiàn)的。

文獻(xiàn)［1］提出了一種改進(jìn)的正向最大匹配算法，改進(jìn)后的算法采用類(lèi)似TRIE 索引樹(shù)的逐字匹配算法，消除了正向最大匹配算法的切分盲點(diǎn)，同時(shí)，避免二分查找，提高分詞效率;文獻(xiàn)［2］提出了一種基于雙詞典機(jī)制的中文分詞方法;文獻(xiàn)［3］提出了全二分最大匹配快速分詞算法，分詞詞典存放在內(nèi)存，在查找時(shí)，不用進(jìn)行I/O 操作，減少了匹配次數(shù)。

2)基于統(tǒng)計(jì)的分詞。此方法認(rèn)為，中文中的詞組是固定的，所以在文章中，相鄰的字出現(xiàn)的頻率越高，就有可能是一個(gè)詞，用字與字之間相鄰出現(xiàn)的概率反映成詞的可信度，通過(guò)統(tǒng)計(jì)文本中各個(gè)字的組合的頻度，計(jì)算它們之間的互現(xiàn)信息，從而判斷漢字之間的緊密程度，當(dāng)緊密程度達(dá)到一個(gè)閾值，就認(rèn)為可能構(gòu)成一個(gè)漢字。

3)基于理解的分詞。基于理解的分詞結(jié)合文本的句法、語(yǔ)法分析和語(yǔ)義分析，通過(guò)對(duì)上下文內(nèi)容所提供信息的分析對(duì)詞進(jìn)行界定，通常由總控部分、分詞子系統(tǒng)和句法語(yǔ)義子系統(tǒng)三部分組成。但是由于漢語(yǔ)言的復(fù)雜性，難以將各種語(yǔ)言知識(shí)組織成機(jī)器可以直接讀取的形式。因此，這種方法并沒(méi)有普及應(yīng)用，還處于試驗(yàn)階段。

4)難點(diǎn)。目前雖有中科院、微軟等研究機(jī)構(gòu)推出的一些實(shí)驗(yàn)系統(tǒng)(如CSW、WB2000 等);但分詞效果仍不盡如人意。中文分詞的難點(diǎn)主要體現(xiàn)在歧義現(xiàn)象、對(duì)未定義詞的識(shí)別和詞性的多重性幾個(gè)方面。

1.2 N-最短路徑算法簡(jiǎn)介

N－最短路徑的分詞算法的基本思想是根據(jù)詞典，順序匹配出在中文字串中所有可能的出現(xiàn)的詞的集合，所有詞語(yǔ)作為一個(gè)節(jié)點(diǎn)構(gòu)造成為一個(gè)有向無(wú)環(huán)圖。在該圖中起點(diǎn)到終點(diǎn)的所有路徑中，求出每個(gè)節(jié)點(diǎn)的所有到源節(jié)點(diǎn)的路徑值，每個(gè)路徑值對(duì)應(yīng)一個(gè)路徑集合，作為相應(yīng)的分詞結(jié)果集。

設(shè)待分字串S= c1c2…cn，其中ci=(i=1，2，…，n)為單個(gè)的字，n為串的長(zhǎng)度，n≥1.建立一個(gè)結(jié)點(diǎn)數(shù)為n +1 的切分有向無(wú)環(huán)圖G，各結(jié)點(diǎn)編號(hào)依次為V0，V1，V2，…，Vn。

通過(guò)以下兩種方法建立G所有可能的詞邊。

1)相鄰結(jié)點(diǎn)Vk－1，Vk之間建立有向邊＜Vk－1，Vk ＞，邊的長(zhǎng)度值為L(zhǎng)k，邊對(duì)應(yīng)的詞默認(rèn)為ck(k=1，2，…，n)。

2)若w= cici+1…cj是一個(gè)詞，則結(jié)點(diǎn)Vi－1，Vj之間建立有向邊＜Vi－1，Vj ＞，邊的長(zhǎng)度值為L(zhǎng)w，邊對(duì)應(yīng)的詞為w(0＜i ＜j≤n)。

這樣待分字串S中包含的所有詞與切分有向無(wú)環(huán)圖G中的邊一一對(duì)應(yīng)(見(jiàn)圖1)。

這樣，對(duì)句子的最短切分問(wèn)題就轉(zhuǎn)化為找出圖1 中從開(kāi)始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的最短路徑問(wèn)題［4］。

圖1 分詞路徑圖

基于N－最短路徑的分詞算法，需要計(jì)算有向圖中從起點(diǎn)到終點(diǎn)的所有路徑值，分詞效率低。

2 改進(jìn)的N－最短路徑算法

正確、快速的中文分詞算法，會(huì)提高排歧、未登錄詞的識(shí)別、詞性標(biāo)注的最終效果，提高中文詞語(yǔ)分析質(zhì)量。本文在對(duì)多種算法的優(yōu)劣進(jìn)行分析之后，在N－最短路徑算法的基礎(chǔ)上，采用動(dòng)態(tài)算法在舊的最短路徑的基礎(chǔ)上，刪除某條弧，并尋找替換的弧來(lái)尋找下一條可選的最短路徑，即通過(guò)在有向圖中增加附加節(jié)點(diǎn)和相應(yīng)的弧來(lái)實(shí)現(xiàn)，減少了搜索路徑范圍，計(jì)算速度快，分詞效率高。

2.1 對(duì)算法的改進(jìn)

將動(dòng)態(tài)刪除算法［5－8］與最短路徑算法結(jié)合起來(lái)，可以改進(jìn)分詞的效率。動(dòng)態(tài)刪除算法的原理是建立一個(gè)最短路徑樹(shù)更新隊(duì)列，將所有將被刪除節(jié)點(diǎn)的子孫節(jié)點(diǎn)保存到該隊(duì)列;從原最短路徑樹(shù)中刪除需要被刪除的節(jié)點(diǎn)和其所有子孫節(jié)點(diǎn);從隊(duì)列中選取與根節(jié)點(diǎn)距離最短的節(jié)點(diǎn)進(jìn)行更新，已更新節(jié)點(diǎn)不再被插入隊(duì)列，從而減少節(jié)點(diǎn)更新次數(shù)。

改進(jìn)后的算法描述如下:

1)根據(jù)N－最短路徑算法構(gòu)造分詞路徑圖1所示的圖G(E，R)，計(jì)算從開(kāi)始節(jié)點(diǎn)V0到結(jié)束節(jié)點(diǎn)Vn的最短路徑為L(zhǎng)j，j=1。

2)IF(j＜最短路徑數(shù))and(候選路徑存在)Then 更新當(dāng)前路徑L為L(zhǎng)j。否則，程序結(jié)束。

3)刪除當(dāng)前路徑中第一個(gè)節(jié)點(diǎn)開(kāi)始的入度大于1 的第一個(gè)節(jié)點(diǎn)，記為Hm，如果被刪除節(jié)點(diǎn)的子孫節(jié)點(diǎn)不在集合E中，則轉(zhuǎn)4);否則從G中刪除Hm節(jié)點(diǎn)和其所有的子孫節(jié)點(diǎn)，轉(zhuǎn)5)。

4)計(jì)算從開(kāi)始節(jié)點(diǎn)V0到Hm的最短路徑，記最短路徑的結(jié)束節(jié)點(diǎn)為H'm。

5)對(duì)于從Hm之后的所有節(jié)點(diǎn)，重復(fù)過(guò)程3)。

6)更新當(dāng)前路徑樹(shù)，求得從節(jié)點(diǎn)V0到所有結(jié)點(diǎn)H'm的最短路徑，j=j+1，轉(zhuǎn)2)繼續(xù)。

2.2 算法示例

以“他說(shuō)的確實(shí)有用”為例，假設(shè)N=3，看一下求解的過(guò)程。圖2 是構(gòu)造的有向圖。

圖2 初始構(gòu)造的有向圖

利用上述算法計(jì)算最短路徑，求其第j條最短路徑，算法的執(zhí)行過(guò)程中，圖1 的變化如圖3～圖6所示。其中粗線表示當(dāng)前狀態(tài)下的最短路徑，虛線圈刪除某一節(jié)點(diǎn)更新后生成的節(jié)點(diǎn)。

圖3 j=1 時(shí)的最短路徑

圖4 j=2 時(shí)的最短路徑

圖5 j=3 時(shí)的最短路徑

圖6 j=4 時(shí)的最短路徑

在算法求解過(guò)程中，還可以繼續(xù)對(duì)j值增加，繼續(xù)尋找最優(yōu)路徑，尋找方法同上，由于篇幅有限，不再進(jìn)行描述。實(shí)際上，N－最短路徑算法的路徑搜索過(guò)程，就是在最短路徑和最大路徑的折中方法。在求解的過(guò)程中，通過(guò)保留前j個(gè)最優(yōu)路徑，j的取值應(yīng)該選擇一個(gè)適中的值，取值過(guò)大會(huì)影響搜索的速度，取值過(guò)小，又會(huì)影響分詞的準(zhǔn)確性。

3 實(shí)驗(yàn)與結(jié)果分析

基于Java 開(kāi)發(fā)平臺(tái)，對(duì)上述的分詞算法進(jìn)行了實(shí)現(xiàn)，針對(duì)從網(wǎng)易、新浪、騰訊等網(wǎng)站的監(jiān)測(cè)內(nèi)容進(jìn)行對(duì)比實(shí)驗(yàn)，測(cè)試的文本總量為300 篇。實(shí)驗(yàn)采用統(tǒng)計(jì)的方法，對(duì)不同的K值，首先統(tǒng)計(jì)出每一文章的句子字節(jié)總數(shù)SUM，根據(jù)算法系統(tǒng)的運(yùn)行時(shí)間和結(jié)果，統(tǒng)計(jì)每一篇文章分詞所用時(shí)間T，從分詞結(jié)果中計(jì)算出分詞正確的詞的數(shù)量FSUM，分詞的正確率=(正確粗分的句子數(shù)量FSUM/句子總數(shù)SUM)* 100%;分詞的速度=(句子字節(jié)總數(shù)SUM/分詞所用時(shí)間T)。通過(guò)多次測(cè)試實(shí)驗(yàn)，并參照同行公布的試驗(yàn)數(shù)據(jù)，本文改進(jìn)的算法與其他算法的性能對(duì)比如表1所示。

表1 業(yè)界公布的數(shù)據(jù)與本文的分詞系統(tǒng)對(duì)比

本文的數(shù)據(jù)來(lái)源于實(shí)驗(yàn)數(shù)據(jù)，由于測(cè)試結(jié)果與系統(tǒng)的實(shí)際運(yùn)行環(huán)境有關(guān)，在實(shí)際應(yīng)用時(shí)，分詞速度可能與本實(shí)驗(yàn)有一定的誤差。

4 總結(jié)

本文對(duì)N－最短路徑算法進(jìn)行了改進(jìn)，將動(dòng)態(tài)刪除算法與最短路徑算法結(jié)合起來(lái)，可以改進(jìn)分詞的效率。通過(guò)對(duì)從網(wǎng)站上監(jiān)測(cè)的內(nèi)容進(jìn)行分詞實(shí)驗(yàn)測(cè)試，將測(cè)試結(jié)果與業(yè)務(wù)公布的算法的效率進(jìn)行比較，結(jié)果表明此方法的分詞速度得到了一定的改善。

［1］葉繼平，張桂珠.中文分詞詞典結(jié)構(gòu)的研究與改進(jìn)［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(23):139－142.

［2］李玲.基于雙詞典機(jī)制的中文分詞系統(tǒng)設(shè)計(jì)［J］.機(jī)械工程與自動(dòng)化，2013，176(1):17－19.

［3］李振星，徐澤平，唐衛(wèi)清，等.全二分最大快速分詞算法［J］.計(jì)算機(jī)工程與應(yīng)用，2002，38(11):106－109.

［4］苗奪謙.中文文本信息處理的原理與應(yīng)用［M］.北京清華大學(xué)出版社，2008:26.

［5］粱德恒，姚國(guó)樣，官全龍.基于路由最短路徑樹(shù)的動(dòng)態(tài)多節(jié)點(diǎn)刪除算法［J］.計(jì)算機(jī)工程，2011，37(5):121－123.

［6］劉代波，侯孟書(shū)，武澤旭，等.一種高效的最短路徑樹(shù)動(dòng)態(tài)更新算法［J］.計(jì)算機(jī)科學(xué)，2011，38(7):96－99.

［7］韓月陽(yáng)，鄧世昆，賈時(shí)銀，等.基于字分類(lèi)的中文分詞的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2011，21(7):29－31.

［8］孫知信，高艷娟，王文鼐.更新最短路徑樹(shù)的完全動(dòng)態(tài)算法［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2007，37(4):860－864.