《搜索引擎中文分词原理与实现.doc》由会员分享，可在线阅读，更多相关《搜索引擎中文分词原理与实现.doc（9页珍藏版）》请在金锄头文库上搜索。
1、搜索引擎中文分词原理与实现因为中文文本中，词和词之间不像英文一样存在边界，所以中文分词是一个专业处理中文信息的搜索引擎首先面对的问题，需要靠程序来切分出词。一、Lucene中的中文分词Lucene在中处理中文的常用方法有三种，以“咬死猎人的狗”为例说明之： 单 字：【咬】 【死】 【猎】 【人】 【的】 【狗】 二元覆盖：【咬死】 【死猎】 【猎人】 【人的】 【的狗】 分 词：【咬】 【死】 【猎人】 【的】 【狗】Lucene中的StandardTokenizer采用单子分词方式，CJKTokenizer采用二元覆盖方式。1、Lucene切分原理Lucene中负责语言处理的部分在 org.
2、apache.lucene.analysis包，其中，TokenStream类用来进行基本的分词工作，Analyzer类是 TokenStream的包装类，负责整个解析工作，Analyzer类接收整段文本，解析出有意义的词语。 通常不需要直接调用分词的处理类analysis，而是由Lucene内存内部来调用，其中： （1）在索引阶段，调用addDocument（doc）时，Lucene内部使用Analyzer来处理每个需要索引的列，具体如下图： 图1 Lucene对索引文本的处理 IndexWriter index = new IndexWriter(indexDirectory, new C
3、nAnalyzer(), /用于支持分词的分析器 !incremental, IndexWriter.MaxFieldLength.UNLIMITED); （2）在搜索阶段，调用QueryParser.parse（queryText）来解析查询串时，QueryParser会调用Analyzer来拆分查询字符串，但是对于通配符等查询不会调用Analyzer。 Analyzer analyzer = new CnAnalyzer(); /支持中文的分词 QueryParser parser = new QueryParser(Version.LUCENE_CURRENT, title, analy
4、zer); 因为在索引和搜索阶段都调用了分词过程，索引和搜索的切分处理要尽量一致，所以分词效果改变后需要重建索引。 为了测试Lucene的切分效果，下面是直接调用Analysis的例子： Analyzer analyzer = new CnAnalyzer(); /创建一个中文分析器 TokenStream ts = analyzer.tokenStream(myfield, new StringReader(待切分文本); /取得Token流 while (ts.incrementToken() /取得下一个词 System.out.println(token:+ ts); 2、Lucene
5、中的Analyzer 为了更好地搜索中文，通过下图来了解一下在Lucene中通过WhitespaceTokenizer、WordDelimiterFilter、LowercaseFilter处理英文字符串的流程：图2 Lucene处理英文字符串流程二、查找词典算法 词典格式可以是方便人工查看和编辑的文本文件格式，也可以是方便机器读入的二进制格式。词典的最基本文本文件格式就是每行一个词。在基于词典的中文分词方 法中，词典匹配算法是基础。一般词典规模都在几十万词以上，所以为了保证切分速度，需要选择一个好的查找词典算法。1、标准Trie树 一个数字搜索Trie树的一个节点只保留一个字符，如果一个单词
6、比一个字符长，则包含第一个字符的节点有指针指向下一个字符的节点，依次类推。这样组成一 个层次结构的树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，依次类推，数字搜索树的最大高度是词典中最长单词的长度。比 如：如下单词序列组成的词典（as at be by he in is it of on or to）会生成如下图所示的数字搜索树：图3 数字搜索树 数字搜索树的结构独立于生成树时单词进入的顺序，这里，Trie树的高度是2。因为树的高度很小，在数字搜索Trie树种搜索一个单词的速度很快。但是， 这是以内存消耗为代价的，树中每个节点都需要很多内存。假设每个词都是由26个
7、小写英文字母中的一个组成的，这个节点中会有26个指针。所以不太可能直接 用这样的数字搜索树来存储中文这样的大字符集。 Trie树在实现上有一个树类（SearchTrie）和一个节点类（TrieNode）。SearchTrie的主要方法有两个： （1）增加单词到搜索树，方法原型是：addWord（String word）。 （2）从文本的指定位置开始匹配单词，方法原型是：matchLong（String text, int offset）。2、三叉Trie树 在一个三叉搜索树（Ternary Search Trie）中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向
8、左边的树；一个指向右边的树；还有一个向下，指向单词的下 一个数据单元。三叉搜索树是二叉搜索树和数字搜索树的混合体。它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。 树是否平衡取决于单词的读入顺序。如果按顺序后的顺序插入，则生成方式最不平衡。单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不太 重要。通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。如下代码可以用来生成平衡的三叉树词典： /* *在调用此方法前，先把词典数组k排好序 * param fp 写入的平衡序的词典 * param k 排好序的词典数组 *
9、 param offset 偏移量 * param n 长度 * throws Exception */ void outputBalanced(BufferedWriter fp, ArrayList k, int offset, int n) int m; if (n 1;/m=n/2 String item = k.get(m + offset); fp.write(item); /把词条写入到文件 fp.write(n); outputBalanced(fp, k, offset, m); /输出左半部分 outputBalanced(fp, k, offset+m+1, n-m-1)
10、; /输出右半部分 再次以有序的数据单元（as at be by he in is it of on or to）为例。首先把关键字“is”作为中间值并且构建一个包含字母“i”的根节点。它的直接后继节点包含字母“s”并且可以存储任何与“is”有关联的数 据。对于“i”的左树，我们选择“be”作为中间值并且创建一个包含字母“b”的节点，字母“b”的直接后继节点包含“e”。该数据存储在“e”节点。对 于“i”的右树，按照逻辑，选择“on”作为中间值，并且创建“o”节点以及它的直接后继节点“n”。最终的三叉树如下图所示：图4 三叉树 垂直的虚线代表一个父节点下面的直接后继节点。只有父节点和它的直接后
11、继节点才能形成一个数据单元的关键字：i和“s”形成关键字“is”，但是 “i”和“b”不能形成关键字，因为它们之间仅用一条斜线相连，不具有直接后继关系。上图中带圈的节点为终止节点。如果查找一个词以终止节点结束，则说明 三叉树包含这个词。以搜索单词“is”为例，向下到相等的孩子节点“s”，在两次比较后找到“is”；查找“ax”时，执行三次比较达到首字符“a”，然 后经过两次比较到达第二个字符“x”，返回结果是“ax”不在树中。三、中文分词原理 中文分词就是对中文断句，这样能消除文字的部分歧义。除了基本的分词功能，为了消除歧义还可以进行更多的加工。中文分词可以分成如下几个子任务： （1）分词：把输
12、入的标题或者文本内容等分成词。 （2）词性标注（POS）：给分出来的词标注上名词或动词等词性。词性标注可以部分消除词的歧义，例如“行”作为量词和作为形容词表示的意思不一样。 （3）语义标注：把每个词标注上语义编码。 很多分词方法都借助词库。词库的来源是语料库或者词典，例如“人民日报语料库”或者现代汉语大词典。 中文分词有以下两类方法： （1）机械匹配的方法：例如正向最大长度匹配（Forward Maximum Match）的方法和逆向最大长度匹配（Reverse Maximum Matching）的方法。 （2）统计的方法：例如概率语言模型分词方法和最大熵的分词方法等。 正向最大长度品牌的分词
13、方法实现起来很简单。每次从词典中查找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词；如果词典中没有词与其匹配，则按单字切分。例如：Trie树结构的词典中包括如下的词语： 大 大学 大学生 活动 生活 中 中心 心 为了形成平衡的Trie树，把词先排序，结果为： 中 中心 大 大学 大学生 心 活动 生活 按平衡方式生成的词典Trie树如下图所示，其中，粗黑显示的节点可以作为匹配终止节点：图5 三叉树 输入“大学生活动中心”，首先匹配出“大学生”，然后匹配出“活动”，最后匹配出“中心”，切分过程如下表所示： 已匹配上的结果 待匹配串 NULL 大学生活动中心 大学生 活动中心 大学生/活动 中心 大学生/活动/中心 NULL
