词典与后缀数组相结合中文分词方法.docVIP

词典与后缀数组相结合中文分词方法 　　摘 要：　目前中文分词成熟的方法主要有基于字符串匹配和基于统计的分词方法，这两种方法各有优缺点，为达到更好的分词效果，提出一种词典与后缀数组相结合的中文分词算法。其基本思想是首先利用后缀数组快速准确地抽取文档中的中、高频词，同时利用词典进行其他词汇的切分。另外，我们对词典的存储结构进行改进，提高匹配速度。实验证明本算法能够有效的提高分全率和准确率。 　　关键词：　中文分词；基于词典的分词；后缀数组；散列表 　　中图分类号：TP391 文献标识码：A 文章编号：1671－7597（2012）1110151－04 　　随着中国计算机技术的发展，诸多领域对计算机的中文信息处理能力提出了更高的要求，中文分词则是中文信息处理的基石。由于汉语的复杂性和多变性，中文分词已成为中文信息处理的瓶颈[1]。如何进一步提高分词的准确率是众多学者研究的课题。 　　中文分词中遇到的主要问题是歧义问题和未登录词问题[2]，在Bakeoff数据上的评估结果表明，未登录词造成的分词精度失落至少比分词歧义大5倍以上[3]，故解决未登录词问题是提高分词准确率的关键。本文引入的后缀数组能够通过上下文自动识别中高频和未登录词汇，使歧义问题不易出现，但是分全率和准确率较低，无法识别文档中只出现一次的词汇，而中文分词中最基本的基于词典的方法分全率和准确率高[7]，但是不能识别未登录词，因此本文提出了词典与后缀数组相结合的方法，使其兼具基于串匹配和基于统计分词算法的优点，取长补短，以期达到更好的分词效果。 　　1　词典与后缀数组相结合的中文分词 　　本文提出的词典与后缀数组相结合的中文分词算法可分为两步。第一步是基于后缀数组的无词典的处理：读入待分词的文档，将整篇文档存入一个字符串str中，根据此字符串生成一个后缀数组及最长公共前缀信息数组，由此得到汉字的结合模式并存入散列表结构HashMap中，再对HashMap中的汉字结合模式（即候选词）进行处理和筛选，得到的结果就是抽到的词；第二步是基于词典的字符串匹配处理：将上一步基于后缀数组抽取到的词语和一个已有的常用词典结合到???起，共同作为分词所用的词典，采用正向最大匹配算法对待分词文档进行处理，处理单元为句子，对每一个句子分别进行正向最大匹配，得到分词结果。下面分别对这两个步骤所涉及到的问题和算法进行详述。 　　2　基于后缀数组的分词处理 　　基于后缀数组的处理部分主要完成文档中未登录词和中高频词汇的识别，是本算法的先进之处。此部分工作还能使得整个分词算法不易产生歧义。 　　2.1　后缀数组 　　后缀数组是当今算法研究的热门之一，它在Web有哪些信誉好的足球投注网站、文本处理、基因匹配等方面都有着极大的应用潜力。后缀数组是作为一种文本索引结构提出的，它记录某个文本的所有半无限串（起点在文本任意位置，终点在文本尾的字符串）的字典排序。 　　height[i]=h[result[i]]，i从1开始 　　算法结束 　　算法2：最大公共前缀数组的构造算法getLcp 　　height数组即为所求，算法的复杂度为O（n）[6]。求出了h数组，根据关系式height[i]=h[SA[i]]可以在O（n）时间内求出height数组，于是可以在O（n）时间内求出height数组。 　　2.4　基于后缀数组的无词典分词算法 　　有了前面后缀数组、最长公共前缀数组的基础知识和构造方法，接下来我们就可以用这两个数组来识别待分词文档中的未登录词和中高频词汇。 　　第一步，使用后缀数组、最长公共前缀数组抽取汉字的结合模式。 　　我们使用HASHMAP存放提取出来的汉字结合模式。HASHMAP具有速度快，使用方便的优点。HASHMAP由两个元素组成（KEY，VALUE），存放汉字串和汉字串在文章中出现的次数，这里我们用HASHMAP的KEY存放汉字字串，VALUE存放汉字串在文章中出现的次数，VALUE的值至少是2。 　　算法结束 　　算法3：取词算法 　　第二步，对HashMap中的汉字串（候选词）进行处理和筛选，最终得到的结果就是抽到的词语。把第一步中放到HashMap中的汉字串称为候选词集。 　　介绍下筛选算法的依据和思想： 　　在候选词集中，假设有两个汉字串W1和W2。其中W1是W2的子串，在这种情况下，可能W1与W2都是词，也可能只有W1是词而W2不是词，还有可能W2是词而W1不是词。我们使用置信度来进行筛选。 　　汉字串W2相对与W1的置信度为 　　其中TF（W1）和TF（W2）分别是W1和W2的词频。设置置信度的上限是0.90，下限为0.30。若confidence高于上限，则W1可以去除，若是低于下限，则W2可以去除。通过这些规则对候选词集进行处理后，HashMa