在英语以外的语言中尝试的局限性和替代方案？
trie数据结构通常是存储英语字符串的好方法。它的工作原理是构建一棵树，其中每条边都标有字母，树中标记节点的路径拼写出数据结构中的一个单词。
这种数据结构在英语中运行良好，因为在英语字母表中“只有”26个字母(一个“合理的”分支因子)，这些字符具有连续的ASCII值(因此，子指针可以存储在一个数组中，该数组以每个子指针使用的字母的索引为关键字)，并且有许多具有公共前缀的英语单词(因此结构中有很多冗余)。
我是一个以英语为母语的人，对其他语言和字母的了解有限，但似乎这些特性中的许多在其他语言中是不存在的。例如，我知道法语、西班牙语、德语和匈牙利语经常使用重音字符，这些字符不会与Unicode空间中的其余字母一起连续存储。希伯来语和阿拉伯语的元音标记通常表示在每个字母的上方或下方。中文使用标志符号系统，韩语韩语字符由组合在一起的较小字符的三元组组成。
对于以这些语言和字母表存储的数据，尝试是否仍然有效？如果要对这类数据使用tries，需要做哪些更改？有没有什么数据结构可以很好地处理那些语言和字母表中的字符串，这些字符串特别适合它们，但在英语中却没有什么用处或效率？
回答 1
Stack Overflow用户
发布于 2014-12-05 06:07:36
我发现尝试对西欧语言、西里尔语和许多其他字母语言都很有效。想想看，我唯一遇到麻烦的语言是中文、日语和其他标志书写系统。对于这些人来说，trie是无用的。
英文字符的顺序Unicode值并不是一个很大的好处。尽管它建议使用简单的节点实现：
CharNode
char
array[26] of CharNode这种结构并不是特别有帮助。它可以使事情变得更快，但需要相当高的内存成本。即使在trie的第二级，该数组也是非常稀疏的。当你达到第四或第五层的时候，它几乎都是死角。我一度对此进行了分析。我会四处看看，看看我还有没有号码。
我发现在节点中有一个可变长度的数组，并按频率对项进行排序，这几乎同样快。在trie的第二或第三级之外，我要查找的字符几乎总是位于该数组的第一或第二个位置。而且节省的空间也相当大。而不是每个节点26个引用(在我的实现中是104个字节)，我有一个字节计数，然后每个引用5个字节。因此，只要特定节点的子节点少于21个(大多数情况下是这样)，我就节省了空间。有一个小的运行时惩罚，但在我的应用程序中还不够重要。
这是我对trie结构所做的唯一修改，以使其支持我正在使用的所有字母语言。正如我所说的，我主要是在使用西欧语言，对于那些语言来说，它工作得很好。我知道它确实适用于希伯来语和阿拉伯语，但我不知道它的效果如何。它符合我们的目的，但它是否会满足以英语为母语的人还不得而知。
我构建的trie对于任何字符符合Unicode Basic多语言平面的语言都能很好地工作。在使用代理对时有一点奇怪，但我们几乎忽略了这些。基本上，我们只是将代理项对视为两个字符，并将其放在那里。
您必须决定是要将重音字符视为单独的字符，还是要映射它们。例如，考虑法语单词"garçon“，有些人会将其拼写为"garcon”，要么是因为他们不知道更好的方法，要么是因为他们不知道如何将字符“ç”拼写成“ç”。根据您使用trie的用途，您可能会发现将重音字符转换为非重音字符是很有用的。但我认为这更多的是输入清理问题，而不是trie问题。
这就是我长篇大论的说法，标准的trie应该适用于任何字母语言，而不需要任何特定于语言的修改。我看不出有什么明显的方法可以将trie用于标识语言。我对韩语一无所知，所以我不能说trie在那里是否有用。
https://stackoverflow.com/questions/27304455
复制相似问题