在一个巨大的字符串中发现长重复的子字符串

我天真地想象到，我可以建立一个后缀trie，我为每个节点保留一个访问计数，然后计数大于1的最深节点是我正在查找的结果集对于。在一个巨大的字符串中发现长重复的子字符串

我有一个非常长的字符串（数百兆字节）。我有大约1 GB的RAM。

这就是为什么使用计数数据构建后缀特里结构对于我而言效率太低的太空效率。引用Wikipedia's Suffix tree：

存储字符串的后缀树通常需要比存储字符串本身更多的空间。

每个边缘和节点中的大量信息使得后缀树非常昂贵，在良好的实现中消耗大约十到二十倍的源文本的内存大小。后缀数组将这一要求降低到四分之一，研究人员继续寻找较小的索引结构。

这就是维基百科对树的评论，而不是trie。

如何在如此大量的数据中以及在合理的时间内（例如，在现代台式机上少于一个小时）找到长的重复序列？

（有些维基百科的链接，以避免人张贴的“答案”：Algorithms on strings，尤其是Longest repeated substring problem ;-)）

来源

2008-12-29 Will

FWIW，这里有一个相关的问题，我写了SpamAssassin的的实现，可能是有用的：http://taint.org/2007/03/05/ 134447a.html – 2010-05-07 11:43:46

执行此操作的有效方法是创建子字符串的索引并对它们进行排序。这是一个O（n lg n）操作。

BWT压缩执行此步骤，因此它是一个很好理解的问题，并且存在基数和suffix（声明O（n））排序实现等，以使其尽可能高效。它仍然需要很长时间，也许几秒钟的大文本。

如果你想使用的工具代码，C++ std::stable_sort()执行多比std::sort()更好地为自然语言（而不是C的qsort()快得多，但出于不同的原因）。

然后访问每个项目以查看其邻居的公共子字符串的长度是O（n）。

来源

2009-11-25 11:29:09 Will

这是文本与断字？然后，我怀疑你想要一个关键字在上下文中的变体：为每行中的n个单词制作n行每行的副本，在每个单词上打破每行;排序整个事物的阿尔法;寻找重复。

如果它是一个单一的长鸣号字符串，就像说生物信息学DNA序列一样，那么你想要在磁盘上构建类似于你的trie的东西;用下一个节点的磁盘偏移量为每个字符创建记录。我会看看Knuth的第3卷第5.4节“外部排序”。

来源

2008-12-29 22:08:19

-1

最简单的方法可能只是为plunk down the $100更多的RAM。否则，您可能需要查看磁盘支持的结构来保存后缀树。

来源

2008-12-29 22:08:24 Eclipse

你可以看看基于磁盘的后缀树。我通过谷歌发现了这个Suffix tree implementation library，以及一些可以帮助你自己实现的文章。

来源

2008-12-29 22:16:35 orip

Ukkonen后缀树算法（http://en.wikipedia.org/wiki/Suffix_tree）*非常漂亮。 – 2008-12-29 22:41:50

您可以通过建立suffix array来解决您的问题吗？否则，您可能需要使用其他答案中提到的其中一种基于磁盘的后缀树。

来源

2008-12-29 22:20:52

你可以用分而治之来解决这个问题。我想，这应该是相同的算法复杂度，使用特里，但也许不太有效的实现明智

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
}

在此之后，你需要做的是落实DiskBackedBuffer，以致于它号码列表类，当缓冲区达到一定的大小时，它会使用临时文件将自己写入磁盘，并在读取时从磁盘读取。

来源

2008-12-29 22:38:14 FryGuy

回答我的问题：

由于长时间的比赛也只有很短的比赛，你可以通过首先找到短的比赛，然后看如果你可以“长大”这些比赛交易多种通行证RAM。

对此的文字方法是在数据中构建一个固定长度的所有序列的trie（每个节点都有计数）。然后，您清除所有不符合条件的节点（例如最长匹配）。然后做一个随后的数据传递，建立更深层次的，但不是更广泛。重复，直到找到最长的重复序列。

一位好朋友建议使用散列法。通过对从每个字符开始的固定长度字符序列进行哈希处理，您现在遇到了查找重复哈希值的问题（并验证重复，因为哈希是有损的）。如果你分配一个数组的长度来保存哈希值，你可以做一些有趣的事情，例如要查看匹配是否比数据的固定长度更长，您可以比较哈希序列而不是重新生成它们。等

来源

2009-01-01 14:13:47 Will

您是否按照这些方针实施了解决方案？我正面临类似的要求。 – 2013-11-20 05:15:35

只是，发生在我迟来的想法...

根据您的OS /环境。（例如64位指针& mmap（）可用。）

您可能能够通过mmap（）在磁盘上创建一个非常大的后缀树，然后保留该树的缓存最频繁访问的子集记忆。

来源

2009-01-02 08:49:01

怎么样像这样一个简单的程序：

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)

来源

2012-05-17 16:49:54

在一个巨大的字符串中发现长重复的子字符串

回答

相关问题