algorithm - Ukkonen 的广义后缀树算法

Question

我目前正在研究我自己的后缀树实现(使用 C++，但问题仍然与语言无关)。我研究了 the original paper from Ukkonen 。这篇文章非常清楚，所以我开始着手我的实现并尝试解决通用后缀树的问题。

在树中，从一个节点到另一个节点的每个子串都使用一对整数表示。虽然这对于常规后缀树来说很简单，但当多个字符串共存于同一棵树中时会出现问题(这成为广义后缀树)。事实上，现在这样的一对是不够的，我们需要另一个变量来说明我们正在使用哪个引用字符串。

一个简单的例子。考虑字符串 coconut :

子串 nut 将是 (4,6) 。

我们在树中添加 troublemaker，(4,6) 现在可以是:

如果我们引用第一个字符串，则为

nut。

ble 如果我们指的是第二个字符串。

为了解决这个问题，我想添加一个表示字符串的 id:

// A pair of int is a substring (regular tree)
typedef std::pair<int,int> substring;
// We need to bind a substring to its reference string:
typedef std::pair<int, substring> mapped_substring;

我目前面临的问题如下:

我得到一个在树中添加字符串的查询。在算法过程中，我可能必须检查与其他注册字符串相关的现有转换，表示为三元组(引用字符串 id、k、p)。一些更新操作基于子字符串索引， 我如何在这种情况下执行它们 ？

注意:这个问题与语言无关，所以我没有包含 c++ 标签，尽管显示了一个小片段。

Answer 1

TL; 博士

编辑(03/2019):我重新设计了我的实现，以使用 C++17 string_view 来表示我的子字符串以及确保引用字符串不会移动的缓存机制。更新后的版本可以在 github 上找到:https://github.com/Rerito/suffix-tree-v2。这是好奇心的 the github for my old implementation (in C++)。哦，新版本还包括测试!

为了构建广义后缀树，实际上不需要修改原始算法。

详分割析

我的预感是正确的。为了跟上原始算法中使用的技巧，我们确实需要添加对原始字符串的引用。此外，该算法是在线的，这意味着您可以将字符串即时添加到树中。

假设我们有一个字符串 (S1, ..., SN) 的广义后缀树 GST(N)。这里的问题是如何使用 GST(N) 处理 GST(N+1) 的构建过程。

调整数据模型

在简单的情况下(单个后缀树)，每个转换都是一对(子串，结束顶点)。 Ukkonen 算法中的技巧是使用一对指向原始字符串中适当位置的指针对子字符串进行建模。在这里，我们还需要将这样的子字符串链接到它的“父”字符串。这样做:

将原始字符串存储在哈希表中，给它们一个唯一的整数键。

现在一个子串变成了:(ID, (left pointer, right pointer))。因此，我们可以使用 ID 在 O(1) 中获取原始字符串。

我们称其为映射子串。我使用的 C++ typedef 是在我的原始问题中找到的:

// This is a very basic draft of the Node class used
template <typename C>
class Node {
    typedef std::pair<int, int> substring;
    typedef std::pair<int, substring> mapped_substring;
    typedef std::pair<mapped_substring, Node*> transition;
    // C is the character type (basically `char`)
    std::unordered_map<C, transition> g; // Called g just like in the article :)
    Node *suffix_link;
};

正如您将看到的，我们也将保留引用对的概念。这一次，引用对，就像转换一样，将保存一个映射的子串。

注意:在 C++ 中，字符串索引将从 0 开始。

插入新字符串

我们想将 SN+1 插入 GST(N)。
GST(N) 可能已经有很多节点和转换。在一个简单的树中，我们只有根节点和特殊的汇节点。在这里，我们可能已经通过插入一些先前的字符串添加了 SN​​+1 的转换。要做的第一件事是沿着树向下走，只要它与 SN+1 匹配。

通过这样做，我们以状态 r 结束。这种状态可能是显式的(即我们在一个顶点上结束)或隐式的(在转换过程中发生了不匹配)。我们使用与原始算法相同的概念来模拟这样的状态:引用对。快速示例:

我们要插入SN+1 = banana

代表 ba 的节点 s 明确存在于 GST(N)

s 具有子串 nal

的转换 t

当我们沿着树向下走时，我们最终在字符 l 处的转换 t 处，这是不匹配的。因此，我们得到的隐式状态 r 由引用对 (s, m) 表示，其中 m 是映射的子串 (N+1, (1,3))。

这里， r 是算法在构建 banana 的后缀树中的第 5 次迭代的事件点。我们达到该状态的事实意味着 bana 的树已经在 GST(N) 中构建。

在这个例子中，我们在第 5 次迭代时恢复算法，使用 banan 的树构建 bana 的后缀树。为了不失一般性，我们将声明 r = (s, (N+1, (k, i-1)), i 是第一个不匹配的索引。我们确实有 k ≤ i(平等是r 是一个明确的状态)。

属性:我们可以恢复 Ukkonen 的算法，在迭代 i(插入 SN+1 中索引 i 处的字符)时构建 GST(N)。这次迭代的事件点是我们通过沿着树 向下走得到的状态 r。唯一需要调整的是一些获取操作来解析子字符串。

属性(property)证明

首先，这种状态 r 的存在意味着中间树 T(N+1)i-1 的整个状态也存在。一切就绪，我们恢复算法。

我们需要证明算法中的每个过程都是有效的。有3个这样的子程序:

test_and_split :给定要在当前迭代中插入的字符，测试我们是否需要将过渡拆分为两个单独的过渡，以及当前点是否为终点。

canonize:给定一个引用对 (n, m)，其中 n 是一个顶点，m 是一个映射的子串，返回表示相同状态的一对 (n', m')，例如 m' 是最短的可能子串。

update :更新 GST(N) 使其在运行结束时具有中间树 T(N+1)i 的所有状态。

test_and_split

输入: 一个顶点 s，一个映射的子串 m = (l, (k, p)) 和一个字符 t。
输出: 一个 bool 值，指示状态 (s, m) 是否是当前迭代的终点，如果不是终点，则节点 r 明确表示 (s, m)。

先说最简单的情况。如果子串为空 (k > p)，则状态已经明确表示。我们只需要测试我们是否到达了终点。在 GST 中，就像在普通后缀树中一样，从给定字符开始，每个节点最多有 一个转换。因此，如果有从 t 开始的转换，我们返回 true(到达终点)，否则返回 false。

现在是困难的部分，当 k ≤ p 时。我们首先需要获取原始字符串表中位于索引 l (*) 处的字符串 Sl。
让 (l', (k', p')) (resp. s') 是与以字符 Sl(k) (*) 开头的 s 的转换 TR 相关的子串(相应的节点)。之所以存在这样的转换，是因为 (s, (l,(k,p)) 表示中间树 T(N+1)i-1 的边界路径上的(存在的)隐式状态。此外，我们 确定 此转换中的 p - k 首字符匹配。

我们需要拆分这个过渡吗？这取决于此转换 (**) 上的 Δ = p - k + 第 1 个字符。为了测试这个字符，我们需要获取位于哈希表索引 l' 处的字符串，并获取索引 k' + Δ 处的字符。这个字符肯定存在，因为我们正在检查的状态是隐式的，因此在转换 TR (Δ ≤ p' - k') 的中间结束。

如果等式成立，我们无事可做并返回 true(终点在这里)并且什么都不做。如果不是，那么我们必须拆分转换并创建一个新状态 r。 TR 现在变成 (l', (k', k' + Δ - 1)) → r。为 r 创建了另一个转换:(l', (k' + Δ, p') → s'。我们现在返回 false 和 r。

(*) : l 不一定等于 N+1。同样，l和l'可以不同(或相等)。

(**) :请注意，数字 Δ = p - k + 1 根本不依赖于选择作为映射子字符串引用的字符串。它只依赖于提供给例程的隐式状态。

圣化

输入: 节点_s_和表示树中现有状态e的映射子串(l,(k,p))。
输出: 一个节点 s' 和一个映射子串 (l',(k',p'))，代表状态 e 的规范引用

使用相同的提取调整，我们只需要沿着树走下去，直到我们用尽角色“池”。在这里，就像 test_and_split 一样，每个转换的唯一性以及我们将现有状态作为输入的事实为我们提供了一个有效的过程。

更新

输入: 当前迭代的事件点和索引。
输出: 下一次迭代的事件点。
update 使用对 GST 友好的 canonize 和 test_and_split。后缀链接编辑与普通树的编辑完全相同。唯一需要注意的是，我们将使用 SN+1 作为引用字符串创建开放转换(即通向节点的转换)。因此，在迭代 i 时，转换将始终链接到映射子串 (N+1,(i,∞))

最后一步

我们需要“关闭”开放的转换。为此，我们只需遍历它们并编辑 ∞ ，将其替换为 L-1，其中 L 是 SN+1 的长度。我们还需要一个哨兵字符来标记字符串的结尾。我们肯定不会在任何字符串中遇到的字符。这样，叶子将永远保持叶子。

结论

额外的获取工作增加了一些 O(1) 操作，稍微增加了复杂性的常数因子。但是，渐近复杂度与插入字符串的长度显然保持线性关系。因此，从长度为 n1,...,nN 的字符串 (S1,..., SN) 构建 GST(N) 是:

c(GST(N)) = Σ_i=1..N n_i