吳曉倩 胡學(xué)鋼

摘要：中文分詞技術(shù)是中文信息處理的基礎(chǔ)，快速、準(zhǔn)確的中文分詞方法是進(jìn)行中文信息搜索的關(guān)鍵?；贜-最短路徑的分詞算法，需要計(jì)算有向圖中從起點(diǎn)到終點(diǎn)的所有路徑值，分詞效率低，將動(dòng)態(tài)刪除算法與最短路徑算法結(jié)合，通過從最短路徑中刪除部分節(jié)點(diǎn)的策略減少搜索路徑范圍，從而提高分詞效率。

關(guān)鍵詞：信息處理；中文分詞；N-最短路徑；刪除算法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1672-1098（2014）01-0072-04

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

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

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

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

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

文獻(xiàn)[1]提出了一種改進(jìn)的正向最大匹配算法，改進(jìn)后的算法采用類似TRIE索引樹的逐字匹配算法，消除了正向最大匹配算法的切分盲點(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)的概率反映成詞的可信度，通過統(tǒng)計(jì)文本中各個(gè)字的組合的頻度，計(jì)算它們之間的互現(xiàn)信息，從而判斷漢字之間的緊密程度，當(dāng)緊密程度達(dá)到一個(gè)閾值，就認(rèn)為可能構(gòu)成一個(gè)漢字。

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

12N-最短路徑算法簡介

N-最短路徑的分詞算法的基本思想是根據(jù)詞典，順序匹配出在中文字串中所有可能的出現(xiàn)的詞的集合，所有詞語作為一個(gè)節(jié)點(diǎn)構(gòu)造成為一個(gè)有向無環(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為串的長度，n≥1.建立一個(gè)結(jié)點(diǎn)數(shù)為n+1的切分有向無環(huán)圖G，各結(jié)點(diǎn)編號(hào)依次為V0，V1，V2，…，Vn。

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

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

2） 若w=cici+1…cj是一個(gè)詞，則結(jié)點(diǎn)Vi-1，Vj之間建立有向邊，邊的長度值為Lw，邊對(duì)應(yīng)的詞為w（0

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

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

圖1分詞路徑圖

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

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

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

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

將動(dòng)態(tài)刪除算法[5-8]與最短路徑算法結(jié)合起來，可以改進(jìn)分詞的效率。動(dòng)態(tài)刪除算法的原理是建立一個(gè)最短路徑樹更新隊(duì)列，將所有將被刪除節(jié)點(diǎn)的子孫節(jié)點(diǎn)保存到該隊(duì)列；從原最短路徑樹中刪除需要被刪除的節(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ì)算從開始節(jié)點(diǎn)V0到結(jié)束節(jié)點(diǎn)Vn的最短路徑為Lj，j=1。

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

3） 刪除當(dāng)前路徑中第一個(gè)節(jié)點(diǎn)開始的入度大于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ì)算從開始節(jié)點(diǎn)V0到Hm的最短路徑，記最短路徑的結(jié)束節(jié)點(diǎn)為H′m。

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

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

22算法示例

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

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

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

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

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

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

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

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

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

基于Java開發(fā)平臺(tái)，對(duì)上述的分詞算法進(jìn)行了實(shí)現(xiàn)，針對(duì)從網(wǎng)易、新浪、騰訊等網(wǎng)站的監(jiān)測內(nèi)容進(jìn)行對(duì)比實(shí)驗(yàn)，測試的文本總量為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）。通過多次測試實(shí)驗(yàn)，并參照同行公布的試驗(yàn)數(shù)據(jù)，本文改進(jìn)的算法與其他算法的性能對(duì)比如表1所示。

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

算法正確率/%分詞速度/（kb·s-1）

本文改進(jìn)的算法9727380

基于詞頻詞典的分詞系統(tǒng)PSCWS495160

基于統(tǒng)計(jì)的分詞算法96252133

本文的數(shù)據(jù)來源于實(shí)驗(yàn)數(shù)據(jù)，由于測試結(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é)合起來，可以改進(jìn)分詞的效率。通過對(duì)從網(wǎng)站上監(jiān)測的內(nèi)容進(jìn)行分詞實(shí)驗(yàn)測試，將測試結(jié)果與業(yè)務(wù)公布的算法的效率進(jìn)行比較，結(jié)果表明此方法的分詞速度得到了一定的改善。

參考文獻(xiàn)：

[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]粱德恒，姚國樣，官全龍.基于路由最短路徑樹的動(dòng)態(tài)多節(jié)點(diǎn)刪除算法[J]. 計(jì)算機(jī)工程，2011，37（5）：121-123.

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

[7]韓月陽，鄧世昆，賈時(shí)銀，等.基于字分類的中文分詞的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2011，21（7）：29-31.

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

（責(zé)任編輯：李麗，范君）