尝试使用Unicode字符集

Question

我必须将输入字符串与一组前缀匹配。匹配应该是最大可能的匹配，因此如果同时存在abcd*和abcde*，则abcdef应该匹配abcde*。我正在为此使用特里。问题在于输入中的字符，并且前缀集中的字符可以是任何Unicode字符。因此，我们不可能在一个简单的Trie中拥有子数组（因为数组的大小将非常大，因此效率至少不够高）。使用map而不是array仍然效率低下。我应该如何解决呢？

Answer 1

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

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

考虑咖啡馆这个词

这可以表示为：
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é。

• 而且，如果您的尝试中有A并尝试匹配B怎么办？是同一个词，所以应该匹配吗？
  ？插入特里和进行匹配时，可能必须将字符串转换为相同的规范化形式。

• 还有其他问题。在德语中，双精度s通常表示为ß。ß和ss是否应匹配？

它继续。确定两个Unicode字符串是否相等本身并不是一个简单的问题。由您决定匹配的复杂程度，这取决于您的应用程序。