再谈拼音匹配系列目录：
第一节 即时匹配与语境
第二节 传统的字符串索引
第三节 拼音树（上）
第四节 拼音树（下）
第五节 杂项
所有内容的实现细节参见 PinIn
前言
在啰嗦了两节之后，我们终于介绍完了拼音树相关的内容。这一节作为整个系列的结束，我会把剩下的内容全部填完，这其中包括了拼音树以外的搜索结构，各类结构的性能测试，被废弃的设计还有潜在的开发方向。
其他搜索结构
对我而言，拼音树的性能毫无疑问已经让我足够满意了。但是他在各项数据上仍然算不上极致：对于索引构建，他要花费数倍于哈希表的时间；对于搜索，使用较短的搜索串时，相比起单纯将结果添加入哈希表，它的耗时要多出数倍，而使用较长的搜索串时，尽管结果通常更少，但是耗时约和短搜索串相当；对于内存消耗，它要花费数倍于字符串本身的容量。尽管对于拼音搜索而言，这样的结果已经是非常可观了，但是在极端情况下，使用仍然会受到限制。因此，这里还有更多的搜索结构可供使用。我这里并不将这些结构称为索引，因为他们的开发过于侧重工程上的优化，所以非常简单粗暴。但是你也知道，在极端场景下，理论模型往往受到各种条件的制约，工程上的优化则显得格外重要。
SimpleSearcher
正如它的名字，这个搜索结构简直就是简单到令人发指：我们将所有字符串存储起来，在需要使用时遍历搜索并返回结果。不过，既然我把它实现出来，自然有他存在的意义。首先，我们不需要建立各种复杂的树结构，所以它在构造上要比拼音树快出几倍。其次，他不需要占用内容用于缓存，所以他占用的内存也是小到极致。换句话说，他几乎是你所能用到的构建最快，占用内存最少的搜索结构。
除去这些显而易见的特征，他还利用了前文所述的“外部加速”和“切片策略”。这使得它在搜索时使用的时间大约只有遍历搜索的三分之一，而用于字符串存储的内存使用仅为通用容器的一半。而且，如前文所述，所有的搜索结构在执行搜索时返回的结果都会按插入时的顺序排列。这一特性对于一些涉及到优先级和排序的场景可能很有帮助。
CachedSearcher
前文中我们提到倒排索引会遭遇组合困境，所以建立完整的倒排索引并不现实。除去大量组合带来的内存开销，建立索引时遍历所有的搜索串同样极为耗时。假设我们使用遍历搜索串来建立缓存，并且只对 26 个小写字母建立 3 位的缓存，我们就需要执行将近两万次搜索。即使每次搜索耗时 1ms，完全建立缓存所需的时间将近 20 秒。作为参考，对于这个容量的数据，建立拼音树所需的时间大约是 100ms。
但是我们换个思路，不同于主动地遍历搜索串，我们只对搜索结果进行被动缓存：在第一次搜索时执行遍历搜索，接下来则使用缓存的结果。和相当多的缓存结构相同，我们不可能对结果无穷无尽地进行缓存，否则我们仍然会面对内存爆炸的困境。取而代之是，我们对缓存限定一个容量，超过容量则将最早使用的条目移除（LRU）。
如果我们想要索引对结果有更加灵活的反应，page flooding 带来的影响就难以避免。举个例子，假如我们的缓存容量只有十个条目，我们只需要连续搜索一大堆又长又罕见的词条，就可以用垃圾内容塞满缓存；如果我们用一些稳健的策略（例如LFU），结果就是缓存一旦填满，新的内容就很难进入，这对于容量很小的缓存而言同样不合适。根本而言，我们需要做的是从源头上堵截垃圾内容进入，这里的策略就是限制缓存搜索串的长度。
你可能有点疑惑，如果我们只缓存短串的结果，那么对于长串是不是就毫无帮助呢？当然不是，否则这个缓存结构的存在就毫无意义。对于文本匹配我们有这一结论：如果 a 是 b 的子串，b 是 c 的子串，则 a 是 c 的子串。对于拼音搜索，我对算法进行了轻度的魔改，使得它满足这一条件：如果 a 是 b 的前缀，拼音 b 匹配文本 c，则拼音 a 匹配文本 c。这是我在之前的文章里反复讨论过的思路：由于这个关系，只要 a 是 b 的前缀，则 b 的搜索结果的集合必然是 a 的结果的子集。这里我们暂且称之为“渐进特性”。基于这一特性，当我们搜索一个长串时，只需要寻找它前缀所对应结果的集合，再对这个集合内的条目（而不是总集）进行遍历搜索即可。
这一思路听起来不是特别诱人，但是对于三个字符长度的搜索串，匹配的结果很有可能只是总集的百分之一。也就是说对于所有更长的搜索串，比起对总集执行遍历搜索，这个缓存有可能将性能提升一百倍。这实际上借鉴了 q-gram 的思想：任意的字符可能是非常常见的，但是稍长一些的序列就会变得罕见得多。为了更高效地使用缓存，我们对缓存串的长度限制是非常严格的。尽管缓存容量是通过一些数学关系表达的，但是对于所有的前缀匹配和绝大部分的包含匹配，缓存总容量应该在 200 条目以下，每个条目被限制在 3 个字符以内。只有对相当长的文本进行包含搜索时，缓存容量才会有明显增长，并且允许 4 个字符长的缓存条目。整体而言，缓存的空间复杂度于拼音树一致，并且实际内存消耗被控制在略小于拼音树总容量的程度。同时，缓存容量也可以被手动修改以适用于不同的场景。
由于这个缓存的生成是完全被动的，一个显而易见的优势就是它构造极快。除此之外，当缓存内容预热完成，它的搜索速度也并不会落后拼音树太多。但是在预热不完全或者缓存不足时，由于它在执行搜索之前还要生成对应的缓存内容，搜索速度实际上要比 SimpleSeacher 更慢，和未加速的遍历搜索相近。从我的个人角度而言，如果对索引建立的耗时没有极端要求，由于缓存不确定造成的性能不稳定，我建议直接使用拼音树 TreeSearcher 作为通用的解决方案。值得一提的是，缓存的实现可以被轻松修改以解除条目的长度限制，这对于极少数条目极高频的查询可能有奇效，但是考虑到该场景更加极端，我们这里就不讨论了。
性能测试
测试使用两组数据。第一组提取自 Enigmatica 模组包，可以近似模拟极端条件下的 Minecraft 环境，文本文件 902KB，共 37k 词条，424k 字符。第二组提取自腾讯 AILab 的汉语短语 语料库，文本文件 14.4MB，共 1M 词条，4.81M 字符。测试在 i7-7700HQ 上进行，仅使用单核运算。对于每组文本，我们分别测量了用于前缀匹配与用于包含匹配的两组时间数据。对于全文匹配，性能几乎等同于前缀匹配，我这里就不单独列出了。
小数据集 + 包含匹配
| 匹配逻辑 | 构建耗时 | 预热耗时 | 搜索耗时 | 内存使用 |
|---|---|---|---|---|
| TreeSearcher | 210ms | N/A | 0.19ms | 9.50MB |
| SimpleSearcher | 27ms | N/A | 9.1ms | 1.84MB |
| CachedSearcher | 28ms | 16ms | 0.55ms | 见备注 |
| 遍历拼音匹配 | N/A | N/A | 23ms | N/A |
| 遍历 contains | N/A | N/A | 0.53ms | N/A |
小数据集 + 前缀匹配
| 匹配逻辑 | 构建耗时 | 预热耗时 | 搜索耗时 | 内存使用 |
|---|---|---|---|---|
| TreeSearcher | 62.5ms | N/A | 0.083ms | 2.80MB |
| SimpleSearcher | 30ms | N/A | 2.4ms | 1.84MB |
| CachedSearcher | 28ms | 2.8ms | 0.10ms | 见备注 |
| 遍历拼音匹配 | N/A | N/A | 8.8ms | N/A |
| 遍历 startsWith | N/A | N/A | 0.53ms | N/A |
大数据集 + 包含匹配
| 匹配逻辑 | 构建耗时 | 预热耗时 | 搜索耗时 | 内存使用 |
|---|---|---|---|---|
| TreeSearcher | 5000ms | N/A | 0.66ms | 159MB |
| SimpleSearcher | 120ms | N/A | 200ms | 22.8MB |
| CachedSearcher | 150ms | 260ms | 6.5ms | 见备注 |
| 遍历拼音匹配 | N/A | N/A | 430ms | N/A |
| 遍历 contains | N/A | N/A | 12ms | N/A |
大数据集 + 前缀匹配
| 匹配逻辑 | 构建耗时 | 预热耗时 | 搜索耗时 | 内存使用 |
|---|---|---|---|---|
| TreeSearcher | 1300ms | N/A | 0.42ms | 70.4MB |
| SimpleSearcher | 120ms | N/A | 48ms | 22.8MB |
| CachedSearcher | 150ms | 64ms | 1.8ms | 见备注 |
| 遍历拼音匹配 | N/A | N/A | 120ms | N/A |
| 遍历 startsWith | N/A | N/A | 10ms | N/A |
备注：
CachedSearcher的内存占用在不同的场景下会有明显波动，在绝大部分情况下小于TreeSearcher的用量。
需要注意的是，所有搜索结构的内存使用值均包含所有文本，一般情况下使用者无需额外消耗内存进行存储。对于小数据集，使用 ArrayList<String> 存储文本约占用 2.6MB 内存，而大数据集约占用 56MB 内存。
尽管我们在讨论拼音索引的性能时，常常拿它与输入法相比，但是从本质上而言，其中涉及到的概念是完全不同的：
- 相当多的输入法使用数据库进行搜索，或者使用其他方法将缓存内容存储在硬盘上，从而减少内存消耗。因此，有些输入法有可能占用上百 MB 的硬盘空间。
- 输入法执行的是全文匹配，也就是说输入“zhong”时，不可能联想到“中国”。这种匹配模式更加苛刻，因此可以有更多方法来优化执行速度。
- 对于相当多数输入法，短语的发音在词库中是确定的，也就是说输入“huoping”并不会联想到“和平”。这在很大程度上解决了多音字的混合问题，而在运行时我们几乎无法完全正确地确定多音字的发音。
- 几乎所有输入法都依赖于搜索串的切分，这对于简化单词搜索内容极为有利。对于支持中英混输的输入法，很有可能在切分时预先参考了英文词库（例如匹配公共子串）。而在我们的场景下，我们无法将词条中的英文部分单独切分出来，因而分词会变得极为繁琐。
- 输入法可以对词库进行相当复杂的预处理，并将结果持久化，而我们的场景要求所有操作在运行时在内存中完成。一个显而易见的例子就是 Rime 可以使用相当大的静态词库，但是当用户（动态）词库容量稍大时就有可能带来性能问题。
由于以上的各类原因，我们所面对的性能压力实际上远高于输入法。对于输入法而言，拼音匹配的逻辑只能算得上是基石，而核心则是各种语言模型。而这个项目则是完全侧重于极端场景下的性能。通过测试数据你也能看出来，在各项性能指标上可以压缩的空间已经是非常小了。
反思与计划
如果你很熟悉 JECh 这个项目的话，你可能知道截至目前索引结构已经迭代到第三个大版本了。第一个版本继承自 JEI，使用缓存加实时搜索。这个版本和目前的 CachedSearcher 很接近，但是对缓存中搜索串的长度不加限制。在绝大部分场景下，它的性能都勉强可用，但是在预热阶段或者执行高频搜索时会产生卡顿。第二个版本使用了一个巨大的缓存，将任何搜索过的搜索串和索引串组合产生的结果完全缓存下来。这个结构是完全失败的：它不仅占用相当多的内存，同时在搜索性能上也并没有明显的提升。每次搜索时，我们都要在缓存中遍历查找所有索引串对应的结果，而这一操作并不比遍历匹配快太多。我曾经因此吐槽过 HashMap 的性能，但是这一问题的瓶颈实际上不在 HashMap，而在缓存设计本身。不过话又说回来，目前该项目中广泛使用的外部加速机制和这一设计非常接近，但是它不仅有着更加谨慎的性能优化，而且从设计上在泛用性和利用率上具有决定性的优势。
相比起之前的方案，目前基于拼音树的实现在整体上更加平衡且高效，唯一令人担心的部分就是相比起不需要建立的搜索结构，它在缓存构建上耗时稍多。在之前版本的 MC 中，缓存构造是在游戏启动前执行的，相比起动辄十几二十分钟的启动时间，这几秒钟完全可以忽略不计。而在新版本的 MC 中，相关的操作被移动到了加载世界的环节。尽管在绝大部分情况下建立索引只需要 5 秒以下的时间，我们仍然需要在性能问题上保持关注。
说到索引构造的性能问题，这个项目中使用的后缀数实现实际上是非常粗糙的。在构造环节，不同于大部分性能优化过的实现，他实际上仅仅是将一个字符串的所有后缀顺序加入字典树。我原先认为这应该就是所谓的 $n^2$ 暴力构造，但是测试下来它的性能近似在 $n$ 和 $nlogn$ 之间。得益于压缩树的切片节点，在插入条目时，一旦我们在树结构中移动到顶端，就可以直接插入一个切片节点来指代剩下的所有内容。也就是说，插入条目的性能主要受到树层数的限制。这显然要慢于各类线性构造的算法，但是大部分线性构造算法需要维护 suffix link，分离节点和边，这需要占用更多内存，而且也不适用于密集节点，所以应用这些算法可能会使内存占用翻倍甚至增加数倍。考虑到这些因素，目前在这方面并没有改动的计划。
小结
说到这里，我们这个系列就告一段落了。对于拼音环境下的字串查找问题，我们给出了实时匹配的实现，基于后缀数的拼音树的实现，以及两种在实时匹配上加速的实现。尽管在性能上还存在一些优化的空间，我想它应该可以应对大部分场景了。如果整个系统有什么新的改动，我也会以附言的形式进行更新。那么，我们下次见吧，
若非特殊注明，文章均为博主原创，通过 CC 4.0 BY License 授权转载
