algorithm - 如果我们知道输入是按字母顺序排列的，我们如何优化 trie 的创建？

Question

我正在实现一个带有标准插入机制的前缀树。如果我们知道我们将得到一个按字母顺序排列的单词列表，是否有任何方法可以更改插入以跳过几个步骤？我正在用 Java 编写代码，尽管我不是在寻找任何特定语言的代码。我考虑过将每个单词的节点添加到队列中，然后向后跳转直到我们到达下一个单词的前缀，但这可能会绕过前缀树的整个点!

对这样的事情有什么想法吗？我发现很难想出一个有用的实现，除非输入是很多非常相似的词 ("aaaaaaaaaab", "aaaaaaaaaac", "aaaaaaaaaad", ...) 或某物。但即便如此，对前缀进行字符串比较的成本也可能与仅正常使用前缀树的成本相似。

Answer 1

您无法避免查看用于构建树的输入字符串中的所有字符。如果有办法做到这一点，那么我可以让你的算法不正确。特别是，假设有一个单词 w 而您没有查看它的其中一个字符(例如，第 k 个字符)。然后，当您的算法运行并尝试将单词放置在 trie 中的某个位置时，它必须能够在不知道所有字符的情况下放置它。因此，如果我将单词的第 k 个字符更改为其他字符，您的算法会将其放在与之前完全相同的位置，这是不正确的，因为单词中的一个字符将不正确。

由于构建 trie 的普通算法所花费的时间与输入中的字符数成正比，如果不采取一些疯狂的技巧(例如并行化构建代码或将字符打包为机器字)，您将无法渐近地超越它并用您的 Hammer of Bit Hackery 击打它们。

但是，您可能会获得常数因子加速。由于缓存性能的原因，在链接结构中跟踪大量指针可能会很慢，因此您可以通过最小化必须跟踪的指针数量来加快算法速度。您可以做的一件事是维护您插入的最后一个字符串的末尾位置，以及一个节点列表(最好是动态数组)，该列表跟踪路径回到根。要插入新字符，您可以执行以下操作:

1. 找到与您插入的最后一个字符串相匹配的字符串的最长前缀。
2. 跳转到数组中标记将带您去向的指针。
3. 像往常一样向下追踪路径的其余部分，将您追踪到的所有节点添加到数组中并覆盖之前的指针。

这样，如果您插入大量具有合理长度的公共(public)前缀的单词，则可以避免通过结构的共享部分执行大量指针追回。如果你有很多具有相同前缀的词，这可以想象地给你带来性能提升。它并没有比以前更好(事实上，使用了更多的内存)，但是不遵循指针所节省的费用可能会增加。我还没有对此进行测试，但它似乎可行。

希望这对您有所帮助!