一種快速的交集型歧義檢測方法

（國防科學技術大學 信息系統與管理學院， 長沙 410073）



摘要：中文分詞中，交集型歧義檢測方法采用的雙向最大匹配法與全切分方法存在著各自的弊病，無法滿足大規模數據的精確處理。為此，提出了一種快速的交集型歧義檢測方法，引入次長詞進行檢測，能高效準確地檢測出中文文本中的交集型歧義。經實驗驗證，該方法在精度與速度兩方面均能滿足大規模語料的處理。

關鍵詞：中文分詞; 交集型歧義; 最長交集字段

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001-3695(2008)11-3259-03



Fast crossing ambiguity detection method



LIU Jian， ZHANG Wei-ming



（School of Information System Management， National University of Defense Technology， Changsha 410073， China）



Abstract:In Chinese word segmentation， the FBMM and word omni-segmentation were widely used to detect OAS， but the shortcomings of their existence make them unable to meet demand. This paper presented a rapid crossing ambiguity detection method， which could efficient and accurate detect the OAS. The experiment shows the new method accuracy and speed in the two areas can meet the handling large-scale corpus.

Key words：Chinese word segmentation; crossing ambiguity; maximal overlapping ambiguity string(MOAS)



中文分詞技術是中文信息檢索、中文自然語言處理等應用的基礎。目前，中文分詞技術面臨的主要問題在于兩個方面，即歧義的處理和未登錄詞的識別。其中歧義按照類型可以分為交集型歧義、組合型歧義兩種類型。根據統計數據表明，在所有歧義中，交集型歧義有90％左右，占絕大多數，因此目前的研究也基本集中在交集型歧義的處理上。孫茂松等人^[1]通過對1億字的語料進行統計，提出了最長交集字段（MOAS）的概念，發現96％的MOAS是偽歧義（這種歧義字段只有一種固定的切分路徑），僅有4％的MOAS屬于真歧義，并由此提出了可以通過記憶的方法提高交集型歧義字段的切分準確率。但是這種方法實現的前提是利用語料庫進行處理，找出所有的MOAS并構造歧義切分字典，因此MOAS的檢測與提取成為該項技術的關鍵。

MOAS根據其長度可以分為三類：字長大于詞典詞（如“結合成分子時”，歧義結構是“結合—合成—成分—分子—子時”）、字長等于詞典詞（如“中學生”，歧義結構是“中學—學生”）、字長小于詞典詞（如“枉費心機”中“費心機”、歧義結構是“費心—心機”）。筆者通過統計1億字的語料，檢測出MOAS段型數為946 200，其中長度等于字典詞的MOAS共有120 413，占12.73%，通過例句與內省的方式進行檢查，發現屬于偽歧義的有90％左右；小于詞表詞的MOAS共有9 329，占總數的1％，其切分方式均服從字典詞，該統計結果與李斌等人^[2]的結論基本一致。由于長度小于字典詞的MOAS均服從字典詞的切分，在MOAS的檢測過程中可以忽略；而等于字典詞長的MOAS一方面由于其數量較多，另一方面其中大量為偽歧義，可能對語義信息產生誤導，因此需要保留。

MOAS的檢測目前都采用基于字典的機械分詞方法，主要是雙向最大匹配法（forward-backward maxmum， FBMM）與全切分方法。這兩種方法都存在不同程度的缺陷：最大雙向匹配法盡管速度很快，但是在MOAS檢測中，一方面無法檢測小于等于字典詞長的MOAS，另一方面對于鏈長為偶數的MOAS也會被忽略；全切分方法雖然可以檢測出所有的MOAS，但是運算速度很慢，時間開銷是前一種方法的上百倍^[3]，不適合處理大規模的語料數據。

針對以上問題，本文結合最大雙向匹配法與全切分方法的優勢，利用最長詞與次長詞進行交叉檢測，提出了一種快速MOAS檢測算法，并在大規模語料上進行了精度與速度的實驗。結果表明該方法可以檢測出所有大于等于字典詞的MOAS，同時具備高效快速的特點，適合海量數據處理。

1基本思想

通過對最大雙向匹配方法與全切分方法的考察，發現最大雙向匹配算法由于使用了長詞優先^[4]的原則，并且僅依次在每個最長詞的結束位置使用該原則，沒有對句子的每個位置都進行檢測，而交集型歧義則可能在這個最長詞內部開始產生。例如短語“是非常有意義”是鏈長為4的MOAS，其正確切分應為“是—非常—有—意義”，歧義正向、反向切分結果均為“是非—常有—意義”從而產生漏檢。因此，對于鏈長為偶數的MOAS，正反方向的切分必然一致從而產生漏檢。其次，即使在每個位置都進行檢測，由于等于詞長MOAS僅僅在這個位置的最長詞內部出現，如對于句子“中國人萬歲”，假設詞典中存在“中國”“國人”“中國人”這三個詞條，“中國人”覆蓋了其他兩個詞條，等于字典詞長的MOAS“中國人”被漏檢，最大雙向匹配方法也無法檢測出等于詞長的MOAS。全切分方法在句子的每個位置都進行檢查，并且將詞條切碎進行檢查，不僅僅依靠最長詞，因此可以檢測出所有的MOAS，但是該方法將詞條切分得過細甚至切分成單字，做了很多重復的工作，從而導致了算法效率低下。

由此，可以得到幾點結論：a)如果要檢測出所有的MOAS，必須對句子的每個位置都進行檢測；b)僅使用最長詞檢測是無法檢測出等于字典詞長的MOAS，必須引入新的機制；c)要提高算法效率，就不能將詞條粒度切得太小。

首先引入幾個概念：

定義1次長詞。它是指在句子某個位置開始的詞條集合中第二長的非單字的詞。



比如“中學生”這個詞中，次長詞為“中學”“中國人”中，次長詞為“中國”。

定義2初始最長詞。每次檢查開始時提取的最長詞稱之為初始次最長詞。

定義3過程最長詞。在對初始最長詞檢測過程中每個位置提取的最長詞稱之為過程最長詞。

例如句子“中國人民萬歲”，第一個初始最長詞是“中國人”“國人”“人民”均是檢測過程中提取的最長詞，屬于過程最長詞，而“萬歲”是在對于初始最長詞“中國人”檢測結束后提取的最長詞，應屬于初始最長詞。

定理 1所有字長等于字典詞長的MOAS中，其首字次長詞必定與其后續詞產生交集。

證明設字典詞wi，n為MOAS，其次長詞wi，m，交集位置為j，k，…，l，只需證明j，k，…，l中，至少有一個小于等于次長詞結束位置m。

設第一個交集位置為j，wi，t是產生交集的第一個詞且不是次長詞，從交集型歧義定義可知j＜t，又根據次長詞定義有t＜m，因此有j＜m，從而可得j，k，…，l中，至少有一個小于等于次長詞結束位置m。證畢。

新方法的思想可以歸納為：當進行檢測時，首先提取當前位置的初始最長詞及次長詞，查找次長詞第二個字至尾字每個位置的最長詞，比較這些過程最長詞的結束位置與次長詞的結束位置，如過程最長詞結束位置大于次長詞結束位置，則表示存在交集型歧義，將結束位置置為產生歧義的過程最長詞結束位置，并從該過程最長詞第二個字至其尾字每個位置繼續檢查，重復該過程，直至無交集型歧義產生；再判斷結束位置與最長詞結束位置關系，如小于最長詞結束位置，說明該MOAS字長小于最長詞，可以丟棄，但是仍需要從該結束位置至初始最長詞結束位置繼續進行檢測。例如結束位置大于等于初始位置最長詞，則說明基于初始最長詞的MOAS檢測結束，提取初始最長詞起始位置至結束位置作為MOAS字段。

可以看到，采用次長詞之后，在最長詞內部也進行了檢查，等于字典詞長的MOAS就可以被檢測到，由于次長詞并非單字詞，也可以避免全切分方法將詞條粒度切得太小的弊病；同時，在檢測過程中，并不是所有的最長詞都需要提取次長詞進行檢測，僅僅只有初始最長詞是需要提取次長詞，而過程最長詞是不需要提取次長詞的。例如句子“中國人民萬歲”，第一個初始最長詞是“中國人”，該詞與后續最長詞“人民”產生交集，因而最長詞“人民”是過程最長詞，不需要提取次長詞，而“萬歲”是在“中國人”不與其前面的詞產生交集，也屬于初始最長詞，但是其次長詞為單字詞，因而也不需要提取次長詞。

2算法描述

a)提取當前位置i的初始最長詞wi，n與次長詞wi，m，記錄其尾字位置n與m。

b)如果次長詞非單字詞，記錄結束位置nEnd=m；否則以初始最長詞作為次長詞，記錄結束位置nEnd=n。起始位置k=i+1，交叉歧義標志位moas＝1。

c)查找k位置的過程最長詞wk，j。

d)比較該過程最長詞結束位置j與nEnd的關系。如果結束位置j大于nEnd，置nEnd＝j，k=k+1，moas＝true，返回c)執行；如果結束位置j小于等于nEnd，轉e)。

e)判斷k與nEnd關系，如果k小于nEnd，置k＝k+1，返回c)執行；否則轉f)。

f)判斷nEnd與初始最長詞結束位置n的關系。如果nEnd＜n，表示基于初始最長詞的檢測未結束，置nEnd＝n，moas＝1，k＝k＋1，轉c)執行；如果nEnd≥n且moas=true，轉g)。

g)提取i至nEnd位置字串作為最大交集型歧義字段，輸出。

該算法的偽代碼表示為：

MOAS_Detection (S)

輸入：句子 S

輸出：最大交集型歧義字段 MOAS[]

for (i=0;i

moas=1; k=i+1;

(n，m)=GetMaxAndSecondWord();

//查找以第i個字為首的最長詞與次長詞;

if(IsSingle()) nEnd=m; else nEnd=n;

CheckWord(k，nEnd，moas);

if(nEnd

nEnd=n;moas=1;k=k+1;

CheckWord(k，nEnd，moas);

}

if(nEnd>n ‖ (nEnd==n moas)){

AddMOAS(i，nEnd);

}

i=nEnd;

}

CheckWord(i，nEnd，moas)

{

for(t=i+1;t<=nEnd;t++){

j=GetMaxWord(t);//提取t位置最長詞

if(j>nEnd){//存在交集型歧義

moas=true;

nEnd=j;

}}}

以“中國人民萬歲”為例，描述其算法流程。

首先，當前位置i為0，查找以“中”起始的最長詞與次長詞，分別為“中國人”與“中國”，記錄n為“中國人”結束位置2，nEnd等于m為“中國”結束位置1。從位置1開始查找過程最長詞為“國人”，其結束位置為2，大于nEnd，表示存在交集型歧義，置nEnd為2；位置2查找到的最長詞為“人民”，其結束位置為3，大于nEnd，置nEnd為3；位置3查找最長詞為“民”，其結束位置等于nEnd，表示不存在歧義，將當前nEnd與n比較，由于nEnd大于n，表示基于最長詞“中國人”的檢測結束且該MOAS大于字典詞長，記錄位置0開始至3的MOAS為“中國人民”。置i等于nEnd＋1為4，查找該位置最長詞與次長詞，分別為“萬歲”與“萬”。由于“萬”詞長小于2，置nEnd等于n為5，從位置5開始查找最長詞為“歲”，其結束位置等于nEnd，不存在歧義，基于最長詞“萬歲”的檢測結束。置i等于nEnd＋1，該位置為結束符，算法結束。

3算法復雜度比較分析

對于長度為N的句子，本算法需要檢查每個位置i（0≤i≤N）的最長詞，并且在初始位置的還需提取次長詞。由于次長詞在查找最長詞的過程就可以同時記錄，時間開銷可以忽略不計。設字典最長詞長度為T，對于使用TRIE樹組織的字典來說，每個位置的搜索長度最壞情況下的時間復雜度是O(T)，對于整個句子則是O（N×T）。一般來說，句子長度N 都是遠大于詞典字長T。此外，結束位置比較的處理時間很短可以忽略不計，因此，整個算法時間復雜度最壞情況下約等于O(N)。

對于全切分方法，由于要在每個位置查找字典，提取以該字為首的每個可能的詞（包括單字），同樣設字典中最長詞長度為T，每個位置處理的次數是 (T+1)×T/2，時間復雜度則為O（T2）。對于長度為N的句子，該算法的總體時間復雜度為O(N×T2)，最壞情況下約等于O(N2)。

對于雙向最大匹配法，并不在所有位置提取最長詞，而是僅僅在每個最長詞結束位置的后續位置進行提取。因此對于長度為N的句子進行一次掃描的判斷次數是T×logT N，正反雙向掃描判斷次數2×T×logT N，整個算法的時間復雜度為O(log N)。

由上面分析可以看出，三種算法的時間復雜度的關系為FBMM＜快速檢測算法＜全切分。快速檢測算法的時間復雜度介于雙向最大匹配法與全切分方法之間。

4算法性能

筆者在Windows XP平臺上利用C＃語言實現了雙向最大匹配法、全切分法與快速MOAS檢測算法，并針對不同語料進行了精度與速度的測試，測試計算機處理器為P4 2.26 GHz、內存1 GB。

第一次實驗采用1998年1月人民日報（199801）共8 MB作為語料進行了精度測試，并比較了這三種方法檢測到的MOAS數量，結果如表 1所示。

從表 1可以看出，最大雙向匹配法無法檢測出長度小于等于字典詞長的MOAS，并且檢測到的MOAS數量大約是全切分方法的50％，因此使用這種方法提取MOAS會有較大的遺漏；全切分方法可以提取的MOAS數量最多，包括了小于等于詞長的MOAS；快速檢測法從語料中提取的MOAS與全切分方法相比，數量上僅僅缺少了小于詞典字長的MOAS，這也正是筆者所希望的結果。從這次測試中可以看出，快速MOAS檢測算法提取字長大于等于字典詞長的MOAS與全切分方法相當，能達到100％的檢測精度。

第二次實驗采用收集到的各類電子文本報刊、小說、資料共305 MB進行了速度測試，三種方法的處理時間如圖 1所示。

從測試結果可以看出，最大雙向匹配法的速度最快，而快速檢測法的檢測速度與之相當，全切分方法處理時間最長，接近前兩者的200倍。

兩次實驗證明了本文提出的快速檢測算法具有速度快、檢測MOAS數量全的優點，適合于大規模數據的MOAS提取。

5結束語

本文提出了一種快速的交集型歧義檢測算法。該方法引入次長詞進行檢測，并融合了全切分方法與雙向最大匹配法的優點。算法分析與實驗驗證表明：該方法可以100％檢測出大于等于字典詞長的最大交集型歧義，同時算法復雜度介于FBMM和全切分法之間，接近FBMM法，適合大規模的語料處理。該方法已經被用于筆者開發的分布式信息檢索系統中，取得了很好的實際使用效果。

參考文獻：

［1］孫茂松，左正平. 漢語真實文本中的交集型切分歧義[M]//漢語計量與計算研究. 香港：香港城市大學出版社， 1998:323-338.

[2]李斌， 陳小荷，方芳，等. 基于語料庫的高頻最大交集型歧義字段考察[J].中文信息學報， 2006，20(1):1-6.

[3]王顯芳， 杜利民. 一種能夠檢測所有交叉歧義的漢語分詞算法[J].電子學報，2004，32(1):50-54.

[4]劉開瑛. 中文文本自動分詞和標注[M]. 北京: 商務印書館， 2000.

[5]侯敏， 孫建軍， 陳肇雄. 漢語自動分詞的歧義問題[M]//計算語言學進展與應用. 北京：清華大學出版社， 1995.

[6]孫茂松，左正平，鄒嘉彥，等. 高頻最大交集型歧義切分字段在漢語自動分詞中的作用[J].中文信息學報， 1997，13(1):27-34.