英语以外的其他语言的尝试的限制和替代方法？

Question

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

这个数据结构在英语中运行良好，因为英文字母中只有26个字母（“合理的”分支因子），这些字符具有连续的ASCII值（因此子指针可以存储在数组键入的通过每个孩子使用的字母的索引），并且有许多英文单词具有共同的前缀（所以在结构中有很多冗余）。

我是一位母语为英语的人，其他语言和字母的知识水平有限，但其中许多属性似乎并不适用于其他语言。例如，我知道法语，西班牙语，德语和匈牙利语经常使用不与Unicode空间中的其余字母连续存储的重音字符。希伯来语和阿拉伯语的元音标记通常在每个字母的上方或下方标出。中文使用的是一个语标系统，韩文韩文字符由三个小字符组合而成。

对于以这些语言和字母存储的数据，Do尝试仍然有效吗？对这类数据使用try有必要进行哪些更改（如果有的话）？是否有任何数据结构对那些特别适合他们的语言和字母的字符串起作用，但在英语中不会有用或有效？

Answer 1

作为@ JimMischel答案的附录，我想提出一个问题，即在其他语言中，通常有多种等效的方法来编写相同的东西。 Vietnamese（基于拉丁/英文脚本）是一个特别好的例子，其中带有两种口音的字母很常见。例如，Ặ（U + 1EB6）也可以用Ă+ dot，Ạ+

Unicode normalization可以通过将字符串转换为标准规范的顺序来解决此问题。有4种不同的变体，NFC，NFKC，NFD和NFKD。在这里我不会详细讨论，但前两个是“组合形式”，它倾向于缩短字符串，将基本字符与它的口音分组，而最后两个是“分解形式”，相反。

Hangul是一个有趣的例子：它是一个字母表，虽然音节的所有字母都被拼在一起。单个字母和音节块都以Unicode存在。规范化可以解决这个问题，尽管不同音节的数量非常大。使用NFC/NFKC对于一个trie可能没有用处，但在这种情况下，使用NFD/NFKD将音节分解为组成字母将会起作用。

其他一些无关的点考虑：

• 除了已经长大了加尔松/ GARCON点，你有棚/科特/科特迪瓦/的Côté的问题，这是完全不同的法语单词。同样，希伯来语和阿拉伯语的元音标记通常不是强制性的，偶尔会造成歧义。
• 英文字母与英文相比可以获得较大的尺寸，大致是其两倍。

---

1. 他们严格称为abugidas，在元音被写为变音符号/口音，但这种区别通常可以从编程的角度来看忽略。

Answer 2

我发现这种尝试适用于西欧语言，以及西里尔文和其他许多字母语言。想想看，我遇到的唯一语言是中文，日文和其他字迹书写系统。而对于那些人来说，这个线索毫无用处。

英文字符的顺序Unicode值并不是真正的好处。虽然它暗示了简单的节点实现：

CharNode 
    char 
    array[26] of CharNode 

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

我发现它几乎与节点中的可变长度数组一样快，项目按频率排序。除了特里的第二或第三级别之外，我所寻找的角色几乎总是处于阵列的第一或第二位置。节省的空间相当大。每个节点（在我的实现中有104个字节）不是每个节点26个引用，而是每个引用有一个字节的计数，然后是五个字节。因此，只要特定节点（大部分时间）的孩子少于21个，我就节省了空间。运行时间很短，但在我的应用程序中不够重要。

这是我必须对我的trie结构进行的唯一修改，以使其支持所有我正在使用的字母语言。正如我所说的，我主要用西欧语言工作，对于那些工作很好的人。我知道它确实与希伯来语和阿拉伯语一起工作，但我不知道以及它的工作原理。它符合我们的目的，但它是否会满足母语人士是未知的。

为了我们的目的，使用任何适合Unicode基本多语言平面的语言，我建立的trie工作得非常好。与代理对一起工作时有点不可思议，但我们几乎忽视了这些。基本上，我们只是将代理对作为两个角色来处理，然后让它继续。

您必须决定是否要将重音字符视为单独的字符，还是要映射它们。例如，考虑一些人会拼写“garcon”的法语单词“garçon”，要么是因为他们不了解任何更好的内容，或者他们不知道如何制作角色“ç”。根据您使用的trie的不同，您可能会发现将重音字符转换为不重音的等效字符很有用。但我想这更像是一个输入清理问题，而不是一个线程问题。

这是我相当冗长的说法，即标准的trie应该适用于任何字母语言，无需进行任何语言特定的修改。我没有看到任何显而易见的方法来使用字典编码语言。我对韩国的韩文一无所知，所以我不能说一个线索是否会在那里有用。