使用后缀树进行近似子串匹配
本文讨论利用后缀树来缩短匹配时间的近似子串匹配技术。 每个答案都是针对不同的算法。
T查找允许多达k不匹配的子字符串（模式） P 。 我邀请人们添加新算法（即使它不完整）并改进答案。
你做得很好。 我不熟悉算法，但今天已阅读论文。 你所写的一切都是正确的。 你说得对，有些部分的解释假设很多。
你的问题
1.根据后缀树或输入字符串，输出大小是指什么？ 最终输出阶段列出T中所有出现的Key（r），对于标记为输出的所有状态r。
输出由T中P的最大k距离匹配组成。特别是你会得到每个匹配的最终索引和长度。 很显然，这也是O（n）（记住大O是一个上界），但可能更小。 这是一个事实，即不可能在小于O（p）的时间内生成p个匹配。 剩下的时间限制只涉及模式长度和可行前缀的数量，它们都可以是任意小的，所以输出大小可以占主导地位。 考虑k = 0并且输入是'a'，并且模式'a'重复n次。
查看算法C，函数dp被定义（第四页）; 我不明白我代表什么指数。 它没有被初始化，也没有增加。
你是对的。 这是一个错误。 循环索引应该是i 。 j呢？ 这是与在动态程序中处理的输入字符对应的列的索引。 它应该是一个输入参数。
让我们退后一步。 第6页上的示例表是使用前面给出的方程（1-4）从左到右，逐列计算的。 这些表明只有前面的D和L列才能得到下一个。 函数dp只是实现了从j-1计算列j的这种想法。 D和L的j列分别称为d和l 。 列j-1 D和L是函数输入参数d'和l' 。
我建议你通过动态程序工作，直到你理解得很好。 该算法全部关于避免重复列计算。 这里的“重复”意味着“在关键部分具有相同的价值”，因为这是重要的。 无关紧要的部分不会影响答案。
未压缩的trie只是一个以明显方式展开的压缩扩展，每个字符都有一个边缘。 除了“深度”的概念，这是不重要的。 在压缩树中，深度（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
为了简单起见，我省略了输出步骤。
什么是遍历后缀的边缘？ 当我们从Key（r）= aX（前导a后面跟着一个字符串X）的节点r完成这个操作时，我们要用关键字X去到节点。结果是：我们将每个对应于可行前缀Q_h的列存储在输入前缀为Q_h的后缀的trie节点。 函数f（s）= r是后缀转换函数。
值得一提的是，维基百科的后缀树图片显示了这一点。 例如，如果从用于“NA”的节点跟随后缀边缘，则我们到达节点“A”并从那里到“”。 我们总是切断主角。 所以如果我们用键标记状态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 <= i}。 其中每一个都有一个从根到唯一节点的路径。 集合S_i由我们通过沿着树状结构中的前往边沿从所有这些节点再走一步而获得的所有状态组成。 这产生了与遍历整个文本寻找每个Q_h和下一个字符a相同的结果，然后将对应于Q_h a的状态添加到S_i中，但速度更快。 S_i状态的密钥恰好是下一个可行前缀Q_ {i + 1}的正确候选。
我们如何选择合适的人选？ 选择位于输入中位置i后面的那个。 这是loc（s）进来的地方。状态s的loc值就是我刚才所说的：从i开始的输入中的位置，其中与该状态相关的可行前缀接着发生。
重要的一点是，我们不希望只将新发现的（通过从H中拉出最小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也是i的函数，当前输入位置正在处理中（他在本文前面的部分从j跳到i，因此对于当前输入位置是无益的）。影响是loc （s）随着输入处理的进行而改变。
事实证明，适用于消除状态的定义的一部分“恰好发生”，因为状态在移除形式H时标记为消除。因此，对于这种情况，我们只需要检查标记。
另一种情况 - 未消除状态 - 要求我们在输入中向前搜索，以查找文本中未被其他字符串覆盖的下一个事件。 覆盖的这个概念是为了确保我们总是只处理“尽可能长”的可行前缀。 为避免输出除最大匹配以外的其他值，必须忽略较短的那些。 现在，向前搜索听起来很昂贵，但很高兴我们已经构建了一个后缀trie，这允许我们在O（| Key（s）|）时间内完成此操作。 必须对注册表进行仔细注释以返回相关输入位置并避免密钥出现，但这不会太难。 当搜索失败时他从不提及该做什么。 这里loc（s）= infty，即它被删除，应该从H中删除。
也许算法最头发的部分是更新H来处理这样的情况：我们为一个可行的前缀添加一个新的状态，该前缀覆盖了已经在H中的一些w的密钥（w）。这意味着我们必须通过手术更新（loc （w）=> w）元素。事实证明，后缀trie仍然有效地支持它的后缀边缘。
有了这些，我们来试试伪代码。
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（日志|时间）时代留下很多想象力。
怪癖的数量让我怀疑这是不是该论文的最终草案。 它也是Springer的出版物，如果它完全一样，这个在线副本可能会违反版权限制。 这可能值得在图书馆看看，或者为最终版本付费，看看最终评论期间是否有一些粗糙的边缘被淘汰。
这是尽我所能。 如果您有具体问题，我会尽力澄清。
这是开始这个主题的原始问题。
Esko Ukkonen教授发表了一篇论文：对后缀树进行近似字符串匹配。 他讨论了3种不同匹配时间的算法：
O(mq + n) O(mq log(q) + size of the output) O(m^2q + size of the output) 其中m是子串的长度， n是搜索字符串的长度， q是编辑距离。
我一直在试图理解算法B，但是我无法遵循这些步骤。 有没有人有这种算法的经验？ 一个例子或伪算法将不胜感激。
尤其是：
size of the output指什么？ 最终输出阶段列出T中所有出现的Key(r) ，对于标记为输出的所有状态r 。 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 node ，其中c = 'a'和x = 'bccb' 。 H ，它包含来自后缀树和值对的节点。 该值由loc(w) ; 我仍然不确定如何评估功能。 该字典包含尚未消除的节点。 extract-min(H)表示获得来自H的对(node, loc(w))具有最小值的条目。 算法的症结似乎与loc(w)的评估方式有关。 我已经使用这里的组合答案构造了我的后缀树; 但是，算法在后缀特里结构（未压缩后缀树）上工作。 因此，像深度这样的概念需要进行不同的维护和处理。 在后缀trie中，深度将代表后缀长度; 在后缀树中，深度将简单地表示树中的节点深度。