其中两个字符串不同

找到位置，我有两个很长的单词序列。其中两个字符串不同

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

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功能来解决，这将是更快（实施）。

来源

2012-06-13 Velvet Ghost

最长公共子可能更适用。 –

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-13 10:57:11

这无疑解决了这个问题！谢谢！如果我需要找出difflib在内部使用的算法，我会查找他们的文档。 –

这是经典的编辑距离问题。我只是想让你谷歌它，并了解它是如何工作的。没有必要在这一个代表。

来源

2012-06-13 10:45:03

NLTK具有以下功能：找到编辑距离。问题是 - 这只是两个字符串之间相似性的数字度量。我刚刚在我的两个'测试'字符串之间获得了34的Levenstein距离。但是，我需要实际的差异和他们的位置，而不仅仅是一个数字！ –

您可以轻松地修改编辑距离的问题，给你，你必须做出的实际变化。 – sukunrt

看看在Levenstein distance wikipedia page的伪代码例子。这个例子可以很容易地修改，以满足您的需求。

来源

2012-06-13 10:58:16 stanri

其中两个字符串不同

回答

相关问题