1

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

如果我们不需要自动机在运行时更改，那么最好的选择不是使用（符号，状态）转换对的排序向量以及二进制搜索吗？

4

2 回答 2

3

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

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

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

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

于 2013-04-04T19:42:03.637 回答
0

鉴于 Aho-Corasick 的说明方式，

阿霍-科拉西克

这是我的节点：

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;

}

资源：

于 2013-04-04T20:59:58.313 回答