近邻匹配算法实现中文分词.docx

近邻匹配算法实现中文分词摘要计算机进行中文分词的处理过程最重要的就是分词算法。现有的中文分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法。本文基于字符串匹配方法使用近邻匹配算法提高了效率。关键词中文分词哈希查找二分查找中图分类号：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、如果当前匹配长度小于最大匹配长度或词表中的词条比字串大结束寻找过程然后用同样方法切分下一词条。算法实现如下：NeighborhoodMatching{inttotalOffset=0；intstrLen=strlen（P）；while（totalOffsetintresult=-O；//计算索引项的地址Unsignedcharq=*P；unsignedcharw=*（P+1）：q-=0xB0；W-=0xA1：Char**Pi=ptrArray[q][w]；intn；//词条数；intindex=FindWord（4（char*）C0C1&result）；if（index==-1）{/*没找到）C0C1还不能确定它是某个词条的前缀还是应分开*/start=result+l；}else{start=index+l：matchMax=l；}intoffset=2；∥跳过首字intbContinued=l；∥是否继续查找标志while（start0）{bContinued=l；Char*wordPtr=Pi[start]；intwordLen=strlen（wordPtr）-2；if（*（P+offset）！=*wordPtr||*（P+offset+1）！=*（wordPtr+1））break；i=2；while（iif（*（P+offset+i）==*（wordPtr+i））i++；else{//如果字串比词条小退出当前循环bContinued=*（textPtr+offset+i）-*（wordPtr+i）；break；}}//完全匹配if（i==wordLen）{i>>=l；if（ibreak；elsematchMax=i；start++；//准备匹配下一词条//处理下一个词offset+=matchMaxP+=offset；TotalOffset+=offset）}}}在上述算法实现的切分情况在切分“中国人民解放军成功守住了大堤”时词表中以“中一开头的词有100多个以“中国"开头的词有“中国人民”、“中国青年”、“中国银行"、“中国政府”找到“中国”后在其后找“中国人民”一词只需两次词条匹配操作即可。由于本文采用的是词表结构支持首字Hash和标准的二分查找方法避开了词表访问过程中的I/O操作并且在分词过程中采用近邻匹配算法大大降低了时间复杂度根据表3-1的统计数据单字词的出现频率约为56.75%二字词的出现频率