摘要：对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
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格式阅读原文”
TAG: 分词 英文字符串
