题 Ukkonen的后缀树算法用简单的英语


此时我觉得有点厚。我花了好几天时间试图完全围绕后缀树构造,但由于我没有数学背景,因为他们开始过度使用数学符号系统时,许多解释都没有。最接近我发现的一个很好的解释是 使用后缀树快速搜索字符串,但他掩盖了各种观点,算法的某些方面仍然不清楚。

这个在Stack Overflow上对这个算法的逐步解释对于我以外的许多其他人来说都是非常宝贵的,我敢肯定。

作为参考,这里是Ukkonen关于算法的论文: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

到目前为止,我的基本理解:

  • 我需要迭代给定字符串T的每个前缀P.
  • 我需要遍历前缀P中的每个后缀S并将其添加到树中
  • 要向树中添加后缀S,我需要遍历S中的每个字符,迭代包括沿着现有分支向下走,该分支以S中相同的字符集C开头,并且可能将边缘拆分为后代节点在后缀中找到不同的字符,或者如果没有匹配的边缘则向下走。当没有找到匹配的边缘向下走C时,为C创建一个新的叶边。

基本算法似乎是O(n2),正如我们在大多数解释中所指出的那样,当我们需要遍历所有前缀时,我们需要逐步遍历每个前缀的每个后缀。由于他使用的后缀指针技术,Ukkonen的算法显然是独一无二的,尽管我认为  是我无法理解的。

我也很难理解:

  • 确切地分配,使用和更改“活动点”的时间和方式
  • 算法的标准化方面发生了什么
  • 为什么我看到的实现需要“修复”他们正在使用的边界变量

这是完成的 C# 源代码。它不仅工作正常,而且支持自动标准化,并提供更好看的输出文本图。源代码和示例输出位于:

https://gist.github.com/2373868


更新2017-11-04

多年以后,我发现了后缀树的一个新用途,并已实现了该算法 JavaScript的。要点如下。它应该没有错误。将其转储到js文件中, npm install chalk 从相同的位置,然后运行node.js看到一些彩色输出。在同一个Gist中有一个精简版本,没有任何调试代码。

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


951
2018-02-26 11:30


起源


你看过给出的描述了吗? 丹古斯菲尔德的书?我觉得这很有帮助。 - jogojapan
要点没有指定许可证 - 我可以更改您的代码并在MIT下重新发布(显然有归属)吗? - Yurik
是的,去寻找你的生活。考虑它是公共领域。正如本页另一个答案所述,无论如何都有一个需要修复的错误。 - Nathan Ridley
也许这个实现将帮助其他人,转到 code.google.com/p/text-indexing - cos
@JamesYoungman我认为你是在思考问题。我说这是公共领域的事实意味着我不会在任何法庭上站稳脚跟。即便如此,在这里你说:“我声明我从这个StackOverflow线程编写并链接到的后缀树代码是MIT许可的。用它做你想做的任何事情。” - Nathan Ridley


答案:


以下是尝试描述Ukkonen算法,首先显示当字符串简单时(即不包含任何重复字符)时它的作用,然后将其扩展为完整算法。

首先,一些初步声明。

  1. 我们正在建设的是 基本上 喜欢搜索trie。所以那里 是一个根节点,边缘走出它导致新的节点,和 进一步的边缘走出那些,等等

  2. :与搜索trie不同,边缘标签不是单一的 字符。相反,每个边使用一对整数进行标记 [from,to]。这些是指向文本的指针。从这个意义上说,每一个 edge携带任意长度的字符串标签,但只占用O(1) 空间(两个指针)。

基本原则

我想首先演示如何创建一个后缀树 特别简单的字符串,没有重复字符的字符串:

abc

算法 从左到右分步进行。有 每个字符串的一步。每个步骤可能涉及多个单独的操作,但我们将看到(参见最后的最终观察结果)操作总数为O(n)。

所以,我们从 剩下,并首先只插入单个字符 a 通过从根节点(左侧)到叶子创建边缘, 并将其标记为 [0,#],这意味着边缘代表了 子串从位置0开始到结束于 目前的结局。一世 使用符号 # 意思是 目前的结局,位于第1位 (紧随其后 a)。

所以我们有一个初始树,看起来像这样:

这意味着什么:

现在我们进入第2位(紧随其后) b)。 我们每一步的目标 是插入 所有后缀直到当前位置。我们这样做 通过

  • 扩大现有的 a - 去吧 ab
  • 插入一个新的边缘 b

在我们的表示中,这看起来像

enter image description here

它意味着:

我们观察 两件事情:

  • 边缘表示 ab 是 一样 往常 在初始树中: [0,#]。它的含义自动改变了 因为我们更新了当前的位置 # 从1到2。
  • 每条边消耗O(1)空间,因为它只包含两个空间 指向文本的指针,无论它有多少个字符 代表。

接下来,我们再次增加位置并通过追加来更新树 一个 c 到每个现有边缘并为新的边缘插入一个新边缘 后缀 c

在我们的表示中,这看起来像

它意味着:

我们观察到:

  • 树是正确的后缀树 到目前的位置 每一步之后
  • 步骤与文本中的字符数一样多
  • 每个步骤的工作量是O(1),因为所有现有边缘 通过递增自动更新 #,并插入 最终字符的一个新边可以在O(1)中完成 时间。因此,对于长度为n的字符串,仅需要O(n)时间。

第一次扩展:简单重复

当然这很好用,因为我们的字符串没有 包含任何重复。我们现在看一个更现实的字符串:

abcabxabcd

它始于 abc 如前例所示 ab 重复 然后是 x, 接着 abc 重复之后 d

步骤1到3: 在前3个步骤之后,我们得到了上一个示例中的树:

步骤4: 我们走 # 位置4.这隐含地更新了所有现有的 边缘到这个:

我们需要插入当前步骤的最后一个后缀, a, 在 根。

在我们这样做之前,我们介绍一下 另外两个变量 (此外 #),当然一直在那里,但我们没有使用过 他们到目前为止:

  • 活跃点,这是一个三重奏 (active_node,active_edge,active_length)
  • remainder,这是一个整数,表示有多少新后缀 我们需要插入

这两者的确切含义很快就会清楚,但就目前而言 我们就说:

  • 在简单 abc 例如,活跃点总是如此 (root,'\0x',0),即 active_node 是根节点, active_edge 被指定为空字符 '\0x',和 active_length 是零。这种效果就是那个新的优势 我们插入的每一步都插在根节点上作为一个 新鲜的边缘。我们很快就会看到为什么需要三元组 代表这些信息。
  • remainder 在每个开头都设置为1 步。这意味着我们必须使用的后缀数量 在每一步结束时积极插入1(总是只是 最后的角色)。

现在这将改变。当我们插入当前的final 字符 a 在根,我们注意到已经有一个外向 边缘开始 a,具体来说: abca。这是我们的工作 这样的情况:

  • 我们 不要 插入新鲜的边缘 [4,#] 在根节点。相反,我们 只需注意后缀即可 a 已经在我们的 树。它在较长边缘的中间结束,但我们不是 对此感到困扰。我们只是按照他们的方式离开。
  • 我们 设置活动点 至 (root,'a',1)。这意味着活跃 point现在位于以节点开头的根节点的传出边缘的中间位置 a特别是在该边缘的第1位之后。我们 请注意,边缘仅由第一个指定 字符 a。这就足够了,因为可以 只有一个 边缘 从任何特定字符开始(在阅读整个描述后确认这是真的)。
  • 我们也增加 remainder,所以在下一步的开始 它将是2。

观察: 当决赛 找到我们需要插入的后缀 已存在于树中,树本身就是 没有改变 根本(我们只更新活动点和 remainder)。那个树 那么就不是后缀树的准确表示 至 当前位置 更多,但它 包含 所有后缀(因为最后的 后缀 a 包含在内 隐式)。因此,除了更新 变量(都是固定长度,所以这是O(1)),有 没工作 在这一步完成。

第5步: 我们更新当前位置 # 到5.这 自动将树更新为:

因为 remainder 是2,我们需要插入两个最终版 当前位置的后缀: ab 和 b。这基本上是因为:

  • a 上一步的后缀从未如此正确 插入。所以它有 保持,因为我们已经取得了进展 一步,它现在已经成长 a 至 ab
  • 我们需要插入新的最终边缘 b

在实践中,这意味着我们转到活跃点(指向 在...后面 a 在什么是现在 abcab 边缘),并插入 目前的最终角色 b但: 事实证明,事实证明 b 是 也已经出现在同一个边缘。

所以,我们再次不改变树。我们只是:

  • 将活动点更新为 (root,'a',2) (相同的节点和边缘 和以前一样,但现在我们指向后面了 b
  • 增加 remainder 到3因为我们还没有正确 插入上一步的最后一个边,我们不插入 当前的最后边缘。

要明确:我们必须插入 ab 和 b 在当前的步骤,但 因为 ab 已经找到,我们更新了活动点并做了 甚至没有尝试插入 b。为什么?因为如果 ab 在树上, 每个后缀 它(包括 b)必须在树上, 太。也许只是 隐式,但它必须在那里,因为 到目前为止我们已经构建了这棵树。

我们继续 第6步 通过递增 #。树是 自动更新为:

因为 remainder 是3,我们必须插入 abxbx 和 x。活跃点告诉我们在哪里 ab 结束,所以我们只需要 跳到那里插入 x。确实, x 还没有,所以我们 分裂了 abcabx edge并插入一个内部节点:

边缘表示仍然是指向文本的指针,因此 拆分和插入内部节点可以在O(1)时间内完成。

所以我们已经处理过了 abx 并减少 remainder 到2.现在我们 需要插入下一个剩余的后缀, bx。但在我们这样做之前 我们需要更新活动点。拆分后的规则 并且将调用边缘 规则1 在下面,它适用于 active_node 是root(我们将进一步学习其他案例的规则3) 下面)。这是规则1:

从root插入后,

  • active_node 仍然是根
  • active_edge 设置为新后缀的第一个字符   需要插入,即 b
  • active_length 减少1

因此,新的活跃点三联 (root,'b',1) 表示 下一个插入必须在 bcabx 边缘,后面1个字符, 即在后面 b。我们可以在O(1)时间内识别插入点 检查是否 x 是否已经存在。如果它存在,我们 将结束当前步骤,并保持一切顺利。但 x 不存在,所以我们通过分割边缘插入它:

再次,这花了O(1)时间,我们更新 remainder 到1和 活跃点 (root,'x',0) 如规则1所述。

但还有一件事我们需要做。我们称之为 规则2:

如果我们拆分边并插入一个新节点,如果是的话 不是   第一个节点 在当前步骤中创建,我们连接之前的   插入节点和新节点通过一个特殊的指针,a 后缀   链接。我们稍后会看到为什么这是有用的。这是我们得到的,   后缀链接表示为虚线边缘:

我们仍然需要插入当前步骤的最后一个后缀, x。自从 active_length 活动节点的组件已经下降 为0,最后插入直接在根处进行。既然没有 以节点开头的根节点的传出边缘 x,我们插入一个新的 边缘:

我们可以看到,在当前步骤中,所有剩余的插入物都已制成。

我们继续 第7步 通过设置 #= 7,自动附加下一个字符, a,一如既往地对所有叶子边缘。然后我们尝试插入新的决赛 活动点(根)的字符,并发现它在那里 已经。所以我们结束当前步骤而不插入任何东西 将活动点更新为 (root,'a',1)

第8步#= 8,我们追加 b,如前所述,这只是 意味着我们将活动点更新为 (root,'a',2) 和增量 remainder 没有做 别的,因为 b 已经存在了。 然而, 我们注意到(在O(1)时间内)活动点 现在处于优势的尽头。我们通过重新设置来反映这一点 (node1,'\0x',0)。在这里,我用 node1 参考 内部节点 ab 边缘结束于。

然后,在 #= 9,我们需要插入'c',这将有助于我们 了解最后的诀窍:

第二个扩展:使用后缀链接

一如既往 # 更新追加 c 自动到叶边 然后我们转到活动点,看看我们是否可以插入'c'。事实证明 out'c'已存在于该边缘,因此我们将活动点设置为 (node1,'c',1), 增量 remainder 什么都不做

现在进来 #= 10remainder is 4,所以我们首先需要插入 abcd (通过插入仍然是3步之前) d 活跃的 点。

试图插入 d 在活动点导致边缘分裂 O(1)时间:

active_node从中开始分割,标记为 上面的红色。这是最终规则, 规则3:

从一个分裂边缘后 active_node 那不是根   如果存在,我们遵循从该节点出来的后缀链接   任何,并重置 active_node 到它指向的节点。如果有   没有后缀链接,我们设置了 active_node到了根。 active_edge   和 active_length 保持不变。

所以活跃点就是现在 (node2,'c',1),和 node2 被标记为 红色如下:

自插入 abcd 完成后,我们减少 remainder 至 3并考虑当前步骤的下一个剩余后缀, bcd。规则3将活动点设置为正确的节点和边缘 插入 bcd 可以通过简单地插入其最终字符来完成 d 在活跃点。

这样做会导致另一个边缘分裂,并且 因为规则2我们 必须创建从先前插入的节点到新节点的后缀链接 一:

我们观察到: 后缀链接使我们可以重置活动点,以便我们   可以做下一个 剩下的插页 在O(1)努力。看着那(这   上面的图表确认标签上确实存在节点 ab 与...有关   节点在 b (后缀)和节点 abc 与...有关    bc

目前的步骤尚未完成。 remainder 现在是2,我们 需要遵循规则3再次重置活动点。自从 当前 active_node (上面的红色)没有后缀链接,我们重置为 根。活跃点现在 (root,'c',1)

因此,下一个插入发生在根节点的一个输出边缘 其标签以 ccabxabcd,在第一个角色后面, 即在后面 c。这导致另一个分裂:

由于这涉及创建一个新的内部节点,我们遵循 规则2并从先前创建的内部设置新的后缀链接 节点:

(我在用 Graphviz Dot 对于这些小 图表。新的后缀链接导致dot重新排列现有的 边缘,所以仔细检查确认唯一的事情 上面插入的是一个新的后缀链接。)

有了这个, remainder 可以设置为1,因为 active_node 是 root,我们使用规则1来更新活动点 (root,'d',0)。这个 表示当前步骤的最终插入是插入单个 d 在根:

这是最后一步,我们已经完成了。有很多 最后 意见但是:

  • 在每一步中我们都会移动 # 前进1个位置。这是自动的 在O(1)时间内更新所有叶节点。

  • 但它不涉及a)任何后缀 其余 从以前 步骤,和b)使用当前步骤的最后一个字符。

  • remainder 告诉我们需要多少额外的插件 使。这些插入与最终后缀一一对应 在当前位置结束的字符串 #。我们考虑一个 在另一个之后并制作插入物。 重要: 每个插入都是 在O(1)时间内完成,因为活动点告诉我们确切的位置 go,我们只需要在active中添加一个单个字符 点。为什么?因为其他人物都是 隐含地包含 (否则活动点不会是它的位置)。

  • 在每次这样的插入之后,我们减少 remainder 并按照 后缀链接,如果有的话。如果不是,我们去根(规则3)。要是我们 已经在根,我们使用规则1修改活动点 无论如何,它只需要O(1)时间。

  • 如果,在其中一个插入过程中,我们发现了我们想要的角色 插入已经存在,我们什么都不做,结束了 当前步骤,即使 remainder> 0。原因是任何 剩下的插入将是我们尝试过的插入的后缀 使。因此他们都是 含蓄 在当前树中。事实 那 remainder> 0确保我们处理剩余的后缀 后来。

  • 如果在算法结束时怎么办? remainder> 0?这将是 只要文本的结尾是发生的子字符串就是大小写 以前的某个地方。在这种情况下,我们必须追加一个额外的角色 在之前没有发生的字符串的末尾。在里面 文学,通常是美元符号 $ 用作符号 那。 为什么这么重要?  - >如果以后我们使用完成的后缀树来搜索后缀,我们必须只接受匹配 落叶。否则我们会得到很多虚假的比赛,因为有 许多 字符串 隐式 包含在树中的不是主字符串的实际后缀。强制 remainder 最后为0本质上是一种确保所有后缀在叶节点处结束的方法。 然而, 如果我们想用树来搜索 一般子串, 不仅 后缀 在主要字符串中,这个最后一步确实不是必需的,正如OP的评论所示。

  • 那么整个算法的复杂性是多少?如果文字是n 字符的长度,显然有n个步骤(如果我们添加,则为n + 1) 美元符号)。在每一步中,我们要么什么都不做(除了 更新变量),或者我们制作 remainder 插入,每个取O(1) 时间。以来 remainder 表示我们没有做过多少次 在前面的步骤中,并为我们制作的每个插入递减 现在,我们做某事的总次数恰好是n(或 N + 1)。因此,总复杂度为O(n)。

  • 但是,有一件小事我没有正确解释: 我们可能会遵循后缀链接,更新活动 点,然后找到它 active_length 组件没有 与新的一起工作 active_node。例如,考虑一种情况 喜欢这个:

(虚线表示树的其余部分。虚线是a 后缀链接。)

现在让积极的一点 (red,'d',3),所以它指向这个地方 在...后面 f 在...上 defg 边缘。现在假设我们做了必要的 更新,现在按照后缀链接更新活动点 根据规则3.新的活跃点是 (green,'d',3)。然而, 该 d - 走出绿色节点的是 de,所以它只有2个 字符。我们显然是为了找到正确的活跃点 需要跟随该边缘到蓝色节点并重置为 (blue,'f',1)

在一个特别糟糕的情况下, active_length 可能会像 remainder,可以和n一样大。它很可能会发生 要找到正确的活动点,我们不仅要跳过一个 内部节点,但也许很多,在最坏的情况下最多n。那样做 意味着该算法具有隐藏的O(n2)复杂性,因为 在每一步 remainder 一般是O(n),后期调整 跟随后缀链接到主动节点也可能是O(n)?

不,原因是如果确实我们必须调整活跃点 (例如,从上面的绿色到蓝色),这将我们带到一个新的节点 有自己的后缀链接,和 active_length 将减少。如 我们跟进我们制作剩余插入的后缀链接链, active_length 只可以 减少,以及我们可以进行的活动点调整的数量 方式不能大于 active_length 在任何给定的时间。以来 active_length 永远不会大于 remainder,和 remainder O(n)不仅是每一步,而且是增量的总和 曾经做过 remainder 在整个过程中是 O(n)也是有效点调整的数量 上)。


2164
2018-03-01 09:13



对不起,这比我希望的要长一点。我意识到它解释了我们都知道的一些微不足道的事情,而困难的部分可能仍然不是很清楚。让我们一起编辑它。 - jogojapan
我应该补充一点 不 根据Dan Gusfield的书中的描述。这是通过首先考虑没有重复的字符串然后讨论如何处理重复来描述算法的新尝试。我希望这会更直观。 - jogojapan
谢谢@jogojapan,由于你的解释,我能够写一个完整的例子。我已经发布了源代码,所以希望其他人可能会发现它的用途: gist.github.com/2373868 - Nathan Ridley
@NathanRidley是的(顺便说一句,最后一点是Ukkonen称之为canonicize)。触发它的一种方法是确保有一个子串出现三次,并以一个字符串结束,该字符串在另一个上下文中再次出现。例如。 abcdefabxybcdmnabcdex。最初的部分 abcd 重复进来 abxy (这会在之后创建一个内部节点 ab)并再次进入 abcdex,它结束了 bcd,这不仅出现在 bcdex 背景,但也在 bcdmn 上下文。后 abcdex 插入后,我们按照后缀链接插入 bcdex,并且可以启用canonicize。 - jogojapan
好的,我的代码已经完全重写,现在可以在所有情况下正常工作,包括自动封装,还有一个更好的文本图输出。 gist.github.com/2373868 - Nathan Ridley


我尝试使用jogojapan的答案中给出的方法来实现后缀树,但由于用于规则的措辞,它在某些情况下不起作用。此外,我已经提到没有人设法使用这种方法实现一个绝对正确的后缀树。下面我将写一个jogojapan答案的“概述”,并对规则进行一些修改。我还将描述我们忘记创造的情况 重要 后缀链接。

使用其他变量

  1. 活跃点  - 一个三元组(active_node; active_edge; active_length),显示我们必须从哪里开始插入新的后缀。
  2.   - 显示我们必须添加的后缀数量 明确地。例如,如果我们的单词是'abcaabca',并且余数= 3,则意味着我们必须处理3个最后的后缀: BCACA 和 一个

让我们用一个概念 内部节点  - 所有节点,除了  和 叶子 是 内部节点

观察1

当我们发现需要插入的最后一个后缀已经存在于树中时,树本身根本没有改变(我们只更新了 active point 和 remainder)。

观察2

如果在某个时候 active_length 大于或等于当前边缘的长度(edge_length),我们移动我们的 active point 直到 edge_length 严格地大于 active_length

现在,让我们重新定义规则:

规则1

如果从插入后 活动节点 = 有效长度 大于0,则:

  1. 活动节点 没有改变
  2. 有效长度 减少了
  3. 活跃的边缘 向右移动(到我们必须插入的下一个后缀的第一个字符)

规则2

如果我们创造一个新的 内部节点  要么 从一个插入器 内部节点,这不是第一个 这样  内部节点 在当前步骤,然后我们链接前一步 这样 节点 这个 一到一个 后缀链接

这个定义了 Rule 2 与jogojapan'不同,因为在这里我们不仅考虑了 新创造的 内部节点,也是内部节点,我们从中插入。

规则3

从插入后 活动节点 这不是  节点,我们必须遵循后缀链接并设置 活动节点 到它指向的节点。如果没有后缀链接,请设置 活动节点 到了  节点。无论哪种方式, 活跃的边缘 和 有效长度 保持不变。

在这个定义中 Rule 3 我们还考虑叶节点的插入(不仅是分裂节点)。

最后,观察3:

当我们想要添加到树的符号已经在边缘时,我们,根据 Observation 1,仅更新 active point 和 remainder,保持树不变。  如果有的话 内部节点 标记为 需要后缀链接,我们必须用当前的节点连接该节点 active node 通过后缀链接。

让我们看一下后缀树的例子 cdddcdc 如果我们在这种情况下添加后缀链接,如果我们不这样做:

  1. 要是我们  通过后缀链接连接节点:

    • 在添加最后一个字母之前 C

    • 添加最后一个字母后 C

  2. 要是我们  通过后缀链接连接节点:

    • 在添加最后一个字母之前 C

    • 添加最后一个字母后 C

似乎没有显着差异:在第二种情况下,还有两个后缀链接。但这些后缀链接是 正确,其中之一 - 从蓝色节点到红色节点 - 非常 重要 对于我们的方法 活跃点。问题是,如果我们不在这里添加后缀链接,稍后,当我们向树中添加一些新字母时,我们可能会省略向树添加一些节点,因为 Rule 3,因为,根据它,如果没有后缀链接,那么我们必须把 active_node 到了根。

当我们将最后一个字母添加到树中时,红色节点有 已经存在 在我们从蓝色节点进行插入之前(边缘标记为 'C')。由于蓝色节点有插入,我们将其标记为 需要后缀链接。然后,依靠 活跃点 方法, active node 被设置为红色节点。但我们不会像红色节点那样插入字母 'C' 已经处于边缘。这是否意味着蓝色节点必须没有后缀链接?不,我们必须通过后缀链接将蓝色节点与红色节点连接起来。为什么这是正确的?因为 活跃点 方法保证我们到达正确的地方,即我们必须处理a的插入的下一个地方  后缀。

最后,这是我对后缀树的实现:

  1. Java的
  2. C ++

希望这个“概述”结合jogojapan的详细答案将有助于某人实现自己的后缀树。


112
2018-01-29 09:57



非常感谢,+1为你的努力。我相信你是对的......虽然我没有时间立刻考虑细节。我稍后会检查,然后也可能修改我的答案。 - jogojapan
非常感谢,这真的很有帮助。虽然,你能更具体地观察观察3吗?例如,给出引入新后缀链接的2个步骤的图表。节点是否与活动节点相关联? (因为我们实际上没有插入第二个节点) - dyesdyes
@makagonov嘿,你能帮我为你的字符串构建后缀树“cdddcdc”我这样做有点困惑(开始的步骤)。 - tariq zafar
对于规则3,一种聪明的方法是将root的后缀链接设置为root本身,并且(默认情况下)将每个节点的后缀链接设置为root。因此,我们可以避免条件,只需遵循后缀链接。 - sqd
很棒的解释!我只想补充一点。我仍然试图理解,但据我所知,这个解释略过了一个边缘案例:“abca”。前一个数字在字符串中重复的情况。在这种情况下,我们需要在字符串中附加一个结束字符,比如'$'。检查第5段 cise.ufl.edu/~sahni/dsaaj/enrich/c16/suffix.htm - elif


感谢您提供的解释良好的教程 @jogojapan,我用Python实现了算法。

@jogojapan提到的一些小问题证明是更多 复杂的 超出我的预期,需要非常小心对待。我需要几天的时间才能完成实施 足够强大 (我想)。问题和解决方案如下:

  1. 结束 Remainder > 0 事实证明,这种情况也可能发生 在展开的步骤,而不仅仅是整个算法的结束。当发生这种情况时,我们可以留下余数,actnode,actted和actlength 不变,结束当前的展开步骤,并根据原始字符串中的下一个字符是否在当前路径上,保持折叠或展开,从而开始另一个步骤。

  2. 跳过节点: 当我们遵循后缀链接时,更新活动点,然后发现其active_length组件与新的active_node不兼容。我们必须 前进 到正确的地方拆分,或插入一片叶子​​。这个过程可能是 不是那么简单 因为在移动过程中,actlength和actted一直在变化,当你必须移回时 根节点actedge 和 actlength 可能 错误 因为那些举动。我们需要额外的变量来保存这些信息。

    enter image description here

另外两个问题以某种方式被指出 @managonov

  1. 分裂可能堕落 尝试拆分边时,有时您会发现拆分操作在节点上。在这种情况下,我们只需要向该节点添加一个新的叶子,将其作为标准的边缘分割操作,这意味着如果存在任何后缀链接,则应相应地进行维护。

  2. 隐藏的后缀链接 还有另一个特殊情况 问题1 和 问题2。有时我们可能需要跳过几个节点到正确的点进行拆分 超过 如果我们通过比较余数字符串和路径标签来移动,那么这是正确的。如果应该有任何后缀链接将无意中被忽略。这可以通过以下方式避免 记住正确的观点 前进的时候。如果拆分节点已存在,或者甚至是,则应保留后缀链接 问题1 在展开的步骤中发生。

最后,我的实施 蟒蛇 如下:

提示:  它包括一个天真的 树印刷 函数在上面的代码中,这在调试时非常重要。它为我节省了很多   时间,便于查找特殊情况。


7
2017-08-02 02:35





我的直觉如下:

在主循环的k次迭代之后,您构建了一个后缀树,其中包含以前k个字符开头的完整字符串的所有后缀。

在开始时,这意味着后缀树包含表示整个字符串的单个根节点(这是从0开始的唯一后缀)。

在len(字符串)迭代之后,您有一个包含所有后缀的后缀树。

在循环期间,键是活动点。我的猜测是,这代表后缀树中最深的一点,它对应于字符串前k个字符的正确后缀。 (我认为正确意味着后缀不能是整个字符串。)

例如,假设您已经看过字符'abcabc'。活动点将表示树中对应于后缀“abc”的点。

活动点由(origin,first,last)表示。 这意味着您当前位于树中您从节点原点开始然后以字符串[first:last]中的字符输入的位置

添加新字符时,您会查看活动点是否仍在现有树中。如果是,那么你就完成了。 否则,您需要在活动点的后缀树中添加新节点,回退到下一个最短匹配,然后再次检查。

注1: 后缀指针为每个节点提供下一个最短匹配的链接。

笔记2: 添加新节点和回退时,为新节点添加新的后缀指针。 此后缀指针的目标将是缩短活动点的节点。 此节点将已存在,或者在此回退循环的下一次迭代中创建。

注3:标准化部分只是节省了检查活动点的时间。 例如,假设您始终使用origin = 0,并且只是先改变了最后一个。 要检查活动点,每次沿着所有中间节点都必须遵循后缀树。 通过仅记录距离最后一个节点的距离来缓存跟踪此路径的结果是有意义的。

你能给出一个“修复”边界变量的代码示例吗?

健康警告:我也发现这个算法特别难以理解,所以请认识到这种直觉可能在所有重要细节中都是错误的......


6
2018-02-26 20:16



其中一篇学术论文将“正确”定义为字符串的“正确后缀”不包含其第一个字符。有时你将整个子字符串称为“后缀”,但在定义算法时,术语“字符串”,“子字符串”和“后缀”会被大量抛出,有时你需要非常清楚“后缀”是什么意思,所以术语“正确的后缀”不包括将整个事物称为后缀。因此,字符串的后缀子字符串可以是任何合法的子字符串,并且可以具有不同的后缀的正确后缀。因为逻辑。 - Blair Houghton


嗨,我已经尝试在ruby中实现上面解释的实现,请检查出来。 它似乎工作正常。

实现的唯一区别是,我试图使用边缘对象而不是仅使用符号。

它也出现在 https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

3
2018-03-02 10:54





@jogojapan你带来了很棒的解释和可视化。但正如@makagonov所说,它缺少一些关于设置后缀链接的规则。当一步一步地进行时,它以可见的方式可见 http://brenden.github.io/ukkonen-animation/ 通过'aabaaabb'这个词。当您从步骤10转到步骤11时,没有从节点5到节点2的后缀链接,但是活动点突然在那里移动。

@makagonov,因为我住在Java世界,我也试着按照你的实现来掌握ST建设工作流程,但由于以下原因我很难:

  • 将边与节点相结合
  • 使用索引指针而不是引用
  • 打破陈述;
  • 继续陈述;

所以我最终在Java中实现了这样的实现,我希望以更清晰的方式反映所有步骤,并减少其他Java人员的学习时间:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

2
2018-04-21 14:22