java - Tries 适用于没有字母表的语言吗？

Question

我正在尝试找出最有效的方法来实现与使用 Trie 存储英文单词类似的效率，但我想用没有字母表的语言(例如中文)存储单词。例如，我希望能够加载一个单词列表并拥有一个应用程序，当用户输入时，它会根据已经输入的字符实时给出建议。关于如何实现这一点的任何建议，就像我使用 Tries 一样，我将拥有大量的父节点，因为有数千个唯一字符。有什么既定的方法可以实现我上面描述的目标吗？

Answer 1

术语绕行:“字母表”一词通常用于指代书写系统中的符号(如各种欧洲语言的符号)，其中每个符号大致对应一个音素(声音)。还有一些书写系统，其中符号对应于音节、语素或整个单词；这些语言的符号比字母表多得多，具有不同的技术名称:音节符号、音节符号、语标符号等，但区分并不精确。

然而，在计算理论中，通常使用“字母表”一词来描述任何有限的符号集合，无论该集合有多大或多小。任何字母表——或有限的符号集——都可以从大小至少为两倍的较小字母表转码为固定长度的序列，长度的变化与字母表的大小成对数关系。因此，假设仅使用二进制表示通常很方便:即来自字母表 {0, 1} 的表示。

trie 将适用于任何字母大小；没有要求 trie 的字母表是来自人类书写系统的“字母表”，也没有禁止它是更大的符号集合，尽管使用大字母表的简单实现可能会非常浪费空间。特别是，没有什么能阻止您将原始书写字符重新编码为更小的字母表，为每个字符使用多个 trie 级别。例如，如果原始字符串以 UTF-8 表示，那么您可以使用单独的字节(并且您可能想要区分前导节点，其中字母表大小为 178，但只有 99 对应于“字母”，以及内部节点，其中字母大小为 64)。或者，您可以将 Unicode 代码点拆分为三个或四个位序列，每个位序列的大小都在可管理范围内。

您可以通过压缩只有一个子节点的连续节点来优化尝试；这可能对上述方案有效。二进制字母表上的紧凑型 trie 称为 Patricia trie，它也可能值得一看。

另一种处理稀疏 trie 节点的常见解决方案是为子节点使用某种关联结构，而不是数组。在 ternary search trees ， children 只是简单地保存在一个排序列表中，这样就可以通过二进制搜索找到正确的 child ，时间对字母大小的对数，这对于给定的字母表是恒定的。 (时间实际上是 child 数量的对数，这可能比字母表的大小小得多。)

另一种适用于中型字母表的解决方案是保留当前子项的位 vector 以及子项的排序 vector ；现代 CPU 的指令可以快速对一个字中的集合位数求和，从而可以高效地使用位 vector 来查找 vector 中子项的索引。

另一种可能的解决方案是使用一个哈希表，其条目由一个由父节点的 id 和子节点的前导字符组成的二元组作为关键字。这种数据结构易于维护且节省空间，但引用的局部性很差。 (一个缺点是需要做额外的工作来构建父节点的子节点列表:例如，通过显式链接子节点。)