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

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

<a href="http://docs.python.org/dev/library/difflib.html" rel="noreferrer noopener nofollow">difflib</a>.<a href="http://docs.python.org/dev/library/difflib.html#difflib.SequenceMatcher" rel="noreferrer noopener nofollow">SequenceMatcher</a>.<a href="http://docs.python.org/dev/library/difflib.html#difflib.SequenceMatcher.get_opcodes" rel="noreferrer noopener nofollow">get_opcodes</a>可以做到这一点。

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