Aho-Corasick FSA的三叉树与以map为转换表的trie

Question

使用三叉树的FSA和将转换表实现为搜索树(例如std::map)的trie有什么不同？对于读取一个符号，两者似乎都具有O(log )复杂度和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)要小。

Answer 2

考虑到阿霍-科拉西克是如何被描绘的，

​

​

这是我的Node：

public class AhoCorasickNode
{

    // This part works as a Trie

    public char literal; // c

    public String stack; // abc

    public AhoCorasickNode previous; // { ab }

    public AhoCorasickNode[] next; // { abca }, { abcb }, { abcc }, ..

    //-----------------------------

    // This part is used when solving

    boolean inDictionary;

    public AhoCorasickNode suffix;

    public AhoCorasickNode dictionarySuffix;

}

来源：

• Wikipedia: Aho-Corasick