如何在 python 中合并具有重叠字符的字符串？

Question

我正在开发一个 python 项目，该项目读取 URL 编码的重叠字符串列表。每个字符串的长度为 15 个字符，并且与其顺序字符串至少重叠 3 个字符，最多 15 个字符（相同）。

该程序的目标是从重叠字符串列表（有序或无序）到压缩的 URL 编码字符串。

我当前的方法在重叠字符串中的重复段上失败。例如，我的程序组合不正确：

StrList1 = [ 'd+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

输出：

output = ['ublic+class+HelloWorld+%7B%0A++++public+', '%2F%2F+Sample+program%0Apublic+static+v`]

当正确的输出是：

output = ['%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v']

我使用的是简单的 python，而不是 biopython 或序列比对器，但也许我应该这样做？

非常感谢在 python!

中就此事提出的任何建议或建议的好方法

谢谢！

Answer 1

您可以从列表中的一个字符串开始（存储为 string），对于列表中剩余的每个字符串（存储为 candidate），其中：

candidate 是 string、
candidate 包含 string,
candidate的尾巴与string、
或者，candidate的头与string的尾相匹配，

assemble 两个字符串根据它们重叠的方式，然后递归重复该过程，从剩余的字符串中删除重叠的字符串并追加 assembled 字符串，直到只有一个字符串留在列表中，此时它是一个有效的完全 assembled 字符串，可以添加到最终输出中。

由于多个字符串相互重叠可能有多种方式，其中一些可能导致相同的 assembled 字符串，您应该改为输出一组字符串：

def assemble(str_list, min=3, max=15):
    if len(str_list) < 2:
        return set(str_list)
    output = set()
    string = str_list.pop()
    for i, candidate in enumerate(str_list):
        matches = set()
        if candidate in string:
            matches.add(string)
        elif string in candidate:
            matches.add(candidate)
        for n in range(min, max + 1):
            if candidate[:n] == string[-n:]:
                matches.add(string + candidate[n:])
            if candidate[-n:] == string[:n]:
                matches.add(candidate[:-n] + string)
        for match in matches:
            output.update(assemble(str_list[:i] + str_list[i + 1:] + [match]))
    return output

因此您的示例输入：

StrList1 = ['d+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

assemble(StrList1) 会 return:

{'%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v'}

或者作为具有各种重叠可能性的输入示例（第二个字符串可以通过在内部匹配第一个字符串，尾部匹配头部，头部匹配尾部）：

assemble(['abcggggabcgggg', 'ggggabc'])

会 return:

{'abcggggabcgggg', 'abcggggabcggggabc', 'abcggggabcgggggabc', 'ggggabcggggabcgggg'}

如何在 python 中合并具有重叠字符的字符串？

How to merge strings with overlapping characters in python?

python

string

merge

string-comparison

sequence-alignment