标签: suffix-tree

对于上下文,我编写了这个算法来获取任何字符串的唯一子串的数量.它为计算其包含的节点的字符串构建后缀树,并将其作为答案返回.我想要解决的问题需要一个O(n)算法,所以这个问题只是关于这个代码的行为方式,而不是关于它的作用有多糟糕.

struct node{
    char value = ' ';
    vector<node*> children;
    ~node()
    {
        for (node* child: children)
        {
            delete child;
        }
    }
};

int numberOfUniqueSubstrings(string aString, node*& root)
{
    root = new node();
    int substrings = 0;
    for (int i = 0; i < aString.size(); ++i)
    {
        string tmp = aString.substr(i, aString.size());
        node* currentNode = root;
        char indexToNext = 0;
        for (int j = 0; j < currentNode->children.size(); ++j)
        {
            if (currentNode->children[j]->value == tmp[indexToNext])
            {
                currentNode = currentNode->children[j];
                j …

我只想知道,当后缀树优于增强后缀数组时.

在阅读了使用增强的suf fi x数组替换suf fi x树之后,我再也看不到使用后缀树的理由了.有些方法可能会变得复杂,但您可以使用后缀数组执行所有操作,使用后缀树可以执行的操作,并且需要相同的时间复杂度但内存较少.

一项调查甚至表明,后缀数组更快,因为它们缓存更友好,并且不会产生更多的缓存未命中,然后产生后缀树(因此缓存可以更好地预测数组使用,然后在递归树结构上).

那么,有没有人知道在后缀数组上选择后缀树的原因？

编辑 好的,如果你知道更多告诉我,到目前为止:

• 后缀不允许在线构造
• 一些模式匹配算法在Suffixtrees上运行得更快
• (补充)由于在线构造,你可以将它保存在高清上并扩大现有的后缀树.如果你使用SSD,它也应该安静快速.

我正在寻找具有以下功能的广义后缀树(GST)的Java实现:

从1000个字符串创建GST之后,我想知道这1000个字符串中有多少包含其他字符串''.

搜索必须快速安静,因为我需要在大约100'000个平均长度为10的候选字符串上应用搜索.

本文讨论了使用后缀树来改善匹配时间的近似子串匹配技术.每个答案都针对不同的算法.

1. 近似子字符串匹配尝试在字符串中查找子字符串(模式)P,以T允许最多k不匹配.
2. 要了解如何创建后缀树,请单击此处.但是,某些算法需要额外的预处理.

我邀请人们添加新算法(即使它不完整)并改进答案.

我已经实施了一个研究项目的基本搜索.我试图通过构建后缀树来提高搜索效率.我对Ukkonen算法的C#实现很感兴趣.如果存在这样的实现,我不想浪费时间自己动手.

我需要在String中找到最长的非重叠重复子字符串.我有可用字符串的后缀树和后缀数组.

当允许重叠时,答案是微不足道的(后缀树中最深的父节点).

例如对于String ="acaca"

如果允许重叠,则回答是"aca"但是当不允许重叠时,回答是"ac"或"ca".

我只需要算法或高级想法.

PS:我试过,但我在网上找不到明确的答案.

摘自编程珍珠第15.2节

可在此处查看C代码:http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

当我使用suffix-array在Python中实现它时:

example = open("iliad10.txt").read()
def comlen(p, q):
    i = 0
    for x in zip(p, q):
        if x[0] == x[1]:
            i += 1
        else:
            break
    return i

suffix_list = []
example_len = len(example)
idx = list(range(example_len))
idx.sort(cmp = lambda a, b: cmp(example[a:], example[b:]))  #VERY VERY SLOW

max_len = -1
for i in range(example_len - 1):
    this_len = comlen(example[idx[i]:], example[idx[i+1]:])
    print this_len
    if this_len > max_len:
        max_len = this_len
        maxi = i

我发现这idx.sort一步很慢.我认为它很慢,因为Python需要通过值而不是指针传递子串(如上面的C代码).

测试文件可以从这里 …

解决这个问题的最佳方法(性能方面)是什么？我被建议使用后缀树.这是最好的方法吗？

是否存在从字符串S [1..m] 的后缀树生成字符串S [2..m]的后缀树的快速(O(1)时间复杂度)方法？

我熟悉Ukkonen的,所以我知道如何从字符串S [1..m]的后缀树制作字符串S [1..m + 1]的快速后缀树,但我不能将该算法用于反向情况.

我目前正在开发自己的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,尽管显示了一些小片段.