查找两个字符串不同的位置

Question

我有两个非常长的单词序列.

我需要找到他们不同的地方.例如,如果输入是

1st sequence: A B C D E F G
2nd sequence: A X D Y Z W G

(这里的每个字符代表一个单词)

输出应该是:

B C -> X
E F -> Y Z W

我的想法:我可以有两个序列的索引.最初,两者都指向A.增加两个指数.现在第一个索引指向B,第二个索引指向X.我现在可以搜索整个第二个序列中的B.没有找到它,我可以搜索整个第二个序列中的C,然后搜索D.我会找到一个D,并且因此可以解决问题.

显然,这种"蛮力"方法很糟糕.

什么是更好的方法？

我正在用Python编写我的代码,并使用NLTK,所以如果可以使用内置的NLTK功能部分或完全解决这个问题,那么它将更快(实现).

Answer 1

difflib.SequenceMatcher.get_opcodes 可以做到这一点.

import difflib

def diff(a, b):
    for tag, i1, i2, j1, j2 in difflib.SequenceMatcher(a=a, b=b).get_opcodes():
        if tag!='equal':
            yield a[i1:i2], b[j1:j2]

>>> d = list(diff('A B C D E F G'.split(), 'A X D Y Z W G'.split()))
>>> d
[(['B', 'C'], ['X']), (['E', 'F'], ['Y', 'Z', 'W'])]
>>> '\n'.join('{} -> {}'.format(*(' '.join(i) for i in l)) for l in d)
B C -> X
E F -> Y Z W

旧答案 - 等效功能:

import difflib

def diff(a, b):
    add, remove = [], []
    for line in difflib.ndiff(a, b):
        d, line = line[0], line[2:]
        if d in '+-':
            (add if d=='+' else remove).append(line)
        elif add or remove:
            yield remove, add
            add, remove = [], []
    if add or remove:
        yield remove, add