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

6 回答

• 6

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

  First, a few preliminary statements.

  • 我们正在建设的，基本上就像搜索特里 . 所以有一个根节点，从它出来的边缘导致新的节点，以及更远的边缘，等等

  • But ：与搜索trie不同，边缘标签不是单个字符 . 相反，每个边都使用一对整数 [from,to] 进行标记 . 这些是指向文本的指针 . 从这个意义上讲，每条边都带有一个任意长度的字符串标签，但只占用O（1）空间（两个指针） .

  基本原理

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

  abc
  

  算法 works in steps, from left to right . 有 one step for every character of the string . 每个步骤可能涉及多个单独的操作，但我们将看到（参见最后的最终观察结果）操作总数为O（n） .

  所以，我们从左边开始，首先只插入单个字符 a ，通过从根节点（左边）到叶子创建边缘，并将其标记为 [0,#] ，这意味着边缘表示从位置0开始的子字符串并在当前结束 . 我使用符号 # 表示当前结束，它位于第1位（在 a 之后） .

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

  

  这意味着什么：

  

  现在我们进入第2位（在 b 之后） . Our goal at each step 是要插入 all suffixes up to the current position . 我们这样做

  • 将现有的 a -edge扩展为 ab

  • 为 b 插入一个新边

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

  

  它意味着：

  

  We observe 两件事：

  • ab 的边缘表示是 the same ，因为它曾经在初始树中： [0,#] . 它的含义自动更改，因为我们将当前位置 # 从1更新为2 .

  • 每个边消耗O（1）空间，因为它只包含两个指向文本的指针，无论它代表多少个字符 .

  接下来，我们再次递增位置并通过将 c 附加到每个现有边并为新后缀 c 插入一个新边来更新树 .

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

  

  什么呢意思是：

  

  We observe:

  • 树是每个步骤后直到当前位置的正确后缀树

  • 步骤与文本中的字符数一样多

  • 每个步骤中的工作量为O（1），因为所有现有边缘都通过递增 # 自动更新，并且为最终字符插入一个新边缘可以在O（1）时间内完成 . 因此，对于长度为n的字符串，仅需要O（n）时间 .

  第一次扩展：简单重复

  当然这很好用，因为我们的字符串不包含任何重复 . 我们现在看一个更现实的字符串：

  abcabxabcd
  

  它以 abc 开头，如上例所示，然后重复 ab ，然后重复 x ，然后重复 abc ，然后重复 d .

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

  

  Step 4: 我们将 # 移动到位置4.这会隐式更新所有现有边缘：

  

  我们需要在根目录下插入当前步骤 a 的最后一个后缀 .

  在我们这样做之前，我们介绍 two more variables （除 # 之外），当然一直都在那里，但到目前为止我们还没有使用它们：

  • active point ，这是一个三重 (active_node,active_edge,active_length)

  • remainder ，这是一个整数，表示我们需要插入多少个新后缀

  这两者的确切含义很快就会清楚，但现在让我们说：

  • 在简单的 abc 示例中，活动点始终为 (root,'\0x',0) ，即 active_node 是根节点， active_edge 被指定为空字符 '\0x' ， active_length 为零 . 这样做的结果是我们在每个步骤中插入的一个新边缘作为新创建的边缘插入根节点 . 我们很快就会看到为什么需要三元组来表示这些信息 .

  • remainder 始终在每个步骤开始时设置为1 . 这意味着我们必须在每个步骤结束时主动插入的后缀数量为1（始终只是最后一个字符） .

  现在这将改变 . 当我们在根目录插入当前最后一个字符 a 时，我们注意到已经有一个以 a 开头的传出边，特别是： abca . 以下是我们在这种情况下所做的事情：

  • 我们 do not 在根节点插入新边 [4,#] . 相反，我们只是注意到后缀 a 已经在我们的树中了 . 它在较长边缘的中间结束，但我们并不为此烦恼 . 我们只是按照他们的方式离开 .

  • 我们 set the active point 至 (root,'a',1) . 这意味着活动点现在位于以 a 开头的根节点的传出边缘的中间位置，特别是在该边缘上的位置1之后 . 我们注意到边缘仅由其第一个字符 a 指定 . 这就足够了，因为只有一个边缘以任何特定字符开头（在阅读整个描述后确认这是真的） .

  • 我们也增加 remainder ，所以在下一步的开头它将是2 .

  Observation: 当最后的 suffix we need to insert is found to exist in the tree already 时，树本身就是 not changed （我们只更新活动点和 remainder ） . 树不再是后缀树的精确表示，直到当前位置，但它 contains 所有后缀（因为最后的后缀 a 是隐式包含的） . 因此，除了更新变量（全部是固定长度，因此这是O（1））之外，在此步骤中完成了 no work .

  Step 5: 我们将当前位置 # 更新为5.这会自动将树更新为：

  

  而 because remainder is 2 ，我们需要插入当前位置的两个最终后缀： ab 和 b . 这基本上是因为：

  • 上一步的 a 后缀从未正确插入 . 所以它一直存在，并且由于我们已经取得了一步，它现在已经从 a 增长到 ab .

  • 我们需要插入新的最终边缘 b .

  在实践中，这意味着我们转到活动点（指向 a 后面的 abcab 边缘），并插入当前的最终字符 b . But: 再次，事实证明 b 也已存在于同一边缘 .

  所以，我们再次不改变树 . 我们只是：

  • 将活动点更新为 (root,'a',2) （与之前相同的节点和边缘，但现在我们指向 b 后面）

  • 将 remainder 递增为3，因为我们仍然没有正确插入上一步的最后一个边，我们也没有插入当前的最终边 .

  要明确：我们必须在当前步骤中插入 ab 和 b ，但由于已找到 ab ，我们更新了活动点，甚至没有尝试插入 b . 为什么？因为如果 ab 在树中，它的 every suffix （包括 b ）也必须在树中 . 也许只是含蓄地，但它必须存在，因为我们迄今为止构建树的方式 .

  我们通过递增 # 继续 step 6 . 树自动更新为：

  

  因为 remainder is 3 ，我们必须插入 abx ， bx 和 x . 活动点告诉我们 ab 在哪里结束，所以我们只需要跳转并插入 x . 实际上， x 还没有，所以我们拆分 abcabx 边并插入一个内部节点：

  

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

  所以我们处理 abx 并将 remainder 减少到2.现在我们需要插入下一个剩余的后缀 bx . 但在我们这样做之前，我们需要更新活动点 . 在分割和插入边之后，此规则将在下面被称为 Rule 1 ，并且只要 active_node 是root，它就适用（我们将在下面的其他情况下学习规则3） . 这是规则1：

  从root插入后，active_node保持root active_edge设置为我们需要插入的新后缀的第一个字符，即b active_length减少1

  因此，新的活动点三元组 (root,'b',1) 表示下一个插入必须在 bcabx 边缘，在1个字符后面，即在 b 之后 . 我们可以在O（1）时间内识别插入点并检查 x 是否已经存在 . 如果它存在，我们将结束当前步骤并将所有内容保留原样 . 但是 x 不存在，所以我们通过分割边缘来插入它：

  

  再次，这需要O（1）时间，我们将 remainder 更新为1，并将活动点更新为 (root,'x',0) 作为规则1状态 .

  但还有一件事我们需要做 . 我们称之为 Rule 2:

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

  

  我们仍然需要插入当前步骤的最后一个后缀 x . 由于活动节点的 active_length 组件已降至0，因此最终插入将直接在根处进行 . 由于在根节点处没有以 x 开头的传出边，因此我们插入一个新边：

  

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

  我们通过设置 # = 7继续 step 7 ，它会像往常一样自动将下一个字符 a 附加到所有叶子边缘 . 然后我们尝试将新的最终字符插入活动点（根），并发现它已存在 . 因此，我们结束当前步骤而不插入任何内容并将活动点更新为 (root,'a',1) .

  在 step 8 ， # = 8中，我们追加 b ，并且如前所述，这仅表示我们将活动点更新为 (root,'a',2) 并在不执行任何其他操作的情况下递增 remainder ，因为 b 已经存在 . However, 我们注意到（在O（1）时间内）活动点现在位于边缘的末尾 . 我们通过将其重新设置为 (node1,'\0x',0) 来反映这一点 . 在这里，我使用 node1 来引用 ab 边结束的内部节点 .

  然后，在 step #=9 中，我们需要插入'c'，这将有助于我们理解最后的技巧：

  第二次扩展：使用后缀链接

  与往常一样， # update会自动将 c 追加到叶子边缘，然后我们转到活动点以查看是否可以插入'c' . 事实证明'c'已存在于该边缘，因此我们将活动点设置为 (node1,'c',1) ，增加 remainder 并且不执行任何其他操作 .

  现在在 step #=10 ， remainder is 4 ，所以我们首先需要在活动点插入 d 来插入 abcd （从3步前开始） .

  尝试在活动点插入 d 会导致在O（1）时间内进行边缘分割：

  

  启动拆分的 active_node 在上面用红色标记 . 这是最终规则， Rule 3:

  从不是根节点的active_node分割边缘后，我们遵循从该节点出来的后缀链接（如果有），并将active_node重置为它指向的节点 . 如果没有后缀链接，我们将active_node设置为root . active_edge和active_length保持不变 .

  所以活动点现在是 (node2,'c',1) ， node2 在下面用红色标记：

  

  由于 abcd 的插入已完成，我们将 remainder 减少为3并考虑当前步骤的下一个剩余后缀 bcd . 规则3将活动点设置为正确的节点和边缘，因此只需在活动点插入其最终字符 d 即可插入 bcd .

  执行此操作会导致另一个边缘拆分，并且 because of rule 2 ，我们必须创建从先前插入的节点到新节点的后缀链接：

  

  We observe: 后缀链接使我们能够重置活动点，所以我们可以在O（1）努力下进行下一个剩余的插入 . 查看上面的图表以确认标签 ab 处的节点确实链接到 b （其后缀）处的节点，而 abc 处的节点链接到 bc .

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

  因此，下一个插入发生在根节点的一个输出边缘，其标签以 c ： cabxabcd 开头，在第一个字符后面，即在 c 之后 . 这导致另一个分裂：

  

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

  

  （我正在使用Graphviz Dot这些小图 . 新的后缀链接导致点重新排列现有边缘，因此请仔细检查以确认上面插入的唯一内容是新的后缀链接 . ）

  有了这个， remainder 可以设置为1，因为 active_node 是root，我们使用规则1将活动点更新为 (root,'d',0) . 这意味着当前步骤的最后一个插入是在根目录下插入一个 d ：

  

  这是最后一步，我们已经完成了 . 但是有多少 final observations ：

  • 在每一步中，我们将 # 向前移动1个位置 . 这会在O（1）时间内自动更新所有叶节点 .

  • 但它不涉及a）前面步骤中剩余的任何后缀，以及b）当前步骤的最后一个字符 .

  • remainder 告诉我们需要做多少额外的插入 . 这些插入与字符串的最终后缀一一对应，该字符串以当前位置 # 结束 . 我们一个接一个地考虑并插入 . Important: 每个插入都在O（1）时间完成，因为活动点告诉我们到底要去哪里，我们需要在活动点只添加一个单个字符 . 为什么？因为隐含地包含其他字符（否则活动点将不在其中） .

  • 在每个这样的插入之后，我们递减 remainder 并且如果有的话后面跟随后缀链接 . 如果不是，我们去根（规则3） . 如果我们已经在root，我们使用规则1修改活动点 . 在任何情况下，它只需要O（1）时间 .

  • 如果在其中一个插入过程中，我们发现要插入的字符已经存在，我们不会执行任何操作并结束当前步骤，即使 remainder > 0 . 原因是剩下的任何插入都将是我们试图制作的插入的后缀 . 因此它们都隐含在当前树中 . remainder > 0的事实确保我们稍后处理剩余的后缀 .

  • 如果在算法结束时 remainder > 0怎么办？只要文本的结尾是之前发生过的子字符串，就会出现这种情况 . 在这种情况下，我们必须在字符串末尾添加一个额外的字符，之前没有发生过 . 在文献中，通常使用美元符号 $ 作为其符号 . Why does that matter? - >如果以后我们使用完成的后缀树来搜索后缀，我们必须接受匹配，只有它们以叶子结尾 . 否则我们会得到很多虚假匹配，因为树中隐含的许多字符串不是主字符串的实际后缀 . 强制 remainder 在结尾处为0实质上是一种确保所有后缀在叶节点处结束的方法 . However, 如果我们想要使用树来搜索一般子字符串，而不仅仅是主字符串的后缀，这个最后一步确实不是必需的，正如下面OP的评论所建议的那样 .

  • 那么整个算法的复杂性是多少？如果文本长度为n个字符，则显然有n个步骤（如果我们添加美元符号，则为n 1） . 在每个步骤中，我们要么什么也不做（除了更新变量），或者我们进行 remainder 插入，每次都花费O（1）时间 . 因为 remainder 表示我们在之前的步骤中没有做过多少次，并且对于我们现在制作的每个插入都递减了，所以我们做某事的总次数恰好是n（或n 1） . 因此，总复杂度为O（n） .

  • 但是，有一件小事我没有正确解释：可能会发生我们遵循后缀链接，更新活动点，然后发现它的 active_length 组件与新的 active_node 不兼容 . 例如，考虑这样的情况：

  

  （虚线表示树的其余部分 . 虚线是后缀链接 . ）

  现在让活动点为 (red,'d',3) ，因此它指向 defg 边缘 f 后面的位置 . 现在假设我们进行了必要的更新，现在按照后缀链接更新活动点，根据规则3.新的活动点是 (green,'d',3) . 但是，退出绿色节点的 d -edge是 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），数量是活动点调整也受O（n）限制 .

  回复于 2024-04-24T18:58:03+08:00
• 7

  由于用于规则的措辞，我尝试使用jogojapan 's answer, but it didn'中给出的方法来实现后缀树 . 而且，我对这些规则进行了一些修改 . 我还将描述忘记创建 important 后缀链接的情况 .

  Additional variables used

  • active point - 三元组（active_node; active_edge; active_length），显示我们必须从哪里开始插入新后缀 .

  • remainder - 显示我们必须明确添加的后缀数量 . 例如，如果我们的单词是'abcaabca'，而余数= 3，则意味着我们必须处理3个最后的后缀： bca ， ca 和 a .

  让我们使用 internal node 的概念 - 除了根和叶子之外的所有节点都是 internal nodes .

  Observation 1

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

  Observation 2

  如果在某一时刻 active_length 大于或等于当前边缘的长度（ edge_length ），我们将 active point 向下移动，直到 edge_length 严格大于 active_length .

  现在，让我们重新定义规则：

  Rule 1

  如果从活动节点插入= root后，活动长度大于0，则：活动节点未更改活动长度递减活动边缘向右移动（到下一个后缀的第一个字符，我们必须插入）

  Rule 2

  如果我们创建一个新的内部节点或从内部节点创建一个插入器，并且这不是当前步骤中的第一个SUCH内部节点，那么我们通过后缀链接将前一个SUCH节点与该一个节点链接起来 .

  Rule 2 的这个定义与jogojapan'不同，因为我们不仅考虑了新创建的内部节点，还考虑了我们进行插入的内部节点 .

  Rule 3

  从非活动节点插入非根节点后，我们必须遵循后缀链接并将活动节点设置为它指向的节点 . 如果没有后缀链接，请将活动节点设置为根节点 . 无论哪种方式，有效边沿和有效长度保持不变 .

  在 Rule 3 的这个定义中，我们还考虑了叶节点的插入（不仅是分裂节点） .

  And finally, Observation 3:

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

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

  • 如果我们 DON'T 通过后缀链接连接节点：

  在添加最后一个字母 c 之前

  • ：

  

  添加最后一个字母 c 后

  • ：

  

  • 如果我们 DO 通过后缀链接连接节点：

  在添加最后一个字母 c 之前

  • ：

  

  添加最后一个字母 c 后

  • ：

  

  似乎没有显着差异：在第二种情况下，还有两个后缀链接 . 但是这些后缀链接是正确的，其中一个 - 从蓝色节点到红色节点 - 对于我们使用 active point 的方法来说非常 important . 问题是，如果我们不在这里添加后缀链接，稍后，当我们向树中添加一些新字母时，由于 Rule 3 ，我们可能会省略向树中添加一些节点，因为根据它，如果没有一个后缀链接，然后我们必须将 active_node 放到根目录 .

  当我们将最后一个字母添加到树中时，红色节点在我们从蓝色节点插入（边缘标记为 'c' ）之前有 already existed . 因为有一个插入蓝色节点，我们将其标记为需要后缀链接 . 然后，依靠 active point 方法， active node 被设置为红色节点 . 但是我们不从红色节点插入，因为字母 'c' 已经在边缘 . 这是否意味着蓝色节点必须没有后缀链接？不，我们必须通过后缀链接将蓝色节点与红色节点连接起来 . 为什么这是正确的？因为 active point 方法保证我们到达正确的位置，即下一个我们必须处理 shorter 后缀插入的地方 .

  最后，这是我对后缀树的实现：

  • Java

  • C++

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

  回复于 2024-04-24T18:58:03+08:00
• 3

  感谢 @jogojapan 提供了很好的解释教程，我用Python实现了算法 .

  @jogojapan提到的一些小问题比我预期的要多得多 sophisticated ，需要非常小心对待 . 我花了几天时间来实现我的实现 robust enough （我想） . 问题和解决方案如下：

  • End with Remainder > 0 事实证明，这种情况也可能发生 during the unfolding step ，而不仅仅是整个算法的结束 . 当发生这种情况时，我们可以保留余数，actnode，actedge和actlength unchanged ，结束当前的展开步骤，并通过保持折叠或展开来开始另一步，具体取决于原始字符串中的下一个字符是否在当前路径上或不 .

  • Leap Over Nodes: 当我们遵循后缀链接时，更新活动点，然后发现其active_length组件与新的active_node不兼容 . 我们必须 move forward 到正确的地方拆分，或插入一片叶子 . 这个过程可能是 not that straightforward 因为在移动期间actlength和actedge一直在变化，当你必须回到 root node 时，由于这些移动， actedge 和 actlength 可能是 wrong . 我们需要额外的变量来保存这些信息 .

  

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

  • Split Could Degenerate 当试图分割边缘时，有时你应该相应地维护它 .

  • Hidden Suffix Links 还有另一个由问题1和问题2引起的特殊情况 . 有时我们需要跳过几个节点到正确的点进行拆分，如果我们通过比较余数字符串和路径标签来移动，我们可能会 surpass 正确的点 . 如果应该有任何后缀链接将无意中被忽略 . 当前进时， remembering the right point 可以避免这种情况 . 如果拆分节点已存在，则应保留后缀链接，或者甚至在展开步骤期间发生问题1 .

  最后，我在 Python 中的实现如下：

  • Python

  提示：它包含上面代码中的天真树打印功能，这在调试时非常重要 . 它为我节省了大量时间，方便查找特殊情况 .

  回复于 2024-04-24T18:58:03+08:00
• 2218

  我的直觉如下：

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

  在开始时，这意味着后缀树包含表示整个字符串的单个根节点（这是从0开始的唯一后缀） .

  在len（字符串）迭代之后，您有一个包含所有后缀的后缀树 .

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

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

  活动点由（origin，first，last）表示 . 这意味着您当前位于树中您从节点原点开始然后以字符串[first：last]中的字符输入的位置

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

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

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

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

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

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

  回复于 2024-04-24T18:58:03+08:00
• 3

  嗨，我已经尝试在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
  

  回复于 2024-04-24T18:58:03+08:00
• 117

  @jogojapan你带来了很棒的解释和可视化 . 但正如@makagonov提到的那样's missing some rules regarding setting suffix links. It'在通过'aabaaabb'一步一步地在http://brenden.github.io/ukkonen-animation/上一步一步地可见 . 当您从步骤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);
          }
      });
    }
  }
  

  回复于 2024-04-24T18:58:03+08:00