string - 英语以外语言的尝试的局限性和替代方案？

Question

trie 数据结构通常是存储英语字符串的好方法。它的工作原理是构建一棵树，其中每条边都标有一个字母，并且树中标记节点的路径拼出数据结构中的一个单词。

这个数据结构在英语中运行良好，因为英语字母表中“只有”26个字母(一个“合理的”分支因子)，这些字符具有连续的 ASCII 值(因此子指针可以存储在由每个 child 使用的字母的索引)，并且有很多具有共同前缀的英语单词(因此结构中有很多冗余)。

我的母语是英语，对其他语言和字母表的了解有限，但似乎其中许多属性在其他语言中并不成立。例如，我知道法语、西类牙语、德语和匈牙利语经常使用重音字符，这些字符不与 Unicode 空间中的其余字母连续存储。希伯来语和阿拉伯语有元音标记，通常标在每个字母的上方或下方。中文使用语标系统，韩文韩文字符由组合在一起的三个较小字符组成。

尝试对于以这些语言和字母存储的数据仍然有效吗？要对此类数据使用尝试，需要进行哪些更改(如果有)？是否有任何数据结构适用于那些特别适合它们的语言和字母表中的字符串，但在英语中却没有用或高效？

Answer 1

我发现这种尝试对于西欧语言以及西里尔字母和许多其他字母语言都很有效。想想看，我唯一遇到困难的语言是中文、日文和其他表意书写系统。对于这些，特里树是没有用的。

英文字符的连续 Unicode 值实际上并不是一个巨大的好处。尽管它建议简单的节点实现:

CharNode
    char
    array[26] of CharNode

该结构并不是特别有用。它可以使事情变得更快，但内存成本相当高。即使在特里树的第二层，该数组也非常稀疏。到了第四层、第五层的时候，这里就几乎全是死角了。我曾经对此进行过分析。我会环顾四周，看看是否还有这些数字。

我发现节点中的可变长度数组几乎与按频率排序的项目一样快。除了特里树的第二层或第三层之外，我要查找的字符几乎总是位于该数组中的第一或第二位置。而且节省的空间也相当大。我没有每个节点 26 个引用(在我的实现中为 104 个字节)，而是采用一字节计数，然后每个引用 5 个字节。因此，只要特定节点的子节点数少于 21 个(这是大多数情况)，我就节省了空间。有一个小的运行时间损失，但在我的应用程序中还不足以产生影响。

这是我必须对我的 trie 结构进行的唯一修改，以使其支持我正在使用的所有字母语言。正如我所说，我主要使用西欧语言，对于那些语言来说它效果很好。我知道它确实适用于希伯来语和阿拉伯语，但我不知道它的效果如何。它满足了我们的目的，但是否能让母语人士满意还不得而知。

我构建的 trie 足以满足我们的目的，对于任何字符适合 Unicode 基本多语言平面的语言。使用代理对时有一点奇怪，但我们几乎忽略了这些。基本上，我们只是将代理对视为两个角色，然后就这样了。

您必须决定是否要将重音字符视为单独的字符，或者是否要映射它们。例如，考虑一下法语单词“garçon”，有些人会将其拼写为“garcon”，要么是因为他们不知道更好，要么他们不知道如何拼写字符“ç”。根据您使用 trie 的用途，您可能会发现将重音字符转换为非重音字符非常有用。但我认为这更多的是一个输入清理问题，而不是一个特里问题。

这是我相当冗长的说法，标准特里树应该适用于任何字母语言，而不需要任何特定于语言的修改。我没有看到任何明显的方法来使用 trie 作为语标语言。我对韩文一无所知，所以我不能说 trie 在那里是否有用。