尝试 Unicode 字符集
Trie for Unicode character set
我必须将输入字符串与一组前缀进行匹配。匹配应该是最好的，这样如果同时存在 abcd* 和 abcde*，那么 abcdef 应该匹配 abcde*。我为此使用 Trie。问题是输入中的字符和前缀集中的字符可以是任何 Unicode 字符。因此，我们在一个简单的 trie 中拥有的子数组将是不可能的（至少不会足够有效，因为数组大小将非常大）。使用 map 而不是 array 仍然是低效的。我应该如何解决这个问题？
要构建 trie，您可以将 Unicode 字符串编码为 UTF-8，然后使用编码后的字节序列构建 trie。或者您可以使用代码点，并在您的节点中使用哈希映射。您必须对您的应用程序进行基准测试以确定哪种方法最有效。
但难题是如何判断两个字符串何时匹配。
考虑单词 café
这可以表示为：
A = [U+0063 U+0061 U+0066 U+0065 U+0301]（以 e 和 组合重音 结尾）
但也作为
B = [U+0063 U+0061 U+0066 U+00E9]（以é结尾，，组合形式）
所以：
字符串是否应该匹配前缀 cafe（无重音）？ A 以该前缀开头，B 不是。但是 A 和 B 要么都匹配前缀，要么不匹配，因为它们代表同一个词 café.
如果您的 trie 中有 A，并且您正在尝试匹配 B 怎么办？同一个词，应该匹配吗？
→ 您可能必须在插入 trie 和匹配时将字符串转换为相同的 normalized form。
还有其他问题。在德语中，双 s 通常写作 ß。 ß 和 ss 应该匹配还是不匹配？
它还在继续。 判断两个 Unicode 字符串是否相等本身就是一个不平凡的问题。匹配的复杂程度由您决定，这取决于您的应用。
我必须将输入字符串与一组前缀进行匹配。匹配应该是最好的，这样如果同时存在 abcd* 和 abcde*，那么 abcdef 应该匹配 abcde*。我为此使用 Trie。问题是输入中的字符和前缀集中的字符可以是任何 Unicode 字符。因此，我们在一个简单的 trie 中拥有的子数组将是不可能的（至少不会足够有效，因为数组大小将非常大）。使用 map 而不是 array 仍然是低效的。我应该如何解决这个问题？
要构建 trie，您可以将 Unicode 字符串编码为 UTF-8，然后使用编码后的字节序列构建 trie。或者您可以使用代码点，并在您的节点中使用哈希映射。您必须对您的应用程序进行基准测试以确定哪种方法最有效。
但难题是如何判断两个字符串何时匹配。
考虑单词 café
这可以表示为：
A = [U+0063 U+0061 U+0066 U+0065 U+0301]（以 e 和 组合重音 结尾）
但也作为
B = [U+0063 U+0061 U+0066 U+00E9]（以é结尾，，组合形式）
所以：
字符串是否应该匹配前缀 cafe（无重音）？ A 以该前缀开头，B 不是。但是 A 和 B 要么都匹配前缀，要么不匹配，因为它们代表同一个词 café.
如果您的 trie 中有 A，并且您正在尝试匹配 B 怎么办？同一个词，应该匹配吗？
→ 您可能必须在插入 trie 和匹配时将字符串转换为相同的 normalized form。还有其他问题。在德语中，双 s 通常写作 ß。 ß 和 ss 应该匹配还是不匹配？
它还在继续。 判断两个 Unicode 字符串是否相等本身就是一个不平凡的问题。匹配的复杂程度由您决定，这取决于您的应用。