使用后缀树进行近似子串匹配

Question

本文讨论了使用后缀树来改善匹配时间的近似子串匹配技术.每个答案都针对不同的算法.

1. 近似子字符串匹配尝试在字符串中查找子字符串(模式)P,以T允许最多k不匹配.
2. 要了解如何创建后缀树,请单击此处.但是,某些算法需要额外的预处理.

我邀请人们添加新算法(即使它不完整)并改进答案.

Answer 1

这是启动该线程的原始问题。

\n\n

Esko Ukkonen教授发表论文： Approximate string-matching over suffix trees。他讨论了 3 种具有不同匹配时间的不同算法：

\n\n

\n
1. 算法A：O(mq + n)
\n
2. 算法B：O(mq log(q) + size of the output)
\n
3. 算法C：O(m^2q + size of the output)
\n

\n\n

其中m是子字符串的长度，n是搜索字符串的长度，并且q是编辑距离。

\n\n

我一直在尝试理解算法 B，但在执行这些步骤时遇到了困难。有人有这个算法的经验吗？示例或伪算法将不胜感激。

\n\n

尤其：

\n\n

\n
1. size of the output后缀树或输入字符串指的是什么？最终输出阶段列出所有状态中所有出现的Key(r)inTr为输出的状态。
\n
2. 查看算法 C，定义了函数dp（第四页）；我不明白什么索引i代表什么。它没有初始化并且似乎没有增加。
\n

\n\n

这是我所相信的（我愿意纠正）：

\n\n

\n
1. 在第七页，我们介绍了后缀树的概念；状态实际上是后缀树中的一个节点：让root表示初始状态。
\n
2. g(a, c) = b其中a和b是树中的节点，c是树中的字符或子字符串。所以这代表了一个转变；从 开始a，沿着 代表的边c，我们移动到节点b。这称为首选转换。所以对于下面的后缀树，g(root, \'ccb\') = red node \n
\n
3. Key(a) = edge sequence其中a代表树中的一个节点。例如，Key(red node) = \'ccb\'。所以g(root, Key(red node)) = red node。
\n
4. Keys(Subset of node S) = { Key(node) | node \xe2\x88\x88 S}
\n
5. a节点和b,存在后缀函数f(a) = b：对于所有（或者可能存在）a\xe2\x89\xa0 root，存在一个字符c、一个子串x和一个节点，b使得g(root, cx) = a和g(root, x) = b。我认为，对于上面的后缀树示例，这意味着f(pink node) = green nodewherec = \'a\'和x = \'bccb\'。
\n
6. 有一个映射H，其中包含后缀树中的一个节点和一个值对。该值由下式给出loc(w)；我仍然不确定如何评估该功能。该字典包含尚未消除的节点。
\n
7. extract-min(H)(node, loc(w))指的是从中获得该对中具有最小值的条目H。
\n

\n\n

该算法的关键似乎与如何loc(w)评估有关。我已经使用此处的组合答案构建了后缀树；然而，这些算法适用于后缀特里树（未压缩的后缀树）。因此，像深度这样的概念需要以不同的方式维护和处理。在后缀特里树中，深度代表后缀长度；在后缀树中，深度仅表示树中的节点深度。

\n