Ukkonen 的广义后缀树算法
Ukkonen's algorithm for Generalized Suffix Trees
我目前正在研究自己的后缀树实现（使用 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++ 标签，尽管显示了一小段。
TL;DR
编辑 (03/2019): 我重新设计了我的实现以使用 C++17 string_view 来表示我的子字符串以及确保参考字符串不会四处移动。更新版本可以在 github: https://github.com/Rerito/suffix-tree-v2. Here is the github for my old implementation (in C++) 上找到，供好奇的人使用。哦，新课程还包括测试！
为了构建广义后缀树.
，实际上不需要修改原始算法
详细分析
我的预感是正确的方法。为了跟上原始算法中使用的技巧，我们确实需要添加对原始字符串的引用。此外，该算法是 在线，这意味着您可以即时将字符串添加到树中。
假设我们有一个 广义后缀树 GST(N) 用于字符串 (S 1, ..., SN)。这里的问题是如何处理GST(N+1)的构建过程，使用GST(N).
调整数据模型
在简单的情况下（单个后缀树），每个转换都是一对（子串，结束顶点）。 Ukkonen 算法中的技巧是使用一对指向原始字符串中适当位置的指针来模拟子字符串。在这里，我们还需要link这样一个子串到它的"parent"串。为此：
- 将原始字符串存储在散列中 table，为它们提供唯一的整数键。
- 一个子串现在变成：(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
- 一个节点s表示
ba显式存在于GST(N )
- s 对子字符串
nal 有一个转换 t
当我们沿着树向下走时，我们最终在字符 l 处的转换 t 处结束，这是不匹配的。因此，我们得到的隐式状态r由参考对表示（s，m) 其中 m 是映射子字符串 (N+1, (1,3)).
这里，r是算法在banana的后缀树构建过程中第5次迭代的活跃点。我们达到该状态的事实恰恰意味着 bana 的树已经构建在 GST(N).
中
在这个例子中，我们在第 5 次迭代时恢复算法，使用 bana 的树为 banan 构建后缀树。为了不失一般性，我们将声明 r = (s, (N+1, (k, i-1)), i 是第一个不匹配的索引。我们确实有 k ≤ i （等式是 r[=274= 的同义词] 是一个显式状态）。
属性：我们可以在 i 迭代中恢复 Ukkonen 的算法来构建 GST(N) （在 SN+1 中索引 i 处插入字符）。本次迭代的活跃点是我们沿着树走下去得到的状态r。 唯一需要调整的是一些获取操作来解析子字符串。
证明 属性
首先，这种状态r的存在意味着中间树的整个状态T(N+1)i -1 也在那里。一切就绪，我们继续算法。
我们需要证明算法中的每个过程仍然有效。有3个这样的子程序：
test_and_split：给定要在当前迭代中插入的字符，测试我们是否需要将一个转换拆分为两个单独的转换以及当前点是否为终点。canonize：给定一个参考对 (n, m) 其中n 是一个顶点，m 是一个映射子串，returns 这对 (n', m') 表示相同的状态例如m'是最短的子串。update：更新 GST(N) 使其具有中间树的所有状态 T(N+1)i结尾的运行.
test_and_split
输入：一个顶点s，一个映射子串m = (l, (k, p)) 和一个字符 t.
输出： 一个布尔值，表明状态 (s, m) 是否是当前迭代的终点和节点 r 明确表示 (s, m) 如果它不是终点。
最简单的情况优先。如果子字符串为空 (k > p)，则状态已明确表示。我们只需要测试是否到达终点。 在 GST 中，就像在普通后缀树中一样，每个以给定字符开头的节点最多 总是 一个转换。 因此，如果有一个从 t 开始的转换，我们 return 为真（我们到达终点），否则为假。
现在是困难的部分，当 k ≤ p 时。我们首先需要获取位于索引 l(* ) 原始字符串 table.
设 (l', (k', p')) (resp. s') 为与相关的子串（resp. 节点）以字符 Sl(k)[ 开头的 s 的转换 TR =274=] (*)。存在这样的转换是因为 (s, (l,(k,p)) 表示 边界路径 上的（现有）隐式状态中间树 T(N+1)i-1。此外，我们确定 p - k 此转换的第一个字符匹配。
我们需要拆分这个过渡吗？这取决于此转换 (**) 上的第 Δ = p - k + 1 个字符。为了测试这个字符，我们需要获取索引 l' 上的字符串 table 并获取索引 k' + Δ[ 处的字符=274=]。这个字符肯定存在，因为我们正在检查的状态是隐式的，因此在转换的中间结束 TR (Δ ≤ p' - k').
如果等式成立，我们什么也不做，return为真（终点在这里），什么都不做。如果不是，那么我们必须拆分转换并创建一个新状态 r。 TR 现在变为 (l', (k', k' + Δ - 1)) → r。为 r 创建另一个转换：(l', (k' + Δ, p') → s'。我们现在 return false 和 r.
(*)：l不一定等于N+1。同样，l 和 l' 可能不同（或相等）。
(**)：请注意数字 Δ = p - k + 1 完全不依赖于所选字符串作为映射子字符串的参考。它仅取决于 隐式状态 提供给例程。
封圣
输入：一个节点_s_and一个映射的子串(l,(k,p))表示一个存在的状态e 在树中。
输出：一个节点s'和一个映射子串(l',(k',p')) 表示状态 e
的规范引用
使用相同的抓取调整，我们只需要沿着树向下走，直到我们 耗尽 字符 "pool"。在这里，就像 test_and_split 每个转换的唯一性以及我们有一个现有状态作为输入的事实为我们提供了一个有效的过程。
更新
输入：当前迭代的活动点和索引。
输出：下一次迭代的活动点。
update 同时使用 canonize 和 test_and_split，它们 GST 友好 。后缀 link 编辑与普通树完全相同。唯一需要注意的是，我们将使用 SN+1[=279= 创建 open transitions（即通向节点的转换） ] 作为参考字符串。因此，在迭代 i 时，转换总是 linked 到映射的子串 (N+1,(i,∞))
最后一步
我们需要"close" 打开转换。为此，我们只需遍历它们并编辑掉 ∞ ，将其替换为 L-1，其中 L 是 [=107 的长度=]SN+1。我们还需要一个哨兵字符来标记字符串的结尾。我们肯定不会在任何字符串中遇到的字符。这样叶子就永远是叶子了。
结论
额外的获取工作增加了一些 O(1) 操作，稍微增加了复杂度的常数因子。但是，渐近复杂度显然与插入字符串的长度呈线性关系。因此，从字符串构建 GST(N) (S1,..., SN) 长度为 n1,...,nN 是：
c(GST(N)) = Σi=1..N ni
如果您的广义后缀树中只有几个字符串，那么您可以在每个字符串之间使用唯一的终结符（这些终结符不应在输入字符串中使用）将它们连接成一个字符串。
例如，假设您有 5 个字符串：str1、str2、str3、str4 和 str5，那么您可以将这 5 个字符串连接为 str1$str2#str3@str4%str5，然后制作一个后缀树连接字符串。
由于我们必须使用唯一的终端符号，因此在通用后缀树中可以添加的最大字符串数量会有限制。任何永远不会在输入字符串中使用的字符都可以作为终端符号。
因此，基于一组预定义的终端符号，我们可以编写代码。
以下文章可能会有所帮助。
我目前正在研究自己的后缀树实现（使用 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++ 标签，尽管显示了一小段。
TL;DR
编辑 (03/2019): 我重新设计了我的实现以使用 C++17 string_view 来表示我的子字符串以及确保参考字符串不会四处移动。更新版本可以在 github: https://github.com/Rerito/suffix-tree-v2. Here is the github for my old implementation (in C++) 上找到，供好奇的人使用。哦，新课程还包括测试！
为了构建广义后缀树.
，实际上不需要修改原始算法详细分析
我的预感是正确的方法。为了跟上原始算法中使用的技巧，我们确实需要添加对原始字符串的引用。此外，该算法是 在线，这意味着您可以即时将字符串添加到树中。
假设我们有一个 广义后缀树 GST(N) 用于字符串 (S 1, ..., SN)。这里的问题是如何处理GST(N+1)的构建过程，使用GST(N).
调整数据模型
在简单的情况下（单个后缀树），每个转换都是一对（子串，结束顶点）。 Ukkonen 算法中的技巧是使用一对指向原始字符串中适当位置的指针来模拟子字符串。在这里，我们还需要link这样一个子串到它的"parent"串。为此：
- 将原始字符串存储在散列中 table，为它们提供唯一的整数键。
- 一个子串现在变成：(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 - 一个节点s表示
ba显式存在于GST(N ) - s 对子字符串
nal 有一个转换 t
当我们沿着树向下走时，我们最终在字符 l 处的转换 t 处结束，这是不匹配的。因此，我们得到的隐式状态r由参考对表示（s，m) 其中 m 是映射子字符串 (N+1, (1,3)).
这里，r是算法在banana的后缀树构建过程中第5次迭代的活跃点。我们达到该状态的事实恰恰意味着 bana 的树已经构建在 GST(N).
在这个例子中，我们在第 5 次迭代时恢复算法，使用 bana 的树为 banan 构建后缀树。为了不失一般性，我们将声明 r = (s, (N+1, (k, i-1)), i 是第一个不匹配的索引。我们确实有 k ≤ i （等式是 r[=274= 的同义词] 是一个显式状态）。
属性：我们可以在 i 迭代中恢复 Ukkonen 的算法来构建 GST(N) （在 SN+1 中索引 i 处插入字符）。本次迭代的活跃点是我们沿着树走下去得到的状态r。 唯一需要调整的是一些获取操作来解析子字符串。
证明 属性
首先，这种状态r的存在意味着中间树的整个状态T(N+1)i -1 也在那里。一切就绪，我们继续算法。
我们需要证明算法中的每个过程仍然有效。有3个这样的子程序：
test_and_split：给定要在当前迭代中插入的字符，测试我们是否需要将一个转换拆分为两个单独的转换以及当前点是否为终点。canonize：给定一个参考对 (n, m) 其中n 是一个顶点，m 是一个映射子串，returns 这对 (n', m') 表示相同的状态例如m'是最短的子串。update：更新 GST(N) 使其具有中间树的所有状态 T(N+1)i结尾的运行.
test_and_split
输入：一个顶点s，一个映射子串m = (l, (k, p)) 和一个字符 t.
输出： 一个布尔值，表明状态 (s, m) 是否是当前迭代的终点和节点 r 明确表示 (s, m) 如果它不是终点。
最简单的情况优先。如果子字符串为空 (k > p)，则状态已明确表示。我们只需要测试是否到达终点。 在 GST 中，就像在普通后缀树中一样，每个以给定字符开头的节点最多 总是 一个转换。 因此，如果有一个从 t 开始的转换，我们 return 为真（我们到达终点），否则为假。
现在是困难的部分，当 k ≤ p 时。我们首先需要获取位于索引 l(* ) 原始字符串 table.
设 (l', (k', p')) (resp. s') 为与相关的子串（resp. 节点）以字符 Sl(k)[ 开头的 s 的转换 TR =274=] (*)。存在这样的转换是因为 (s, (l,(k,p)) 表示 边界路径 上的（现有）隐式状态中间树 T(N+1)i-1。此外，我们确定 p - k 此转换的第一个字符匹配。
我们需要拆分这个过渡吗？这取决于此转换 (**) 上的第 Δ = p - k + 1 个字符。为了测试这个字符，我们需要获取索引 l' 上的字符串 table 并获取索引 k' + Δ[ 处的字符=274=]。这个字符肯定存在，因为我们正在检查的状态是隐式的，因此在转换的中间结束 TR (Δ ≤ p' - k').
如果等式成立，我们什么也不做，return为真（终点在这里），什么都不做。如果不是，那么我们必须拆分转换并创建一个新状态 r。 TR 现在变为 (l', (k', k' + Δ - 1)) → r。为 r 创建另一个转换：(l', (k' + Δ, p') → s'。我们现在 return false 和 r.
(*)：l不一定等于N+1。同样，l 和 l' 可能不同（或相等）。
(**)：请注意数字 Δ = p - k + 1 完全不依赖于所选字符串作为映射子字符串的参考。它仅取决于 隐式状态 提供给例程。
封圣
输入：一个节点_s_and一个映射的子串(l,(k,p))表示一个存在的状态e 在树中。
输出：一个节点s'和一个映射子串(l',(k',p')) 表示状态 e
使用相同的抓取调整，我们只需要沿着树向下走，直到我们 耗尽 字符 "pool"。在这里，就像 test_and_split 每个转换的唯一性以及我们有一个现有状态作为输入的事实为我们提供了一个有效的过程。
更新
输入：当前迭代的活动点和索引。
输出：下一次迭代的活动点。
update 同时使用 canonize 和 test_and_split，它们 GST 友好 。后缀 link 编辑与普通树完全相同。唯一需要注意的是，我们将使用 SN+1[=279= 创建 open transitions（即通向节点的转换） ] 作为参考字符串。因此，在迭代 i 时，转换总是 linked 到映射的子串 (N+1,(i,∞))
最后一步
我们需要"close" 打开转换。为此，我们只需遍历它们并编辑掉 ∞ ，将其替换为 L-1，其中 L 是 [=107 的长度=]SN+1。我们还需要一个哨兵字符来标记字符串的结尾。我们肯定不会在任何字符串中遇到的字符。这样叶子就永远是叶子了。
结论
额外的获取工作增加了一些 O(1) 操作，稍微增加了复杂度的常数因子。但是，渐近复杂度显然与插入字符串的长度呈线性关系。因此，从字符串构建 GST(N) (S1,..., SN) 长度为 n1,...,nN 是：
c(GST(N)) = Σi=1..N ni
如果您的广义后缀树中只有几个字符串，那么您可以在每个字符串之间使用唯一的终结符（这些终结符不应在输入字符串中使用）将它们连接成一个字符串。
例如，假设您有 5 个字符串：str1、str2、str3、str4 和 str5，那么您可以将这 5 个字符串连接为 str1$str2#str3@str4%str5，然后制作一个后缀树连接字符串。
由于我们必须使用唯一的终端符号，因此在通用后缀树中可以添加的最大字符串数量会有限制。任何永远不会在输入字符串中使用的字符都可以作为终端符号。
因此，基于一组预定义的终端符号，我们可以编写代码。
以下文章可能会有所帮助。