while (ts.i ncreme ntToke n()) {//取得下一个词搜索引擎中文分词原理与实现因为中文文本中，词和词之间不像英文一样存在边界， 所以中文分词是一个专业处理中文信息的搜索引擎首先面对的问题，需要靠程序来切分出词。
一、LUCene 中的中文分词LUCene 在中处理中文的常用方法有三种，以 皎死猎人的狗"为例说明之：单 字:【咬】【死】 【猎】 【人】 【的】 【狗】二元覆盖：【咬死】 【死猎】 【猎人】 【人的】 【的狗】分词：【咬】 【死】 【猎人】 【的】【狗】LUCene 中的StandardTokenizer 采用单子分词方式， CJKTokenize 采用二元覆盖方式。
1、LUCene 切分原理LUCene 中负责语言处理的部分在 org.apache.Iucene.analysis 包，其中， TokenStream 类 用来进行基本的分词工作， Analyzer 类是TokenStream 的包装类，负责整个解析工作，Analyzer 类接收整段文本，解析出有意义的词语。
通常不需要直接调用分词的处理类 analysis ,而是由LUCene 内存内部来调用，其中：(1) 在索引阶段，调用 addDocument (doc )时，LUCene 内部使用 Analyzer 来处理每 个需要索引的列，具体如下图：图1 LUCene 对索引文本的处理In dexWriter in dex = new In dexWriter(i ndexDirectory, new CnAn alyzer(), //用于支持分词的分析器 !in Creme ntal,In dexWriter.MaxFieldLe ngth.UNLIMITED);(2) 在搜索阶段，调用QUeryParSer.parse (queryText )来解析查询串时， QUeryParSer 会调用Analyzer 来拆分查询字符串，但是对于通配符等查询不会调用 Analyzer 。
An alyzer an alyzer = new CnAn alyzer();//支持中文的分词QUeryParSer ParSer = new QUeryParSer(VerSiO n.L UCENE_CURRENT, "title", an alyzer); 因为在索引和搜索阶段都调用了分词过程，索引和搜索的切分处理要尽量一致，所以 分词效果改变后需要重建索引。
为了测试LUCene 的切分效果，下面是直接调用 Analysis 的例子： Analyzer analyzer = new CnAnalyzer();// 创建一个中文分析器TokenStream ts = analyzer.tokenStream("myfield", new StringReader(" 待切分文本 "));//取得Token流SyStem.out.pri ntln ("toke n: "+ ts);}2、LUCene 中的Analyzer为了更好地搜索中文，通过下图来了解一下在LUCene中通过WhiteSPaCeTOkeniZer、WOrdDeIimiterFiIter、LOWerCaSeFiIter 处理英文字符串的流程：LeXCorP BFG-9000Whi te spar eToken i ZerLeXCorP BFG-9000Word Deliini terFilter C Cltenale WOrdii= 1rLOWerCaSeFiIlerIejtCCrP图2 LUCene处理英文字符串流程、查找词典算法词典格式可以是方便人工查看和编辑的文本文件格式，也可以是方便机器读入的二进制格式。
词典的最基本文本文件格式就是每行一个词。
在基于词典的中文分词方法中，词典匹配算法是基础。
一般词典规模都在几十万词以上，所以为了保证切分速度，需要选择一个好的查找词典算法。
1、标准Trie树一个数字搜索Trie树的一个节点只保留一个字符，如果一个单词比一个字符长，则包含第一个字符的节点有指针指向下一个字符的节点，依次类推。
这样组成一个层次结构的树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，依次类推，数字搜索树的最大高度是词典中最长单词的长度。
比女口：如下单词序列组成的词典(as at be by he in is it Of On Or to )会生成如下图所示的数字搜索树:图3数字搜索树数字搜索树的结构独立于生成树时单词进入的顺序，这里，Trie树的高度是2。
因为树的高度很小，在数字搜索Trie树种搜索一个单词的速度很快。
但是，这是以内存消耗为代价的，树中每个节点都需要很多内存。
假设每个词都是由26个小写英文字母中的一个组成的，这个节点中会有26个指针。
所以不太可能直接用这样的数字搜索树来存储中文这样的大字符集。
Trie树在实现上有一个树类( SearChTrie)和一个节点类(TrieNode)。
SearChTrie的主要方法有两个：(1)增加单词到搜索树，方法原型是：addWord ( String word )。
(2)从文本的指定位置开始匹配单词，方法原型是：matchLOng( String text, int OffSet )。
2、三叉Trie树在一个三叉搜索树(Ternary SearCh Trie)中，每一个节点包括一个字符，但和数字搜索树不同，三叉搜索树只有三个指针：一个指向左边的树；一个指向右边的树；还有一个向下，指向单词的下一个数据单元。
三叉搜索树是二叉搜索树和数字搜索树的混合体。
它有和数字搜索树差不多的速度但是和二叉搜索树一样只需要相对较少的内存空间。
树是否平衡取决于单词的读入顺序。
如果按顺序后的顺序插入，则生成方式最不平衡。
单词的读入顺序对于创建平衡的三叉搜索树很重要，但对于二叉搜索树就不太重要。
通过选择一个排序后数据单元集合的中间值，并把它作为开始节点，我们可以创建一个平衡的三叉树。
如下代码可以用来生成平衡的三叉树词典：*在调用此方法前，先把词典数组k排好序* @Param fp写入的平衡序的词典* @Param k排好序的词典数组* @Param OffSet 偏移量* @Param n 长度* @throws EXCePti On*/Void OUtPUtBaIa nced(BufferedWriter fp, ArrayLiStVStri ng> k, int offset, i nt n) {int m;if (n < 1) {return;}m = n >> 1; //m=n/ 2Stri ng item = k.get(m + offset);fp.write(item); //把词条写入到文件fp.write('∖ n');OUtPUtBaIa nced(fp, k, offset, m); 〃输出左半部分OUtPUtBaIanced(fp, k, OffSet+m+1, n-m-1); // 输出右半部分}再次以有序的数据单元(as at be by he in is it of on or to )为例。
首先把关键字"is乍为中间值并且构建一个包含字母“ i的根节点。
它的直接后继节点包含字母“ S并且可以存储任何与“is有关联的数据。
对于“i的左树，我们选择“be作为中间值并且创建一个包含字母“b”的节点，字母“ b的直接后继节点包含“e。
'该数据存储在“e节点。
对于“ i的右树，按照逻辑，选择“On作为中间值，并且创建“0节点以及它的直接后继节点“n”最终的三叉树如下图所示：图4三叉树垂直的虚线代表一个父节点下面的直接后继节点。
只有父节点和它的直接后继节点才能形成一个数据单元的关键字："i"和“S形成关键字“is,”但是“i和“b不能形成关键字，因为它们之间仅用一条斜线相连，不具有直接后继关系。
上图中带圈的节点为终止节点。
如果查找一个词以终止节点结束，则说明三叉树包含这个词。
以搜索单词“is为例，向下到相等的孩子节点“s”在两次比较后找到“is;”查找“aX”，执行三次比较达到首字符“a”然后经过两次比较到达第二个字符“X；'返回结果是“ax不在树中。
三、中文分词原理中文分词就是对中文断句，这样能消除文字的部分歧义。
除了基本的分词功能，为了消除歧义还可以进行更多的加工。
中文分词可以分成如下几个子任务：（1）分词：把输入的标题或者文本内容等分成词。
（2）词性标注（POS ：给分出来的词标注上名词或动词等词性。
词性标注可以部分消除词的歧义，例如行”作为量词和作为形容词表示的意思不一样。
（3）语义标注：把每个词标注上语义编码。
很多分词方法都借助词库。
词库的来源是语料库或者词典，例如人民日报语料库”或者《现代汉语大词典》。
中文分词有以下两类方法：（1）机械匹配的方法：例如正向最大长度匹配（ForWard MaXimUm MatCh ）的方法和逆向最大长度匹配（ReVerSe MaXimUm MatChing ）的方法。
（2）统计的方法：例如概率语言模型分词方法和最大熵的分词方法等。
正向最大长度品牌的分词方法实现起来很简单。
每次从词典中查找和待匹配串前缀最长匹配的词，如果找到匹配词，则把这个词作为切分词，待匹配串减去该词；如果词典中没有词与其匹配，则按单字切分。
例如：Trie树结构的词典中包括如下的词语：大大学大学生活动生活中中心心为了形成平衡的Trie树，把词先排序，结果为：中中心大大学大学生心活动生活按平衡方式生成的词典Trie树如下图所示，其中，粗黑显示的节点可以作为匹配终止节点：(⅛)图5三叉树输入大学生活动中心”首先匹配出大学生”然后匹配出活动”，最后匹配出中心” 切分过程如下表所示：已匹配上的结果待匹配串NULL大学生活动中心大学生活动中心大学生/活动中心大学生/活动/中心NULL在最大长度匹配的分词方法中，需要用到从指定字符串返回指定位置的最长匹配词的方法。
例如：当输入串是大学生活动中心”，则返回大学生”这个词，而不是返回大”或者大学”。
四、中文分词流程与结构中文分词总体流程与结构如下图所示：切分工具词査找模块切分算法J L I丿图6中文分词结构图简化版的中文分词切分过程说明如下：（1）生成全切分词图：根据基本词库对句子进行全切分，并且生成一个邻接链表表示的词图。
（2）计算最佳切分路径：在这个词图的基础上，运用动态规划算法生成切分最佳路径。