一種對英文字符串進行分詞的方法

摘要：對Aho－Corasick算法略作改變，用一個收詞豐富的有優先級的字典構造Aho－Corasick樹，并利用它對英文字符串進行字典匹配。對匹配的結果，利用后綴詞按優先級排序的特點設計了一個高效的分詞算法。實驗證明該算法具有高效性。

關鍵詞：字典匹配； 英文分詞； 后綴詞

中圖分類號：TP311文獻標志碼：A

文章編號：1001－3695(2007)07－0052－03

0引言

分詞（Words Segmentation）是詞法分析、語義分析、自然語言理解的基礎。中文分詞是當前計算語言學的一個重點和難點。英文分詞在一般情況下要簡單一些，因為英語的詞與詞之間有間隔符，如空格和標點。但是在一些特殊情況下，英文分詞也存在與中文分詞類似的難題。如果要對數據庫的表和字段進行數據庫模式映射（Schema Mapping）或語義理解時，它們的名稱是必須考慮的重要元素。這些名稱一般由多個詞組成，并且詞與詞之間一般不會有分隔符，而要理解這些名稱語義的前提就是對它們進行分詞。

對英文字符串的分詞算法非常少見。為此，本文在字典匹配算法基礎上，設計了一種高效、快速的英文分詞算法。本文采用的字典匹配算法是Aho－Corasick（以下簡稱AC）算法[1]。首先將一個收集詞匯比較全面的詞典組織成一個AC樹（一種特殊的自動機），然后利用這一自動機將英文字符串進行字典匹配。由于字典收集的詞匯比較全面，這一字典匹配的結果可以看成是英文字符串在所有英文單詞上的全切分。對字符串全切分的結果，本文給出了一種高效、快速的按詞匯優先級進行分詞的算法。

1AC算法簡介

2分詞算法

字典匹配的結果是字符串在字典上的全切分，因此詞與詞之間可能會互相交疊。在進行分詞時則不允許詞交疊，因此需要確定一種對全切分結果詞之間的取舍標準。為此，規定字典中的詞是有優先級的，并且規定字典中的詞按優先級從高到低順序排列。對全切分結果進行分詞時，如果有詞交疊，則保留最高優先級的詞而刪除與其交疊的低優先級詞。

對于用有優先級的字典進行分詞，有以下定理和推論：

定理1如果字典中詞A的優先級大于詞B，則A不能是B的子串。

證明：用反證法。如果A是B的子串，分詞中如果有B，由于A是B的子串，則必有A且與B交疊；又因為A的優先級大于B，B必被刪除。因此，A不能是B的子串。證畢。

對于不滿足定理1的詞典，可以先進行預處理，使其滿足這一要求。

對于定理1，有如下的一個重要推論：

推論1A、B都是字典中的詞且B是A的真后綴，則B的優先級必然低于A。

該算法首先將字典按要求準備好，并存放到按優先級排序的數組DICT中，即數組下標小的優先級高。在用AC算法進行字典匹配時，按狀態轉移順序將Output表寫到數組ALLPARTITION中，這個數組實質上是一個雙向鏈表。同時，將Output表寫到ALLPARTITION之前，還要對Output表進行排序，使低優先級詞排序在前，然后才將其按順序寫到ALLPARTITION中。最后得到的ALLPARTITION數組顯然就是AC算法全切分結果。ALLPARTITION數組數據項的結構如下：

struct PARTITION_WORD

{

int index; //詞在字典DICT中的下標號

int start; //詞在字符串T中的開始位置

int end; //詞在字符串T中的結束位置

int suffix_num; 

//本狀態所表示的字符串的所有后綴是詞的個數

int left; /*詞左邊的尚未刪除的詞在ALLPARTITION中的下標號，如果詞在ALLPARTITION中的下標號為0，或從0到這個詞（可不含）都被刪除，則為－1*/

int right; /*詞右邊的尚未刪除的詞在ALLPARTITION中的下標號，如果詞是ALLPARTITION中的最后一個詞，或從這個詞（可不含）到最后一個詞都被刪除，則為全切分詞的個數*/

short deleted; //0表示詞未被刪除，1表示詞已被刪除

}

為了能夠按照上述要求組織全切分結果和節省內存，取消了AC算法中的Output表，并對AC樹中的狀態節點進行了改進。在狀態節點結構中，增加兩個結構項，即當前狀態節點所對應的字符串的所有后綴是詞的個數suffix_num，及當前狀態節點所對應的字符串是否為詞Output。若是則為該詞在字典中的下標號，否則為－1。AC狀態節點的結構定義如下：

struct AC_STATE

{

int state_id; //狀態編號

int depth; //從根到當前狀態節點的路徑長度

short suffix_num; 

//當前狀態節點所表示的字符串的所有后綴是詞的個數

int output; /*如果當前狀態節點所表示的字符串是詞，則為該詞在字典中的下標號，否則為－1*/

AC_STATE *fail; //失敗指針

AC_STATE *trans[CHAR_NUM]; 

//指向后繼狀態的指針數組，CHAR_NUM=|Σ|

}

在向AC樹中加入詞時，置詞的最后字符所在的狀態節點的suffix_num為1，output為詞在字典中的下標號；其他字符所在的狀態節點的suffix_num為0，output為－1。在構造失敗指針時，同時計算出suffix_num。其計算方法為suffix_num＝suffix_num+fail->suffix_num。

while (i>0) 

//將狀態state的Output表按要求寫入ALLPARTITION

{

while (suffix->output<0) suffix=suffix->fail;

ALLPARTITION[pos+i].index=suffix->output;

ALLPARTITION[pos+i].start=j-strlen(DICT[suffix->output])+1;

ALLPARTITION[pos+i].end=j;

ALLPARTITION[pos+i].suffix_num=suffix->suffix_num;

ALLPARTITION[pos+i].left=pos+i-1;

ALLPARTITION[pos+i].right=pos+i+1;

ALLPARTITION[pos+i].deleted=0;

suffix = suffix->fail;

--i;

}

pos+=state->suffix_num;

對于ALLPARTITION數組中的數據，有以下性質：

性質3如果i＜j，則ALLPARTITION[i].end≤ALLPARTITION[j].end。

性質4如果ALLPARTITION[i].end＜ALLPARTITION[j].end，則i＜j。

性質5如果i＜j且ALLPARTITION[i].end=ALLPARTITION[i+1].end=…=ALLPARTITION[j].end，則DICT[ALLPARTITION[i].index]，DICT[ALLPARTITION[i+1].index]，…，DICT[ALLPARTITION[j].index]為一組后綴詞，且長度由短到長，優先級由低到高。

性質3和4是明顯的。性質5中的詞ALLPARTITION[x]（i≤x≤j）實質上就是某個狀態的Output表中的詞按照前面的要求排序后的結果。這可以用AC算法性質1和性質2、本文的推論1以及得到ALLPRATITION數組數據的方法進行證明。

性質5表明，同一組后綴詞中，高優先級詞在后面。為此，分詞算法從后向前掃描數組ALLPARTITION，以找到一個結果詞，這個詞的優先級比與其交疊的詞的優先級都高；刪除與它交疊的詞后，再分別對ALLPARTITION數組的前、后部分用同樣的方法掃描，以找到下一個結果詞。根據推論1，一個詞的真后綴詞的優先級總是低于詞本身的優先級，因此掃描時直接向前跳過suffix_num個詞。分詞算法偽代碼如下（一開始將ALLPARTITION數組作為參數傳送給partition函數，最后ALLPARTITION數組中未被刪除的詞即是分詞結果）：

void partition(PARTITION_WORD words[]， int startpos， int end_pos)

{

int curpos， maxpos， endpos， nextendpos;

endpos=end_pos;

while (1)

{

//判斷結束條件

對startpos、endpos進行合法性處理及檢查，合法則繼續，非法則返回；

if (startpos==endpos)

{

刪除words[endpos]的真后綴詞；

return;

}

//搜索一個結果詞，注意搜索時每次都跳過suffix_num個詞

maxpos=endpos;

curpos=maxpos-words[maxpos].suffix_num;

while((curpos>=startpos) (words[curpos].end>=words[maxpos].start))

{

//如果words[curpos]的優先級大于words[maxpos]

if (words[curpos].index

maxpos=curpos;

curpos=curpos-words[curpos].suffix_num;

}

nextendpos=curpos;

//搜索到結果詞，它在ALLPARTITION中的下標是maxpos

//刪除與這個詞交疊的所有詞

刪除words[nextendpos+1，maxpos-1];

curpos=endpos;

while(curpos>maxpos)

{

if (words[curpos].start<=words[maxpos].end)

{

刪除words[curpos];

curpos--;

}

else

{

curpos=curpos-words[curpos].suffix_num;

}

}

partition_words(maxpos+1， endpos); 

//遞歸掃描words[maxpos]右面部分

/*掃描words[maxpos]左面部分。此處為了避免尾部遞歸，采用循環方式*/

endpos=nextendpos;

}

}

3算法分析與實驗

用C++實現整個算法，在Red－hat Linux 7．3上用GCC 2．96編譯器進行編譯，CPU是Intel Pentium Ⅲ 1 GHz，內存為256 MB。字典則采用免費的Part of Speech Database[8]，優先級按詞的長度和字母順序排列。用一個實際使用的數據庫的表的字段名稱作為字符串的來源，長的字符串則用這些字段名稱連接起來得到。為了比較，用Linux中的標準函數strstr()實現機械分詞算法，即首先用最高優先級的詞對字符串進行分詞，再用次優先級的詞對剩下的字符串進行分詞，依此類推。兩個算法的運行結果如表1所示。

表1分詞算法實驗結果

在上面的實驗中，分詞的正確性為100%。用大量的包含會產生歧義的字符串進行了實驗。實驗結果表明，算法并不需要復雜地確定字典優先級的規則，如簡單地以詞的長度、字符順序、使用頻率等來確定優先級，就可以使分詞的正確性在95%以上。

4結束語

對于字典匹配算法，除了AC算法外，還有WuManber算法[2]、Commentz－Walter算法[3]等。文獻[4]則提出了一個動態改變字典的算法。常用的單模式匹配算法見文獻[5~7]。

該文利用AC算法對字符串進行全切分后，利用后綴詞按優先級排序的特點，實現了一個高效的英文字符串分詞算法。這一算法略作修改，即可實現在線分詞。另外，現在的算法要求字典中詞的優先級是靜態的，如何實現動態優先級的分詞值得進一步研究。

參考文獻：

[1]AHO A V， CORASICK M J. Efficient string matching: an aid to bibliographic search[J]. Communication of the ACM， 1975，18(6):333－340.

[2]WU S， MANBER U. A fast algorithm for multi－pattern searching， TR－94－17[R]. Tucson: Department of Computer Science， University of Arizona， 1994:1－11.

[3]COMMENTZ－WALTER B. A string matching algorithm fast on the average: proc.of the 6th Colloquium on Automata， Languages and Programming[C]. London: Springer－Verlag， 1979:118－132.

[4]AMIR A， FARACH M. Adaptive dictionary matching: proc.of the Foundations of Computer Science[C].Atlanta: Georgia Tech， 1991:760－766.

[5]BOYER R S， MOORE J S. A fast string searching algorithm[J]. Communication of the ACM， 1977，20(10):762－772.

[6]KNUTH D E， MORRIS J H， PRATT V R. Fast pattern matching in strings[J]. SIAM Journal on Computing， 1977，6(2):323－350.

[7]KARP R M， RABIN M O. Efficient randomized pattern－matching algorithms[J]. IBM Journal of Research and Development， 1987，31(2):249－260.

[8]ATKINSON K. Part of speech database[EB/OL].[2004－08－10].http://wordlist.sourceforge.net/.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”