其中兩個字符串不同

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 

Answer 2

這是經典的編輯距離問題。我只是想讓你谷歌它，並瞭解它是如何工作的。沒有必要在這一個代表。

Answer 3

看看在Levenstein distance wikipedia page的僞代碼例子。這個例子可以很容易地修改，以滿足您的需求。