python - 海量字符串中最长的重复子串

问题描述

给定一个长字符串，找到最长的重复子字符串。

蛮力方法当然是找到所有子字符串并检查剩余字符串的子字符串，但是有问题的字符串有数百万个字符（如 DNA 序列、AGGCTAGCT 等），我想要一些完成的东西在宇宙自行坍塌之前。

尝试了多种方法，我有一个解决方案可以在高达数百万的字符串上运行得非常快，但对于较大的字符串需要永远（6 多个小时），特别是当重复序列的长度变得非常长时。

def find_lrs(text, cntr=2):
    sol = (0, 0, 0)
    del_list = ['01','01','01']
    
    while len(del_list) != 0:
        d = defaultdict(list)
        
        for i in range(len(text)):
            d[text[i:i + cntr]].append(i)
        
        del_list = [(item, d[item]) for item in d if len(d[item]) > 1]

        # if list is empty, we're done
        if len(del_list) == 0:
            return sol
        else:
            sol = (del_list[0][1][0], (del_list[0][1][1]),len(del_list[0][0]))
        cntr += 1

    return sol

我知道这很丑，但是，嘿，我是一个初学者，我很高兴我有工作要做。想法是遍历以长度为 2 的子字符串作为键开始的字符串，子字符串的索引位于该值处。如果文本是“香蕉”，那么在第一次通过后，字典将如下所示：

{'BA'：[0]，'AN'：[1, 3]，'NA'：[2, 4]，'A'：[5]}

BA 只出现一次 - 从索引 0 开始。AN 和 NA 出现两次，分别出现在索引 1/3 和 2/4 处。

然后我创建一个列表，其中仅包含至少出现两次的键。在上面的示例中，我们可以删除 BA，因为它只出现一次 - 如果没有以 'BA' 开头的长度为 2 的子字符串，则不会有以 BA 开头的长度为 3 的子字符串。所以经过剪枝后的第一个过去是：[('AN', [1, 3]), ('NA', [2, 4])]

由于至少有两种可能性，我们保存迄今为止发现的最长子字符串和索引，并将子字符串长度增加到 3。我们继续直到没有重复子字符串。

如前所述，这可以在大约 2 分钟内处理多达 1000 万个字符串，这显然是合理的 - 但是，最长的重复序列相当短。在较短的字符串但较长的重复序列上，运行需要-小时-。我怀疑这与字典的大小有关，但不太清楚为什么。

我想做的当然是通过删除明显不重复的子字符串来保持字典的简短，但是在迭代它时我不能从字典中删除项目。我知道有后缀树的方法，这样 - 现在 - 在我的范围之外。

可能只是这超出了我目前的知识范围，这当然很好，但我不禁动摇了这里有解决方案的想法。

标签： pythonlongest-substring

解决方案

我忘了更新这个。再次检查我的代码后，远离我的电脑——在我的 iPad 上写下小图表——我意识到上面的代码并没有像我想象的那样做。

如上所述，我的攻击计划是从以长度为 2 的子字符串作为键开始的字符串开始，子字符串的索引位于该值处，创建一个仅捕获发生的长度为 2 的子字符串的列表至少两次，并且只看那些位置。

一切都很好 - 但仔细观察，你会发现我实际上从未将默认字典更新为只有两个或多个重复的位置！//刘海头靠在桌子上。

我最终想出了两个解决方案。第一个解决方案使用了一种稍微不同的方法，即“排序后缀”方法。这将获取单词的所有后缀，然后按字母顺序对它们进行排序。例如，“BANANA”的后缀，排序后将是：A ANA ANANA BANANA NA NANA

然后，我们查看每个相邻的后缀，并找出每对开始有多少个相同的字母。A 和 ANA 只有“A”的共同点。ANA 和 ANANA 有共同的“ANA”，所以我们有长度 3 作为最长的重复子串。ANANA 和 BANANA 在开始时没有任何共同点，BANANA 和 NA 也是如此。NA 和 NANA 有共同的“NA”。所以'ANA'，长度为3，是最长的重复子串。

我做了一个小辅助函数来进行实际比较。代码如下所示：

def longest_prefix(suf1, suf2, mx=None):
    min_len = min(len(suf1), len(suf2))
    for i in range(min_len):
        if suf1[i] != suf2[i]:
            return (suf1[0:i], len(suf1[0:i]))
    return (suf1[0:i], len(suf1[0:i]))


def longest_repeat(txt):
    lst = sorted([text[i:] for i in range(len(text))])
    print(lst)
    mxLen = 0
    mx_string = ""
    for x in range(len(lst) - 1):
        temp = longest_prefix(lst[x], lst[x + 1])
        if temp[1] > mxLen:
            mxLen = temp[1]
            mx_string = temp[0]
    first = txt.find(mx_string)
    last = txt.rfind(mx_string)
    return (first, last, mxLen)

这行得通。然后我回去重新查看我的原始代码，发现我没有重置字典。关键是每次通过后，我都会更新字典以仅查看重复的候选者。

def longest_repeat(text):
    # create the initial dictionary with all length-2 repeats
    
     cntr = 2 # size of initial substring length we look for
     d = defaultdict(list)
     for i in range(len(text)):
         d[text[i:i + cntr]].append(i)
    
     # find any item in dict that wasn't repeated at least once
     del_list = [(d[item]) for item in d if len(d[item]) > 1]
     sol = (0,0,0)
    
     # Keep looking as long as del_list isn't empty,
     while len(del_list) > 0:
         d = defaultdict(list) # reset dictionary
         cntr += 1 # increment search length
         for item in del_list:
             for i in item:
                 d[text[i:i + cntr]].append(i)
     # filter as above
     del_list = [(d[item]) for item in d if len(d[item]) > 1]
    
     # if not empty, update solution
     if len(del_list) != 0:
         sol = (del_list[0][0], del_list[0][1], cntr)
     return sol

这是相当快的，我认为它更容易遵循。

python - 海量字符串中最长的重复子串

问题描述

解决方案

推荐阅读