我在这学期学习算法,并阅读了关于Aho-Corasick 字符串匹配算法和Ukkonen构建后缀树的算法。
我阅读了它们,但无法理解这两者的主要基本区别,除了失败链接检查前缀和后缀链接检查后缀。
这两种算法有什么区别?
我在这学期学习算法,并阅读了关于Aho-Corasick 字符串匹配算法和Ukkonen构建后缀树的算法。
我阅读了它们,但无法理解这两者的主要基本区别,除了失败链接检查前缀和后缀链接检查后缀。
这两种算法有什么区别?
我认为你对后缀链接和失效链接的理解是不正确的。在这两种情况下,后缀/失败链接都是从 trie/后缀树中的一个节点到 trie/后缀树中的另一个节点的指针,具有以下属性:如果原始节点表示字符串 x,则字符串 y 由后缀/失败链接指向的节点是 y 是字符串 x 的最长可能后缀的节点。
两种算法之间的主要区别在于算法产生的内容,而不是后缀/失败链接的含义。Aho-Corasick 生成了一个带有额外转换信息注释的 trie,它可以尽可能快地找到字符串集合的所有实例。产生的故障链接用于算法的构建和模式匹配步骤。Ukkonen 的算法生成后缀树,仅在构造期间使用后缀链接,而不是在树上的大多数查询期间使用。
希望这可以帮助!
不同之处在于后缀/字典链接就像指向孩子的父母的指针。失败链接来自广度优先搜索。两个链接都是后缀。