Unicode字符集的java Trie

Question

我必须将输入字符串与一组前缀进行匹配。匹配应该是最好的，这样如果同时存在abcd*和abcde*，那么abcdef应该匹配abcde*。我用Trie来做这个。问题在于输入和前缀集中的字符可以是任何Unicode字符。因此，我们在一个简单的trie中拥有的子数组是不可能的（至少不会有足够的效率，因为数组的大小将非常大）。使用map而不是数组仍然是低效的。我应该如何着手解决这个问题

Answer 1

要构造trie，可以将Unicode字符串编码为UTF-8，然后使用编码的字节序列构造trie。或者您可以使用代码点，并在节点中使用哈希映射。您必须对应用程序进行基准测试，以确定哪种方法最有效

但难题是如何确定两个字符串何时匹配

考虑<强>咖啡> <强>

这可以表示为：
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字符串是否相等本身就是一个非常重要的问题。由您决定匹配的复杂程度，这取决于您的应用程序