首页 文章

Ukkonen的广义后缀树算法

提问于
浏览 次
10

我目前正在开发自己的Suffix Tree实现（使用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） . 一些更新操作基于子串索引， how can I perform them in such conditions ？

注意：这个问题与语言无关，所以我没有包含c++ -tag，尽管显示了一些小片段 .

algorithm suffix-tree

2 回答

  • 0

    TL; DR

    编辑（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算法的技巧是使用一对指向原始字符串中适当位置的指针对子字符串进行建模 . 在这里，我们还需要将这样的子字符串链接到它的"parent"字符串 . 为此：

    • 将原始字符串存储在哈希表中，为它们提供唯一的整数键 .

    • 现在变为子串：（ID，（左指针，右指针）） . 因此我们可以使用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）可能已经有很多节点和转换 . 在一个简单的树中，我们只有root和特殊的sink节点 . 在这里，我们可能已经通过插入一些先前的字符串添加了SN 1的转换 . 首先要做的是，只要它与SN 1匹配，就可以沿树向下穿过过渡 .

    通过这样做，我们以状态r结束 . 该状态可以是显式的（即，我们在顶点上正好结束）或隐式的（在转换的中间发生不匹配） . 我们使用与原始算法中相同的概念来模拟这样的状态：参考对 . 快速举例：

    • 我们要插入SN 1 = banana

    • GST（N）中明确存在表示 ba 的节点

    • 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的同义词是一个明确的国家） .

    Property: We can resume Ukkonen's algorithm to build GST(N) at iteration i (insertion of the character at index i in SN+1). The active point for this iteration is the state r we got by walking down the tree . 唯一需要调整的是一些解析子串的提取操作 .

    该 properties 的证明

    首先，这种状态r的存在意味着中间树T（N 1）i-1的整个状态也在那里 . 所以一切都已 Build ，我们恢复算法 .

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

    • test_and_split ：给定要在当前迭代中插入的字符，测试我们需要将转换拆分为两个单独的转换，如果当前点是终点 .

    • canonize ：给定一个引用对（n，m），其中n是顶点，m是映射的子字符串，返回表示相同状态的对（n ', m'），例如m'是最短的子字符串 .

    • update ：更新GST（N），使其在运行结束时具有中间树T（N 1）i的所有状态 .

    test_and_split

    Input: 顶点s，映射的子串m =（l，（k，p））和字符t .
    Output: 一个布尔值，它告诉状态（s，m）是否是当前迭代的终点，而节点r是否显式表示（s，m），如果它不是终点 .

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

    现在是困难的部分，当k≤p . 我们首先需要获取原始字符串表中索引为l (*) 的字符串S1 .
    令（l ', (k'，p'））（相应的s'）是与以字符S1（k） (*) 开始的s的转变TR相关的子串（相应的节点） . 存在这样的转变是因为（s，（l，（k，p））表示中间树T（N 1）i-1的边界路径上的（现有的）隐式状态 . 此外，我们是 sure ，即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完全不依赖于选择作为映射子字符串的引用的字符串 . 它只取决于提供给例程的隐式状态 .

    Canonize

    Input: 节点_s_和表示树中现有状态e的映射子字符串（l，（k，p）） .
    Output: 节点s'和映射的子字符串（l ',(k'，p'））表示状态e的规范参考

    使用相同的提取调整，我们只需要走下树直到我们已经用尽了字符"pool" . 在这里，就像 test_and_split 每个转换的唯一性以及我们将现有状态作为输入的事实为我们提供了有效的过程 .

    更新

    Input: 当前迭代的活动点和索引 .
    Output: 下一次迭代的活动点 .

    update 同时使用 canonize 和 test_and_split 这些都是GST友好的 . 后缀链接编辑与公共树的编辑完全相同 . 唯一需要注意的是，我们将使用SN 1作为参考字符串来创建开放转换（即通向节点的转换） . 因此，在迭代i，转换将始终链接到映射的子串（N 1，（i，∞））

    最后一步

    我们需要"close"开放过渡 . 为此，我们只是遍历它们并编辑∞远，用L-1替换它，其中L是SN 1的长度 . 我们还需要一个标记字符来标记字符串的结尾 . 我们肯定永远不会在任何字符串中遇到的角色 . 这样，叶子将永远留下叶子 .

    结论

    额外的读取工作增加了一些O（1）操作，增加了一点复杂性的常数因素 . 但是，渐近复杂度与插入的字符串的长度保持明显的线性关系 . 因此，从长度为n1，...，nN的字符串（S1，...，SN）构建GST（N）是：

    c（GST（N））=Σi= 1..N ni

    回复于
  • 6

    如果你的通用后缀树中只有几个字符串，那么你可以使用每个字符串之间的唯一终端符号（这些终端符号不应该在输入字符串中使用）在一个字符串中将它们连接在一起 .

    例如，假设您有5个字符串：str1，str2，str3，str4和str5，那么您可以将这5个字符串连接为str1 $ str2＃str3 @ str4％str5，然后创建此连接字符串的后缀树 .

    由于我们必须使用唯一的终端符号，因此在广义后缀树中可以添加的最大字符串数量会受到限制 . 任何永远不会在输入字符串中使用的字符都可以作为终端符号 .

    因此，基于一组预定义的终端符号，我们可以编写代码 .

    以下文章可能会有所帮助 .

    Generalized Suffix Tree

    回复于

相关问题