在一个大串中寻找长重复子串

有效的方法是创建子字符串的索引,并对其进行排序。这是一个O(N LG N)操作。

BWT 压缩完成这一步,所以这是一个很好理解的问题,有基数和 suffix (claim o(n))对实现进行排序,以使其尽可能高效。它仍然需要很长时间,对于大文本来说可能需要几秒钟。

如果你想使用实用代码,C++ std::stable_sort() 表演 许多的 胜过 std::sort() 对于自然语言(比C语言快得多) qsort() 但原因不同)。

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

您可以查看基于磁盘的后缀树。我发现了这个 Suffix tree implementation library 通过谷歌,加上一堆文章,可以帮助实现它自己。

你可以用分而治之的方法来解决这个问题。我认为这应该是和使用trie一样的算法复杂性,但可能在实现方面效率较低。

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的类,使其成为一个数字列表,当缓冲区达到一定大小时,它将使用临时文件将自己写到磁盘上,并在读取时从磁盘调用。

回答我自己的问题:

考虑到长匹配也是短匹配,您可以先找到短匹配,然后查看是否可以“增长”这些匹配,从而将多个通行证交换为RAM。

这种方法的文字化方法是对数据中某个固定长度的所有序列构建一个trie(每个节点都有计数)。然后剔除所有不符合条件的节点(例如最长匹配)。然后做一个后续的数据传递,构建出更深的trie,但不是更宽的trie。重复,直到找到重复时间最长的序列。

一个好朋友建议使用哈希。通过散列从每个字符开始的固定长度字符序列,您现在有了查找重复散列值的问题(并验证重复,因为散列是有损的)。如果为数组分配数据长度以保存哈希值,则可以执行一些有趣的操作,例如,要查看匹配是否比固定长度的数据传递长,只需比较哈希序列,而不是重新生成它们。等。

像这样的简单程序怎么样:

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)

这篇文章有断字吗?然后我怀疑你想在上下文中改变关键词:对一行中的n个单词复制每行n次,在每个单词处破坏每行;对整个单词的alpha排序;寻找重复。

如果它是一个长的按喇叭的字符串,比如说生物信息学的DNA序列,那么你需要在磁盘上建立类似trie的东西;为每个字符建立一个记录,并为下一个节点建立一个磁盘偏移量。我想看看第三卷 Knuth 第5.4节“外部排序”。

你能通过建立一个 suffix array 相反?否则,您可能需要使用其他答案中提到的基于磁盘的后缀树之一。

只是我想到的一个迟来的想法…

取决于您的操作系统/环境。(例如,64位指针&mmap()可用。)

您可以通过mmap()在磁盘上创建一个非常大的后缀树,然后在内存中保存该树最常访问的缓存子集。

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