Unicode字符集的Trie

Question

我需要将输入字符串与一组前缀进行匹配。匹配应该是最佳的，例如如果有abcd*和abcde*，那么abcdef应该与abcde*匹配。我使用Trie来实现这个功能。问题是输入字符串和前缀集合中的字符可以是任何Unicode字符。因此，我们在简单的Trie中使用的子节点数组将不可行（至少不够高效，因为数组大小会非常大）。即使使用map而不是数组仍然是低效的。我该如何解决这个问题？

- ptntialunrlsd

---

我不确定我是否正确理解了问题；使用Unicode作为字符集会使问题变得更加困难吗？ - Codor

支持Unicode（而不是ASCII）的问题是否在于子数组所需的存储空间？ - Simon

对于一个简单的 Trie，我们使用该节点的字符来索引下一个节点的引用。 - ptntialunrlsd

@Simon，是的。没错。 - ptntialunrlsd

@wero，现有的也可以。我没有什么具体的任务。 - ptntialunrlsd

Answer 1

构建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é。

• 如果您在字典树中有A，并且要匹配B，那么怎么办？这是相同的单词，所以它应该匹配吗？
  → 当插入字典树和进行匹配时，您可能需要将字符串转换为相同的规范形式。

• 还有其他问题。在德语中，双s通常写作ß。 ß和ss是否应该匹配？

还有其他问题。决定两个Unicode字符串是否相等本身就是一个非平凡的问题。您需要决定匹配的复杂程度，这取决于您的应用程序。

- roeland