Rer*_*ito 10 algorithm suffix-tree
我目前正在开发自己的Suffix Tree实现(使用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 ++ -tag,尽管显示了一些小片段.
为了构建通用后缀树,不需要修改原始算法.
这是我当前实现的github(在C++中).它仍然需要一些审查和重构(以及一些广泛的测试...)但它是一个开始!
注意:我目前正在开发这个实现,当我可以使用它时,我会用这些东西更新这个答案!(Coliru生活之类......)
我得到的预感是正确的方式.为了跟上原始算法中使用的技巧,我们确实需要添加对原始字符串的引用.此外,该算法是在线的,这意味着您可以即时向树中添加字符串.
假设我们有一个广义后缀树 GST(ñ)的字符串(小号1,...,S ñ).这里的问题是如何使用GST(N)处理GST(N + 1)的构建过程.
在简单的情况下(单个后缀树),每个转换是一对(子串,末端顶点).Ukkonen算法的技巧是使用一对指向原始字符串中适当位置的指针对子字符串进行建模.在这里,我们还需要将这样的子字符串链接到其"父" 字符串.为此:
我们将其称为映射子字符串.我使用的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开始.
我们想要将S N + 1插入GST(N).
GST(N)可能已经有很多节点和转换.在一个简单的树中,我们只有root和特殊的sink节点.在这里,我们可能已经通过插入一些先前的字符串添加了S N + 1的转换.首先要做的是,只要它与S N + 1匹配,就可以沿树向下穿过过渡.
通过这样做,我们以状态r结束.此状态可以是显式的(即,我们在顶点上结束)或隐式(在转换的中间发生不匹配).我们使用与原始算法中相同的概念来模拟这样的状态:参考对.快速举例:
string_viewbanana 明确地在GST存在(Ñ)ba当我们走在树,我们在过渡结束牛逼的人物nal是不匹配的.因此,我们得到的隐式状态r由参考对(s,m)表示,其中m是映射的子串(N + 1,(1,3)).
这里,r是构建l后缀树时算法的第5次迭代的活动点.我们到达那个状态的事实恰恰意味着树banana已经建立在GST(N)中.
在这个例子中,我们在第5次迭代中恢复算法,以构建bana使用树的后缀树banan.不丧失一般性,我们将状态[R = (S,(N + 1,(K,I-1)) ,我是第一个不匹配的索引.我们确实ķ≤我(该egality是同义词r是一个明确的状态).
属性:我们可以恢复Ukkonen的算法,在迭代i中构建GST(N)(在S N + 1中插入索引i处的字符).这次迭代的活跃点是我们通过走在树上获得的状态r.唯一需要调整的是一些解析子串的提取操作.
首先,这种状态r的存在意味着中间树T(N + 1)i-1的整个状态也在那里.所以一切都已建立,我们恢复算法.
我们需要证明算法中的每个过程都是有效的.有3个这样的子程序:
bana:给定要在当前迭代中插入的字符,测试我们需要将转换分成两个单独的转换,如果当前点是结束点.test_and_split:给定一个引用对 (n,m),其中n是顶点,m是映射的子串,返回表示相同状态的对(n',m'),例如m'是最短的子串.canonize:更新GST(N),使其在运行结束时具有中间树T(N + 1)i的所有状态.输入:顶点s,映射的子串m =(l,(k,p))和字符t.
输出:一个布尔值,它告诉状态(s,m)是当前迭代的结束点,还是一个节点r表示显式(s,m),如果它不是终点.
最简单的情况首先.如果子字符串为空(k> p),则状态已经明确表示.我们只需要测试我们是否达到了终点.在消费税,就像在一个共同的后缀树,还有总是先从给定的人物每个节点至多有一个过渡.因此,如果存在以t开始的转换,则返回true(我们到达终点),否则返回false.
现在是困难的部分,当k≤p.我们首先需要获取位于原始字符串表中索引l (*)的字符串S l.
令(l',(k',p'))(相应的s')是与以字符S l(k)(*)开始的s的转变TR相关的子串(相应的节点).这样的过渡的存在是因为(S,(1,(K,P))表示上的(现有的)隐式状态边界路径的中间树T(N + 1)I-1 .此外,我们确定的是,p -此转换的第一个字符匹配.
我们需要分裂这种转变吗？这取决于此转换(**)上的Δ= 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的规范参考
使用相同的提取调整,我们只需要走下树,直到我们用尽了字符"池".在这里,就像update每个转换的唯一性以及我们将现有状态作为输入这一事实为我们提供了有效的过程.
输入:当前迭代的活动点和索引.
输出:下一次迭代的活动点.
test_and_split同时使用update以及canonize它们是GST友好.后缀链接编辑与公共树的编辑完全相同.唯一需要注意的是,我们将使用S N + 1作为参考字符串创建开放转换(即通向节点的转换).因此,在迭代i,转换将始终链接到映射的子串(N + 1,(i,∞))
我们需要"关闭" 开放的过渡.为此,我们只是遍历它们并编辑∞,用L-1替换它,其中L是S N + 1的长度.我们还需要一个标记字符来标记字符串的结尾.我们肯定永远不会在任何字符串中遇到的角色.这样,叶子将永远留下叶子.
额外的读取工作增加了一些O(1)操作,增加了一点复杂性的常数因素.但是,渐近复杂度与插入的字符串的长度保持明显的线性关系.因此,从长度为n 1,...,n N的字符串(S 1,...,S N)构建GST(N)是:
c(GST(N))= Σi = 1..N n i