本文讨论了利用后缀树改进匹配时间的近似子串匹配技术。每个答案都针对不同的算法。
- 近似子字符串匹配尝试在允许不匹配
P的字符串中查找子字符串（模式） 。Tk - 要了解如何创建后缀树，请单击此处。然而，一些算法需要额外的预处理。
我邀请人们添加新算法（即使它不完整）并改进答案。
问问题
5154 次
2 回答
3
你做得很好。我不熟悉该算法，但今天阅读了该论文。你写的一切都是正确的。你是对的，解释的某些部分假设了很多。
你的问题
1.就后缀树或输入字符串而言，输出的大小指的是什么？最后的输出阶段列出了所有在 T 中出现的 Key(r)，对于所有标记为输出的状态 r。
输出由 T 中 P 的最大 k 距离匹配组成。特别是，您将获得每个匹配的最终索引和长度。所以很明显这也是 O(n) （记住 big-O 是一个上限），但可能更小。这是对不可能在少于 O(p) 的时间内生成 p 个匹配的事实的认可。其余时间限制仅涉及模式长度和可行前缀的数量，两者都可以任意小，因此输出大小可以占主导地位。考虑 k=0 并且输入是 'a' 以模式 'a' 重复 n 次。
2.看算法C，定义函数dp（第四页）；我不明白我代表什么索引。它没有初始化，也没有增加。
你是对的。这是一个错误。循环索引应该是i. 怎么样j？这是与动态程序中正在处理的输入字符对应的列的索引。它实际上应该是一个输入参数。
让我们退后一步。第 6 页上的示例表是使用前面给出的公式 (1-4) 从左到右逐列计算的。这些表明只需要 D 和 L 的前一列即可获得下一列。函数dp只是j从j-1. D列j和L列分别称为d和l。j-1D 和 L 列是d'和l'，函数输入参数。
我建议您通过动态程序工作，直到您完全理解它为止。该算法旨在避免重复的列计算。这里的“重复”意味着“在本质部分具有相同的值”，因为这才是最重要的。无关紧要的部分不会影响答案。
未压缩的特里树只是以明显方式扩展的压缩特里树，每个字符都有一条边。除了“深度”的概念，这并不重要。在压缩树中，depth(s) 只是字符串的长度——他称之为 Key(s)——需要从根节点 s 获取。
算法 A
算法 A 只是一个聪明的缓存方案。
他的所有定理和引理都表明：1）我们只需要担心列的基本部分，以及 2）列 j 的基本部分完全由可行前缀 Q_j 确定。这是以 j 结尾的输入的最长后缀，它匹配模式的前缀（在编辑距离 k 内）。换句话说，Q_j 是迄今为止所考虑的输入结束时 k 编辑匹配的最大开始。
有了这个，这里是算法 A 的伪代码。
Let r = root of (uncompressed) suffix trie
Set r's cached d,l with formulas at end page 7 (0'th dp table columns)
// Invariant: r contains cached d,l
for each character t_j from input text T in sequence
Let s = g(r, t_j) // make the go-to transition from r on t_j
if visited(s)
r = s
while no cached d,l on node r
r = f(r) // traverse suffix edge
end while
else
Use cached d',l' on r to find new columns (d,l) = dp(d',l')
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s
while depth(r) != |Q_j|
mark r visited
r = f(r) // traverse suffix edge
end while
mark r visited
set cached d,l on node r
end if
end for
为简单起见，我省略了输出步骤。
什么是遍历后缀边？当我们从节点 r 执行此操作时，其中 Key(r) = aX（前导 a，后跟一些字符串 X），我们将前往具有 Key X 的节点。结果：我们将对应于可行前缀 Q_h 的每一列存储在带有前缀 Q_h 的输入后缀的 trie 节点。函数 f(s) = r 是后缀转移函数。
对于它的价值，后缀树的维基百科图片很好地展示了这一点。例如，如果从“NA”的节点我们沿着后缀边，我们到达“A”的节点，然后从那里到“”。我们总是在剪掉主角。因此，如果我们用 Key(s) 标记状态 s，我们就有 f("NA") = "A" 和 f("A") = ""。（我不知道他为什么不在论文中这样标记状态。这会简化许多解释。）
现在这非常酷，因为我们只计算每个可行前缀的一列。但它仍然很昂贵，因为我们正在检查每个字符并可能遍历每个字符的后缀边。
算法 B
算法 B 的目的是通过跳过输入来加快速度，只触及那些可能产生新列的字符，即那些与以前看不见的模式前缀匹配的输入结尾的字符。
正如您所怀疑的，算法的关键是loc函数。粗略地说，这将告诉下一个“可能”输入字符在哪里。该算法有点像 A* 搜索。我们维护了一个最小堆（它必须有一个删除操作）对应于论文中的集合 S_i。（他称其为字典，但这不是该术语的非常传统的用法。）如上所述，最小堆包含潜在的“下一个状态”，键控于下一个“可能字符”的位置。处理一个字符会产生新的条目。我们继续前进，直到堆为空。
你是绝对正确的，他在这里变得粗略。定理和引理并没有联系在一起来对正确性进行论证。他认为你会重做他的工作。我对这种挥手并不完全相信。但是那里似乎确实有足够的东西来“解码”他想到的算法。
另一个核心概念是集合 S_i，特别是未消除的子集。我们将这些未消除的状态保留在最小堆 H 中。
你说得对，这个符号掩盖了 S_i 的意图。当我们从左到右处理输入并到达位置 i 时，我们已经积累了迄今为止看到的一组可行前缀。每次找到一个新的时，都会计算一个新的 dp 列。在作者的符号中，这些前缀将是所有 h<=i 的 Q_h 或更正式的 { Q_h | h <= 我 }。这些中的每一个都有从根到唯一节点的路径。集合 S_i 包含我们通过沿着 trie 中的 go-to 边缘从所有这些节点多走一步获得的所有状态。这产生的结果与遍历整个文本查找 Q_h 的每次出现和下一个字符 a，然后将对应于 Q_h a 的状态添加到 S_i 中的结果相同，但它更快。
我们如何选择合适的候选人？选择输入中位置 i 之后的下一个。这就是 loc(s) 的用武之地。状态 s 的 loc 值正是我上面所说的：输入中从 i 开始的位置，接下来出现与该状态相关的可行前缀。
重要的一点是，我们不想仅仅将新找到的（通过从 H 中提取 min loc 值）“下一个”可行前缀分配为 Q_{i+1}（dp 列 i+1 的可行前缀）和继续下一个字符 (i+2)。这是我们必须设置阶段尽可能向前跳到最后一个字符 k（具有 dp 列 k）的地方，例如 Q_k = Q_{i+1}。我们按照算法 A 中的后缀边向前跳过。只是这次我们通过更改 H 来记录我们的步骤以供将来使用：删除元素，这与从 S_i 中删除元素相同，并修改 loc 值。
函数 loc(s) 的定义是赤裸裸的，他从未说过如何计算它。还没有提到的是 loc(s) 也是 i 的函数，当前正在处理的输入位置（他从论文前面部分的 j 跳到这里的 i 因为当前输入位置是无用的。）影响是 loc (s)随着输入处理的进行而变化。
事实证明，适用于消除状态的定义部分“刚刚发生”，因为状态在从 H 中移除时被标记为消除。所以对于这种情况，我们只需要检查一个标记。
另一种情况 - 未消除的状态 - 要求我们在输入中向前搜索，以寻找文本中未被其他字符串覆盖的下一个出现。这种覆盖的概念是为了确保我们总是只处理“最长可能”的可行前缀。必须忽略较短的，以避免输出最大匹配以外的输出。现在，向前搜索听起来很昂贵，但很高兴我们已经构建了一个后缀树，它允许我们在 O(|Key(s)|) 时间内完成。必须仔细注释 trie 以返回相关的输入位置并避免出现被覆盖的 Key(s)，但这不会太难。他从来没有提到当搜索失败时该怎么做。这里 loc(s) = \infty，即被淘汰，应该从 H.
也许算法中最棘手的部分是更新 H 以处理我们为一个可行的前缀添加一个新状态 s 的情况，该前缀覆盖了已经在 H 中的某些 w 的 Key(w)。这意味着我们必须手术更新 (loc H 中的 (w) => w) 元素。事实证明，后缀特里树再次通过其后缀边缘有效地支持这一点。
考虑到所有这些，让我们尝试伪代码。
H = { (0 => root) } // we use (loc => state) for min heap elements
until H is empty
(j => s_j) = H.delete_min // remove the min loc mapping from
(d, l) = dp(d', l', j) where (d',l') are cached at paraent(s_j)
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s_j
while depth(r) > |Q_j|
mark r eliminated
H.delete (_ => r) // loc value doesn't matter
end while
set cached d,l on node r
// Add all the "next states" reachable from r by go-tos
for all s = g(r, a) for some character a
unless s.eliminated?
H.insert (loc(s) => s) // here is where we use the trie to find loc
// Update H elements that might be newly covered
w = f(s) // suffix transition
while w != null
unless w.eliminated?
H.increase_key(loc(w) => w) // using explanation in Lemma 9.
w = f(w) // suffix transition
end unless
end while
end unless
end for
end until
为了简单起见，我再次省略了输出。我不会说这是正确的，但它在球场上。一件事是他提到我们应该只处理不在“访问”之前的节点的 Q_j，但我不明白在这种情况下“访问”是什么意思。我认为算法A定义的访问状态不会发生，因为它们已从H中删除。这是一个谜......
引理 9 中的increase_key操作在没有证据的情况下仓促描述。他声称最小操作在 O(log |alphabet|) 时间内是可能的，这给我们留下了很多想象空间。
怪癖的数量让我想知道这是否不是论文的最终草稿。它也是 Springer 出版物，如果完全一样，这个在线副本可能会违反版权限制。可能值得在图书馆中查找或为最终版本付费，以查看在最终审查期间是否消除了一些粗糙的边缘。
这是我所能得到的。如果您有具体问题，我会尽力澄清。
于 2013-10-27T00:35:56.750 回答
3
这是开始这个线程的原始问题。
Esko Ukkonen 教授发表了一篇论文：Approximate string-matching over suffix trees。他讨论了具有不同匹配时间的 3 种不同算法：
- 算法 A：
O(mq + n) - 算法 B：
O(mq log(q) + size of the output) - 算法 C：
O(m^2q + size of the output)
其中m是子串n的长度，是搜索串的长度，q是编辑距离。
我一直在尝试理解算法 B，但在执行这些步骤时遇到了麻烦。有没有人有这个算法的经验？一个示例或伪算法将不胜感激。
尤其是：
size of the output后缀树或输入字符串指的是什么？最后的输出阶段列出所有出现的Key(r)in ，用于标记为输出T的所有状态。r- 查看算法 C，定义了函数dp（第四页）；我不明白索引
i代表什么。它没有初始化，也没有增加。
这就是我所相信的（我会被纠正）：
- 在第七页，我们介绍了后缀树的概念；一个状态实际上是后缀树中的一个节点：让
root表示初始状态。 g(a, c) = b其中a和b是树中的节点，并且c是树中的字符或子字符串。所以这代表了一个过渡；从 开始a，沿着由 表示的边c，我们移动到节点b。这称为首选转换。所以对于下面的后缀树，g(root, 'ccb') = red node
Key(a) = edge sequence其中a表示树中的一个节点。例如，Key(red node) = 'ccb'。所以g(root, Key(red node)) = red node。Keys(Subset of node S) = { Key(node) | node ∈ S}a节点和b,有一个后缀函数f(a) = b：对于所有（或者可能存在）a≠root，存在一个字符c、一个子字符串x和一个b节点g(root, cx) = a和g(root, x) = b。我认为这意味着，对于上面的后缀树示例，f(pink node) = green nodewherec = 'a'和x = 'bccb'.- 有一个映射
H包含来自后缀树的一个节点和一个值对。该值由loc(w); 我仍然不确定如何评估该功能。该字典包含尚未消除的节点。 extract-min(H)(node, loc(w))是指从中获得对中值最小的条目H。
该算法的症结似乎与如何loc(w)评估有关。我在这里使用组合答案构建了我的后缀树；但是，这些算法适用于后缀树（未压缩的后缀树）。因此，需要以不同的方式维护和处理诸如深度之类的概念。在后缀树中，深度代表后缀长度；在后缀树中，深度仅表示树中的节点深度。
于 2013-10-26T10:04:41.693 回答