algorithm - 三元树 vs trie， map 作为 Aho-Corasick FSA 的转换表

Question

使用三叉树的 FSA 和将转换表实现为搜索树(例如 std::map)的 trie 有什么区别？看起来两者都具有读取一个符号的 O(log k) 复杂度和 O(S) 内存复杂度，其中 k 是字母表大小，S 是所有接受的输入字符串的长度总和。

如果我们不需要自动机在运行时更改，最好的选择是使用(符号、状态)转换对的排序向量和二分查找吗？

Answer 1

三元搜索树 (TST) 与在每个节点上使用二叉搜索树实现的 Trie 之间没有真正的区别。实际上，您可以将后者视为前者的(低效)实现； TST的优点是易于优化，空间开销合理。

经典的 Trie 使用由符号索引的转换向量直接查找决策节点。这是 O(1)时间，但对空间的要求是巨大的。尽管如此，还是有一些优化存储的方法。此外，还存在混合解决方案，其中 Trie 结构仅用于树顶部的宽决策节点；一旦候选者的数量减少到一定程度，就可以使用快速扫描或哈希表来找到合适的候选者。

以简单的方式使用(符号，状态)转换的排序向量需要 O(log T)每次转换的时间，其中 T是转换的总数；本质上是所有输入字符串的总大小。给定目标的总时间将为 |target|*log(T) .

相比之下，TST 要求不超过 O(log S)每次转换的时间，其中 S是字母表的大小；这比 T 小得多.此外，整个目标字符串的查找总数受输入字符串数量的限制，因此整个查找的总和小于|target|*log(S)。 .