前言
本章节为原书的
2.4.4首字散列其余二分的字典树
2.4.5前缀树的妙用
主要作为叙述了解即可
提示：以下是本篇文章正文内容，下面案例可供参考
一、首字散列其余二分
首先需要了解散列函数，其实一般也就说的是哈希函数，这个大家就不陌生了。将某个字符输出为对应的散列值，也就说一串整数
例如：
$ python3 >>> hash('池')-hash('江') 2668313623312284569
这是Python的散列，采用Unicode，显然结果 很不友好
再例如：
System.out.println(new Character('池').hashcode() - new Character('江').hashcode()) >输出结果 1
java的散列值明显友好一些，采用utf-16（池江二字已知字符相邻）
java的散列函数输出是[0,65535]，用来索引子节点很合适
做法如下：
1.创建一个65535大小的数组
2.将子节点按对应的字符整型值作为下标放入数组中
这样做，每次访问只需要访问对应的下标即可，考虑到汉语中二字词最多，所以结合二分的策略，诞生了本节的字典树，仅在根节点实施散列，其余二分。举例如下图（引用hankcs的原图）：
引用上节的效率测评代码之后，首字散列其余二分的算法比二叉树相比而言，最长匹配中文分词速度又得到了一些提升，特别是在逆向和双向，优势更明显。
二、前缀树的妙用
上一节用字典树代替了TreeMap,利用containsKey做分词，速度加快了近一倍，但并没有达到字典树的潜力。
利用字典树的概念，我们可以做的更快，发挥前缀的作用
这种性质如何加速诃典分词呢？在扫描“自然语言处理”这句话的时候，朴素实现会依次查询“自”“自然”“自然语”“自然语言”是否在可典中。但事实上，如果“自然”这条路径不存在于前缀树中，则可以断定一切以“自然”开头的词语都不可能存在。也就是说，在状态转移失败时（由根节点向“自”、由“自”向“自然”的转移)，我们就可以提前终止对以“自”开头的扫描，从而节省相当多的时间。
全切分核心代码如下（示例）：
public void parseText(String text, AhoCorasickDoubleArrayTrie.IHit<V> processor) { int length = text.length(); int begin = 0; BaseNode<V> state = this; for (int i = begin; i < length; ++i) { state = state.transition(text.charAt(i)); if (state != null) { V value = state.getValue(); if (value != null) { processor.hit(begin, i + 1, value); } } else { i = begin; ++begin; state = this; } } }
最长匹配核心代码如下（示例）：
public void parseLongestText(String text, AhoCorasickDoubleArrayTrie.IHit<V> processor) { int length = text.length(); for (int i = 0; i < length; ++i) { BaseNode<V> state = transition(text.charAt(i)); if (state != null) { int to = i + 1; int end = to; V value = state.getValue(); for (; to < length; ++to) { state = state.transition(text.charAt(to)); if (state == null) break; if (state.getValue() != null) { value = state.getValue(); end = to + 1; } } if (value != null) { processor.hit(i, end, value); i = end - 1; } } } }
其实我们不必深究代码怎么去写，但一定要去了解每段代码是什么原理，为什么这样写，可能说起来有些矛盾，懂得都懂。
测试
利用状态转移的技巧，前缀树的作用就发挥出来了，同样进行上节的测试，速度差异就明显了，同样用原书展示：
over！
