摘 要 计算机进行中文分词的处理过程，最重要的就是分词算法。现有的中文分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法。本文基于字符串匹配方法使用近邻匹配算法，提高了效率。
　　关键词 中文分词 哈希查找 二分查找
　　中图分类号：TP391 文献标识码：A
　　一、解决问题的思路
　　在高效字典中，在同样首字下的词条，在内存中是按照汉字内码大小排列的。在词典中匹配成功某个字串后，会在其后面增加一个字即得一个新的字串，如果新字串在词典中出现了，那么新字串一定在原字串后面，且相隔的位置不会太远。近邻匹配算法基于这一特点设计的，使用这种算法避免了每增加一个字就要重新在字典中从头开始匹配的冗余操作，是一种高效的分词算法。该算法的分词过程如下：
　　1、将词库读入内存。这是读入词库切词的第一步，为了提高整个切词的速度，可将整个词库一次性读入内存，并常驻内存。
　　2、读入要切分的中文文本数据。对于待切分的文本数据按行进行处理，每处理一行，就要先将字符数据读入缓冲区，并进行相应的字符集转换。
　　3、从缓冲区中读取搜索字串P=C0C1C2……CL-1。（L为字串长度），根据待搜索字符串P的首字C0，可以根据计算出的C0相应的索引项Ii的地址，并得到以C0为词首字的词数n及指向所有词条：W0W1……Wn-1的指针Pi。如果说，这个字不能成词，那么就退出。
　　4、在词表中查询中，前两个字形成的子串CoCl，得到索引index，然后在index之后寻找最长且完全匹配的词条。
　　5、如果当前匹配长度小于最大匹配长度或词表中的词条比字串大，结束寻找过程，然后用同样方法切分下一词条。
　　算法实现如下：
　　Neighborhood Matching
　　{
　　int totalOffset=0；
　　int strLen=strlen（P）；
　　while（totalOffset　　int
　　result=-O；
　　//计算索引项的地址
　　Unsigned char q=*P；
　　unsigned char w=*（P+1）：
　　q-=0xB0；
　　W-=0x A1：
　　Char**Pi=ptrArray[q][w]；
　　int n；//词条数；
　　int index=FindWord（4，（char*）C0C1，&result）；
　　if（index==-1）{
　　/*没找到）C0C1，还不能确定它是某个词条的前缀还是应分开*/
　　start=result+l；
　　}else{
　　start=index+l：
　　matchMax=l；
　　}
　　int offset=2；∥跳过首字
　　int bContinued=l；∥是否继续查找标志
　　while（start0）{
　　bContinued=l；
　　Char *wordPtr=Pi[start]；
　　int wordLen=strlen（wordPtr）-2；
　　if（*（P+offset）！=*wordPtr ||*（P+offset+1）！=*（wordPtr+1））
　　break；
　　i=2；
　　while（i　　if（*（P+offset+i）==*（wordPtr+i））
　　i++；
　　else{//如果字串比词条小，退出当前循环
　　bContinued=*（textPtr+offset+i）-*（wordPtr+i）；
　　break；
　　}
　　}
　　//完全匹配
　　if（i==wordLen）{
　　i>>=l；
　　if（i　　break；
　　else matchMax=i；
　　start++；//准备匹配下一词条
　　//处理下一个词
　　offset+=matchMax<<1；
　　P+=offset；
　　TotalOffset+=offset）
　　}
　　}
　　}在上述算法实现的切分情况，在切分“中国人民解放军成功守住了大堤”时，词表中以“中一开头的词有100多个，以“中国"开头的词有“中国人民”、“中国青年”、“中国银行"、“中国政府”，找到“中国”后，在其后找“中国人民”一词，只需两次词条匹配操作即可。
　　由于本文采用的是词表结构支持首字Hash和标准的二分查找方法，避开了词表访问过程中的I/O操作，并且在分词过程中采用近邻匹配算法，大大降低了时间复杂度，根据表3-1的统计数据，单字词的出现频率约为56.75%，二字词的出现频率约为39.65%，二字词以上的词的出现频率为3.6%，每个首字下的平均词数为12.35，该算法时间复杂度计算如下：
　　查找单字词无需匹配。
　　查找一个两字词的平均匹配次数为：
　　0.3965 €？log2n = 0.3965 €？log212.35 ≈ 1.44
　　查找一个三字词或高于三字的词平均匹配次数：
　　（1-0.5675-0.3965） €？n / 2 = 0.036 €？13.35 / 2 ≈ 0.22
　　利用这种算法，假设有12万条词库的基础上，在P42.0GHz的电脑，lG内存的平台下，1.2MB的文本在最大匹配算法的状态下，所需时间约为1.0 ～1.1s，在同类算法中是比较优秀的。
　　二、分词算法准确性测试
　　为了检验本论文采用的分词算法的准确性，本论文采用了两段文字进行测试：
　　源文件：中文信息和英文信息相比，有一个明显的差别，英文单词之间用空格分隔；而在中文文本中，单词之间没有天然的分隔符，中文单词大多是两个或两个以上的汉字组成的，并且，语句是连续的，这就要求在对中文文本进行自动分析前，先将整句切割成单词单元，即中文分词。
　　分词结果：中文/信息/和/英文/信息/相比/有/一个/明显/的/差别/英语/单词/之间/用/空格/分隔/而/在/中文/文本/中/单词/之间/没有/天然/的/分隔符/中文/单词/大多/是/由/两/个/或/两/个/以上/的/汉字/组成/的/并且/语句/是/连续/的/这就/要求/在/对/中文/文本/进行/自动/分析/前/先将/整/句/切割/成/单词/单元/即/中文/分词
　　三、结论
　　通过试验得知，本论文采用的分词算法分词精确率达到95%，分词速率快，基本满足了一个中大型搜索引擎的需要。
　　（作者：桂林电子科技大学工程硕士在读，本科学士学位，研究方向：垂直搜索引擎，中文分词）
　　参考文献：
　　[1]刘开瑛，吴伟民.中文文本自动分词和标注.商务印书馆，2000.
　　[2]张恒，杨文昭，屈景辉，卢虹冰，张亮，赵飞.基于词典和词频的中文分词方法.微计算机信息， 2008.
　　[3]刘件.中文分词算法研究.微计算机应用， 2008 .