再谈拼音匹配系列目录：
第一节 即时匹配与语境
第二节 传统的字符串索引
第三节 拼音树（上）
第四节 拼音树（下）
第五节 杂项
所有内容的实现细节参见 PinIn
前言
上一节我们说到，通过在字典树中添加胶水层，我们可以令字典树执行拼音匹配的逻辑。但是字典树的内存占用本来就不理想，在添加胶水层之后就显得更加臃肿了。我们迫切需要一种办法来优化字典树的内存占用。除此之外，这一节还会补足所有上一节没有充分解释的内容。
密集节点
在前文中我们已经多次吐槽过树结构的存储效率。相反地，使用数组则在内存占用上具有绝对的优势。因此，我们可以使用一些小技巧，将数组混合进树结构中。这听起来十分黑暗，但是实际上效果拔群。我们知道，字典树相比起遍历搜索，在越密集的区域中能提供越好的加速效果，而在松散的区域，由于合并加速与跳转加速均不能生效，性能上则与遍历搜索类似。与此同时，松散区域的节点同样需要建立节点对象以及维护节点引用，因此占用了相当多的空间。由于松散区域主要出现在枝干的末尾部分，我们可以将所有末尾节点一并移除，转而将这些节点中的数据以数组的形式储存下来。
如上图所示，对于上一节给出的树结构，我们我们将节点“中”以下的部分移除，并将相关的信息作为数组存储在节点“中”内。这样一来，节点”中”就被转换成了一个“密集节点”。通过这种方式，配合前文提到的“切片技巧”，我们将传统树结构的效率从 50 字节每字符，提升到了 4 字节每字符。换句话说，当我们越广泛的使用密集节点，整个树结构的存储效率就越接近 4 字节每字符。
在使用密集节点时，我们不得不完全遍历密集节点中的所有词条来完成匹配。也就是说，我们在最大化存储效率的同时也完全放弃了合并加速与跳转加速。尽管如此，你也不必太过担心：我们在前文说到，跳转加速与合并加速主要出现在节点密集的区域，而对于疏松的枝干尾部，使用便利搜索并不会显著影响到搜索性能。假设每个末端的密集节点含有 k 个词条，对于总量确定的词条，拼音树的整体内存消耗可以认为是 a+b/k，而搜索耗时可以认为是 c+kd。对于不同的场景，k 的值也可以相应的取舍。目前的实现在对搜索速度造成小于 20% 的影响的同时，将内存消耗压缩到了原先的四分之一左右。
值得一提的是，这一结构并非拼音树限定。对于普通的字典树也同样适用。当应用于字典树时，它所提供的内存优化效果不变，但相比起搜索耗时较长的拼音树，使用密集节点对字典树所造成的性能开销可能更明显。我也没有查看是否有人使用过类似的结构，对于基于密集节点的字典树，我暂且称之为“部分字典树（partial trie）”。
外部加速
前文我们说到在拼音树中，执行一次搜索可能激活多个分支，并根据这一特性判断拼音树是一种 NFA。但是这一判断是不严谨的：在一次搜索中，任意时间的状态都包含两个变量：树中当前节点的位置和搜索串的偏移量。举个例子，当我们用“中国”匹配“zhongguo”，我们初始状态为 ("", 0)。在这一状态，我们可以跳转到 ("中", "2")（匹配“zh”） 和 ("中", "5")（匹配“zhong”）。每一次状态跳转都意味着两个变量的同时变化。从根本上而言，字典树搜索仍然是 NFA，但是涉及到的状态远比前文所述要更复杂。
我本不必要把这些状态关系说的这么细节，但是其中的偏移量和外部加速有着极为紧密的关系。这里给出了一个拼音树的例子：“核实”与“何时”。当我们搜索拼音“heshi”时，他一共需要匹配“核”，“实”，“何” 和“时”四个字符，尽管我们知道其中有两组同音字。对于任意的自动机，状态的转移必须是确定的。这一结论适用于拼音树搜索，也适用于拼音匹配（前文说到拼音匹配的逻辑同样基于自动机）。也就是说在偏移量为 0 时，对于拼音 “he2” 的匹配结果是确定的。因此，在对“核”与“何”进行匹配时，我们实际上可以复用一部分结果。
实现的逻辑也很简单：当我们基于任何偏移量对任何拼音执行匹配时，都将结果存储下来。如果已经有缓存的结果，就直接使用。这个逻辑听起来十分暴力，但是因为我们在此之前已经高度优化了相关的数据结构，所以开销非常有限。对于绝大部分的搜索场景，所有匹配结果的缓存一般可以控制在 100 KB 以下，几乎可以忽略不记。
基于这一逻辑，对图中所给的索引，我们可以将实际的匹配量缩减一半。考虑到拼音匹配的部分占据搜索耗时的绝大部分，在使用这一加速逻辑时，我们可以显著提升索引的搜索速度。由于这一加速逻辑是独立于树结构的，我们把它暂且称作外部加速。尽管外部加速对索引性能的影响不是决定性的，但是它一方面不需要任何预处理，另一方面可以和树结构的合并加速与跳转加速同时生效。因此，在大规模匹配的场景下，外部加速可以被轻松而广泛的使用。
设计思路
切片策略
这是我们在本系列的第二节中就使用过的策略：当我们需要在数据结构中广泛使用字符串时，可以将相关的字符以数组的形式存储下来，并在使用时直接以字符数组的索引（切片）来指代字符串。对于每一个字符，生成缓存都会消耗两字节，但是相比起节省的内存，这一点开销可以说是微不足道。在我们使用字符串时，每个引用需要 8 字节，每个字符串对象通常需要 20 字节以上。与此同时，每次生成子串还要消耗额外的时间和内存。当我们使用索引或切片来代替字符串时，这一部分的开销可以被大大缩减。
拆分策略
拆分策略是拼音树中广泛采用的思想，核心在于利用树结构的合并加速，将乘法关系转变为加法关系。这句话听起来可能有点抽象，我们不如再引用之前的例子：“中”和“国”各有四种拼法，那么根据排列组合，匹配的“中国”的字符串就共有 16 个。在树结构中，我们在执行时实际上先匹配了“中”的四个拼法，再在下一层匹配了“国”的四个拼法。这也就是将乘法关系转换为加法关系的直观案例。同样地，在子树法中，假如我们共有 400 个符号需要匹配，可以在搜索前先根据声母归纳合并。搜索时，我们先遍历匹配所有声母，再匹配该声母对应的若干字符。基于这个逻辑，我们就将遍历个 400 字符近似转化为了遍历 20 个声母 + 遍历 20 个字符。对于遍历搜索的场景，拆分策略是极为重要的优化手段。
层级策略
层级策略是在工程中极为常见的优化手段。类似的例子非常常见，比如 HashMap 在桶过多时转化为红黑树，比如 Java 中的锁从偏向锁到轻量锁到重量锁的升级。这一思路在实现中也被广泛应用：从密集节点（NDense）到切片节点（NSlice）到分支节点（NMap）到加速节点（NAcc），整个系统在松散区域使用存储效率更高的节点，而在密集区域使用性能更高的节点，从而把内存使用在更有意义的位置。类似地，对于节点中的绝大部分容器，初始使用基于数组遍历的实现，而在容量达到一定尺度时转换为基于哈希表的实现。这一策略并不能在理论上提供帮助，但在工程上对性能优化起着至关重要的作用。通过调整转换条件，我们可以在内存使用与搜索速度之间取得平衡。
小结
至此，拼音树的内容也就告一段落了。我平时很少做文献综述，但是再写这篇前特地大致阅览了谷歌上关于拼音匹配的相关结果。说句大言不惭的话，拼音树在我目前读到的论文或者博文中，在公开的算法中对大批量的文本匹配，有着相当出色的理论性能和灵活性。与此同时，不同于大部分论文的纯理论分析，本系列中提到的所有结构均在 PinIn 中提供了实现（TreeSearcher），并且被反复优化，而且绝大部分逻辑在 JECh 中已经被广泛使用和验证过了。
在实现后缀数的同时，拼音树也可以被用于前缀搜索。这里我稍微透露一些数据：对于 15MB 的文本，生成缓存时间小于两秒，执行一次搜索小于两毫秒，内存占用大约 70MB。我们知道输入法通常使用预分割来大幅简化搜索逻辑，但是如果我们基于拼音树开发一套输入法，它的性能相比起市面上的常见输入法也尚有胜算。另外，基于字典树的一个特性：搜索结果的顺序永远和加入索引的顺序一致，我们甚至可以进行词频排序。当然篇幅有限，我就不再细说了。
在后续章节中，对于其他的使用场景，我们会讨论拼音树以外的搜索结构。在此之后，我会对本系列中提出的搜索结构进行测试并给出结果。回见。
若非特殊注明，文章均为博主原创，通过 CC 4.0 BY License 授权转载
