algorithm - 使用后缀树近似子字符串匹配

Question

本文讨论了利用suffix tree的近似子串匹配技术。以改善匹配时间。每个答案都针对不同的算法。

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

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

Answer 1

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

Esko Ukkonen 教授发表了 paper :后缀树上的近似字符串匹配。他讨论了 3 种具有不同匹配时间的不同算法:

1. 算法 A:O(mq + n)
2. 算法 B:O(mq log(q) + 输出大小)
3. 算法 C:O(m^2q + 输出大小)

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

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

特别是:

1. 就后缀树或输入字符串而言，输出大小指的是什么？ 最终输出阶段列出了 T 中所有出现 Key(r) 的情况，以及标记为输出的所有状态 r。>
2. 看看算法C，定义了函数dp(第四页)；我不明白索引 i 代表什么。它没有初始化并且似乎没有增加。

这是我所相信的(我愿意纠正):

1. 在第七页，我们介绍了后缀树概念；状态实际上是后缀树中的一个节点:让root表示初始状态。
2. g(a, c) = b 其中 a 和 b 是树中的节点，c 是树中的字符或子字符串。所以这代表了一个转变；从a开始，沿着c表示的边，我们移动到节点b。这称为转到转换。因此，对于下面的后缀树，g(root, 'ccb') = red node
3. Key(a) = 边序列，其中 a 表示树中的节点。例如，Key(红色节点)= 'ccb'。所以g(root, Key(红色节点)) = 红色节点。
4. Keys(节点 S 的子集) = { Key(节点) |节点 ∈ S}
5. 节点 a 和 b 有后缀函数，f( a) = b:对于所有(或者可能存在)a ≠ root，存在字符c、子字符串x和节点b 使得 g(root, cx) = a 且 g(root, x) = b。我认为，对于上面的后缀树示例，f(粉红色节点)= 绿色节点，其中 c = 'a' 和 x = 'bccb'。
6. 有一个映射H，其中包含后缀树中的一个节点和一个值对。该值由 loc(w) 给出；我仍然不确定如何评估该功能。该字典包含尚未消除的节点。
7. extract-min(H)指的是获取对中具有最小值的条目(node, loc(w)) 来自 H。

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