用于广义后缀树的Ukkonen算法
我目前正在研究自己的后缀树实现（使用C ++，但问题仍然是语言不可知的）。 我研究了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
为了构建通用后缀树，原始算法并不需要进行修改。
这是我当前实现的github（使用C ++）。 它仍然需要一些审查和重构（以及一些广泛的测试......），但这是一个开始！
注意：我目前正在研究这个实现，当我有了它的时候，我会用这些东西更新这个答案！ （Coliru活着，等等......）
详细分析
我得到的预感是正确的。 为了跟上原始算法中使用的技巧，我们确实需要添加对原始字符串的引用。 此外，该算法在线，这意味着您可以将字符串即时添加到树中。
假设对于字符串（S1，...，SN）我们有一个广义后缀树GST（N）。 这里的问题在于如何使用GST（N）来处理GST（N + 1）的构建过程。
调整数据模型
在简单情况下（单个后缀树），每个转换都是一对（substring，end vertex）。 Ukkonen算法中的诀窍是使用一对指向原始字符串中适当位置的指针对子串进行建模。 在这里，我们还需要将这样一个子字符串链接到它的“父”字符串。 要做到这一点：
我们称之为映射子串。 我使用的C ++ typedefs是在我原来的问题中找到的：
// 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状态结束。 这种状态可能是明确的（即我们终止在一个顶点上）或隐式的（在转换过程中出现不匹配）。 我们使用与原始算法相同的概念来模拟这种状态：参考对。 快速示例：
banana ba的节点明确存在于GST（N） 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（egality是r是一个明确的状态）。
属性：我们可以恢复Ukkonen的算法在迭代i中建立GST（N）（在SN + 1中将索引i处的字符插入）。 这个迭代的活动点是我们沿着树走过的状态 。 唯一需要调整的是一些提取操作来解析子字符串。
证明财产
首先，这种状态r的存在意味着中间树T（N + 1）i-1的整个状态也在那里。 因此，所有设置，我们恢复算法。
我们需要证明算法中的每个过程都是有效的。 有3个这样的子程序：
test_and_split ：给定要在当前迭代插入的字符，测试我们需要将转换分成两个单独的转换，并且如果当前点是终点。 canonize ：给定一个参考对（n，m），其中n是顶点和ma映射的子串，返回表示相同状态的对（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开始的转换，我们返回true（我们到达终点），否则返回false。
当k≤p时，现在是困难的部分。 我们首先需要获取位于原始字符串表中索引为l （*）的字符串S1。
令（1'，（k'，p'））（或s'）为与字符S1（k） （*）开始的s的转变TR有关的子串（或节点） 。 这样的转换存在是因为（s，（l，（k，p））表示中间树T（N + 1）i-1的边界路径上的一个（存在的）隐式状态，并且我们确信 p - 此转换中k个首字符匹配。
我们是否需要分裂这种转变？ 这取决于此转换（**）上的Δ= p - k + 1个字符。 为了测试这个字符，我们需要获取位于散列表索引l'处的字符串并获取索引k'+Δ处的字符。 这个字符保证存在，因为我们正在检查的状态是隐含的，因此在转换TR（Δ≤p'-k'）的中间结束。
如果平等成立，我们无事可做，并且返回真实（终点在这里）并且别无其他。 如果不是，那么我们必须拆分过渡并创建一个新的状态r。 TR现在变成（l'，（k'，k'+Δ-1））→r。 另一个转换是为r：（l'，（k'+Δ，p'）→s'）创建的，我们现在返回false和r。
（*） ：l不一定等于N + 1。 同样，l和l'可能不同（或相等）。
（**） ：请注意，Δ= p - k + 1的数字完全不依赖于被选作映射子串的引用的字符串。 它只依赖于例程中的隐式状态。
长期委任
输入：表示树中现有状态e的节点_s_和映射子串（l，（k，p））。
输出：表示状态e的规范参考的节点s'和映射的子串（l'，（k'，p'））
使用相同的提取调整，我们只需要走下树，直到我们已经用尽了字符“池”。 在这里，就像test_and_split每个转换的test_and_split性以及我们现有状态作为输入的事实为我们提供了一个有效的过程。
更新
输入：当前迭代的活动点和索引。
输出：下一次迭代的激活点。
update同时使用canonize和test_and_split这是GST友好。 后缀链接编辑与普通树的编辑完全相同。 唯一需要注意的是，我们将使用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 ni
如果您的广义后缀树只包含少量字符串，则可以在每个字符串之间使用唯一的终端符号（这些终端符号不应用于输入字符串中）将它们连接在一起形成单个字符串。
例如，假设您有5个字符串：str1，str2，str3，str4和str5，则可以将这5个字符串连接为str1 $ str2＃str3 @ str4％str5，然后为该连接字符串创建一个后缀树。
由于我们必须使用唯一的终端符号，因此会限制在通用后缀树中可以添加多少最大字符串。 永远不会在输入字符串中使用的任何字符都可以作为终端符号。
因此，根据预定义的一组终端符号，我们可以编写代码。
以下文章可能会有所帮助。
广义后缀树
链接地址: http://www.djcxy.com/p/40097.html