2

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

我需要找到它们不同的地方。例如，如果输入是

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 功能部分或完全解决这个问题，它会更快（实现）。

4

3 回答 3

7

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
于 2012-06-13T10:57:11.917 回答
1

这是经典的编辑距离问题。我只是让你谷歌它并了解它是如何工作的。这个不需要代表。

于 2012-06-13T10:45:03.070 回答
0

查看Levenstein distance wikipedia page上的伪代码示例。可以轻松修改此示例以满足您的需要。

于 2012-06-13T10:58:16.110 回答