《一种对英文字符串进行分词的方法.doc》由会员分享，可在线阅读，更多相关《一种对英文字符串进行分词的方法.doc（8页珍藏版）》请在三一文库上搜索。
1、一种对英文字符串进行分词的方法0引言 分词（Words Segmentation）是词法分析、语义分析、自然语言理解的基础。中文分词是当前计算语言学的一个重点和难点。英文分词在一般情况下要简单一些，因为英语的词与词之间有间隔符，如空格和标点。但是在一些特殊情况下，英文分词也存在与中文分词类似的难题。如果要对数据库的表和字段进行数据库模式映射（Schema Mapping）或语义理解时，它们的名称是必须考虑的重要元素。这些名称一般由多个词组成，并且词与词之间一般不会有分隔符，而要理解这些名称语义的前提就是对它们进行分词。 对英文字符串的分词算法非常少见。为此，本文在字典匹配算法基础上，设计了一种
2、高效、快速的英文分词算法。本文采用的字典匹配算法是AhoCorasick（以下简称AC）算法1。首先将一个收集词汇比较全面的词典组织成一个AC树（一种特殊的自动机），然后利用这一自动机将英文字符串进行字典匹配。由于字典收集的词汇比较全面，这一字典匹配的结果可以看成是英文字符串在所有英文单词上的全切分。对字符串全切分的结果，本文给出了一种高效、快速的按词汇优先级进行分词的算法。 1AC算法简介 2分词算法 字典匹配的结果是字符串在字典上的全切分，因此词与词之间可能会互相交叠。在进行分词时则不允许词交叠，因此需要确定一种对全切分结果词之间的取舍标准。为此，规定字典中的词是有优先级的，并且规定字典中
3、的词按优先级从高到低顺序排列。对全切分结果进行分词时，如果有词交叠，则保留最高优先级的词而删除与其交叠的低优先级词。 对于用有优先级的字典进行分词，有以下定理和推论： 定理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。 该算法首先将字典按要求准备好，并存放到按优先级排
4、序的数组DICT中，即数组下标小的优先级高。在用AC算法进行字典匹配时，按状态转移顺序将Output表写到数组ALLPARTITION中，这个数组实质上是一个双向链表。同时，将Output表写到ALLPARTITION之前，还要对Output表进行排序，使低优先级词排序在前，然后才将其按顺序写到ALLPARTITION中。最后得到的ALLPARTITION数组显然就是AC算法全切分结果。ALLPARTITION数组数据项的结构如下： struct PARTITION_WORD int index; /词在字典DICT中的下标号 int start; /词在字符串T中的开始位置 int end;
5、 /词在字符串T中的结束位置 int suffix_num; /本状态所表示的字符串的所有后缀是词的个数 int left; /*词左边的尚未删除的词在ALLPARTITION中的下标号，如果词在ALLPARTITION中的下标号为0，或从0到这个词（可不含）都被删除，则为1*/ int right; /*词右边的尚未删除的词在ALLPARTITION中的下标号，如果词是ALLPARTITION中的最后一个词，或从这个词（可不含）到最后一个词都被删除，则为全切分词的个数*/ short deleted; /0表示词未被删除，1表示词已被删除 为了能够按照上述要求组织全切分结果和节省内存，取消了
6、AC算法中的Output表，并对AC树中的状态节点进行了改进。在状态节点结构中，增加两个结构项，即当前状态节点所对应的字符串的所有后缀是词的个数suffix_num，及当前状态节点所对应的字符串是否为词Output。若是则为该词在字典中的下标号，否则为1。AC状态节点的结构定义如下： struct AC_STATE int state_id; /状态编号 int depth; /从根到当前状态节点的路径长度 short suffix_num; /当前状态节点所表示的字符串的所有后缀是词的个数 int output; /*如果当前状态节点所表示的字符串是词，则为该词在字典中的下标号，否则为1*/
7、 AC_STATE *fail; /失败指针 AC_STATE *transCHAR_NUM; /指向后继状态的指针数组，CHAR_NUM=| 在向AC树中加入词时，置词的最后字符所在的状态节点的suffix_num为1，output为词在字典中的下标号；其他字符所在的状态节点的suffix_num为0，output为1。在构造失败指针时，同时计算出suffix_num。其计算方法为suffix_numsuffix_num+fail-suffix_num。 while (i0) /将状态state的Output表按要求写入ALLPARTITION while (suffix-outputfai
8、l; ALLPARTITIONpos+i.index=suffix-output; ALLPARTITIONpos+i.start=j-strlen(DICTsuffix-output)+1; ALLPARTITIONpos+i.end=j; ALLPARTITIONpos+i.suffix_num=suffix-suffix_num; ALLPARTITIONpos+i.left=pos+i-1; ALLPARTITIONpos+i.right=pos+i+1; ALLPARTITIONpos+i.deleted=0; suffix = suffix-fail; -i; pos+=state
9、-suffix_num; 对于ALLPARTITION数组中的数据，有以下性质： 性质3如果ij，则ALLPARTITIONi.endALLPARTITIONj.end。 性质4如果ALLPARTITIONi.endALLPARTITIONj.end，则ij。 性质5如果ij且ALLPARTITIONi.end=ALLPARTITIONi+1.end=ALLPARTITIONj.end，则DICTALLPARTITIONi.index,DICTALLPARTITIONi+1.index,DICTALLPARTITIONj.index为一组后缀词，且长度由短到长，优先级由低到高。 性质3和4是明
10、显的。性质5中的词ALLPARTITIONx（ixj）实质上就是某个状态的Output表中的词按照前面的要求排序后的结果。这可以用AC算法性质1和性质2、本文的推论1以及得到ALLPRATITION数组数据的方法进行证明。 性质5表明，同一组后缀词中，高优先级词在后面。为此，分词算法从后向前扫描数组ALLPARTITION，以找到一个结果词，这个词的优先级比与其交叠的词的优先级都高；删除与它交叠的词后，再分别对ALLPARTITION数组的前、后部分用同样的方法扫描，以找到下一个结果词。根据推论1，一个词的真后缀词的优先级总是低于词本身的优先级，因此扫描时直接向前跳过suffix_num个词。
11、分词算法伪代码如下（一开始将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) 删除wordsendpos的真后缀词； return; /搜索一个结果词，注意搜索时每次都跳过suffix_num个词 maxpos=endpos; curpos=maxpos-wordsmaxpos.suffix_num; while(curpos=startpos) & & (wordscurpos.end=wordsmaxpos.start) /如果wordscurpos的优先级大于wordsmaxpos if (wordscurpos.indexmaxpos) if (wordscurpos.start