Trie三叉树分词实现

最长匹配中文词典分词算法

中文的语句与英文不同，英文单词之间均有空格隔开，英文的语句没有分词的概念。而中文则不同，单词之间没有空格隔开。在处理中文语句时需要对中文语句进行分词。
目前多数的中文分词的算法采用了，最长匹配词典的算法。词典是将众多的中文词组存放在一个文件内。如下的词典的格式：

大
大学
大学生
中
中心
活
活动

此时我想要对中文语句：String keyStr = "大学生活动中心" 进行分词。
采用最长匹配词典的算法，从keyStr大第一个字符开始，匹配到词典表中的大；
keyStr继续下一个字符学与词典匹配，可以得出这个也可以在词典中匹配到，匹配到了大学这个单词。
此时思考是否已经匹配结束了呢，还要继续向下匹配，因为最长匹配词典算法是匹配不到为止。
向下一个匹配就是生这个字符了。至此中文分词算法就结束了。不禁会问，如此简单，其实就是这么简单。
后续的工作均在此工作基础上进行优化，如keyStr如何快速匹配到词典中的词组，中文词典的大量的词组如何存储。

优化中文最长匹配词典算法工作

中文词组词典查找与存储

为了快速能够查找到中文词典的单词需要设计一个好的数据结构用于存放中文词典中词组，好的标准是查询速度快而且内存占用又少。
词典表中的中文词组，每个词组由一个到多个的字符组成，每个词组存放在链表中，如下图。

将量表合并成以大为根节点的树，如下图

每一个相同的开头字符中文词组形成一棵的树，能够有效的减少内存开销，该树就是标准Tire树。

解决了词典中中文词组存放的问题，那么需要解决快速查找到一个中文词组。比如查询大学生，在词典表中如何快速能够查询到。根据Tire树的性质，每个根节点是一个字符，通过一个词典表中的中文词组生成标准Tire树，每课树的根节点均是不同且是字符。
在ASCII码中，每一个字符都是一个编号，他们是有大小的，很容易想到我们可以使用二叉搜索树来解决查询标准Tire树的问题。如下图 C大于B，存放在右子树，A小于B存放在左子树。

上面的两者性质一个是存放中文词组，另一个是快速查找。如果将其二者性质合并在一起会是一个很好的解决方案。为了方便显示，使用英文字符来表示，效果与中文词组的一个字符是一样的。

三叉Tire树中，每一个节点包含一个字符，但是和标准Tire树不同，三叉Tire树的节点中有三个位置相关的属性，一个指向左边的树（比该父节点大的节点），一个指向右边的树（比该父节点小的节点），还有一个是向下的节点（上图绿色箭头指向的节点），表示当前中文词组该字符的下一个字符。
例如：b指向下节点是点e，在e节点中没有向下的节点，所以表示的单词为be。

上图中绿色的箭头线代表一个父节点的下面的直接后继节点，只有父节点和他的直接后继节点才能形成一个数据单元的关键字（一个单词或者一个中文词组）；i和s形成关键字is，但是i和b不能形成关键字，因为他们之间仅有一条斜线相连，不具有直接后继的关系。
上图的中带有阴影的圆圈，是表示终止的节点，如果查找以一个词以终止节点结束，则说明三叉树包含这个词。
从根节点开始查找单词，以搜索单词is为例，向下到相等的孩子节点s，在两次比较后找到is。查找ax时，执行三次比较到达的首字符a，然后经过两次比较到达第二个字符x，返回结果是ax不在树中。

代码实现 中文分词代码