python 中的粗略字符串对齐

Question

如果我有两个长度相等的字符串，如下所示：

'aaaaabbbbbccccc'
'bbbebcccccddddd'

有没有一种有效的方法来对齐这两个字母，使尽可能多的字母排成一行，如下所示？

'aaaaabbbbbccccc-----'
'-----bbbebcccccddddd'

我能想到的唯一方法是通过编辑字符串然后遍历和比较蛮力。

Answer 1

我不确定你所说的高效是什么意思，但你可以在 str:

上使用 find 方法

first = 'aaaaabbbbbccccc'
second = 'bbbebcccccddddd'
second_prime = '-'* first.find(second[0]) + second
first_prime = first + '-' * (len(second_prime) - len(first))
print first_prime + '\n' + second_prime
# Output:
# aaaaabbbbbccccc-----
# -----bbbebcccccddddd

Answer 2

我会对你的每个字符串执行类似二进制 & 函数的操作。在排列时比较每个字符串，计算字母匹配的次数。然后，移动一个，做同样的事情，一直移动，直到不再排成一行。以这种方式匹配字母最多的班次是正确的输出班次，您可以在打印时添加破折号。您实际上不必为此修改字符串，只需计算班次的数量并通过该班次数量抵消您对字符的比较。这不是非常有效 (O(n^2) = n+(n-2)+(n-4)...)，但这是我能想到的最好的。

Answer 3

除了暴力破解，我看不出还有什么办法。复杂度将是字符串长度的二次方，这可能是可以接受的，具体取决于您使用的字符串长度。

可能是这样的：

def align(a, b):
    best, best_x = 0, 0
    for x in range(len(a)):
        s = sum(i==j for (i,j) in zip(a[x:],b[:-x]))
        if s > best:
            best, best_x = s, x
    return best_x

align('aaaaabbbbbccccc', 'bbbebcccccddddd')
5

Answer 4

Return给出最大分数的索引，其中最大分数是具有最多匹配字符的字符串。

def best_overlap(a, b):
    return max([(score(a[offset:], b), offset) for offset in xrange(len(a))], key=lambda x: x[0])[1]

def score(a, b):
    return sum([a[i] == b[i] for i in xrange(len(a))])

>>> best_overlap(a, b)
5
>>> a + '-' * best_overlap(a, b); '-' * best_overlap(a, b) + b
'aaaaabbbbbccccc-----'
'-----bbbebcccccddddd'

或者，等价地：

def best_match(a, b):
    max = 0
    max_score = 0
    for offset in xrange(len(a)):
        val = score(a[offset:], b)
        if val > max_score:
            max_score = val
            max = offset
    return max

还有优化空间如：

没有匹配字符提前退出
找到最大可能匹配项后提前退出

python 中的粗略字符串对齐

Rough string alignment in python

python

string-comparison