difflib根據序列的順序返回不同的比率

Question

有誰知道爲什麼這兩個返回不同的比率。

>>> import difflib 
>>> difflib.SequenceMatcher(None, '10101789', '11426089').ratio() 
0.5 
>>> difflib.SequenceMatcher(None, '11426089', '10101789').ratio() 
0.625 

Answer 1

This給出了匹配如何工作的一些想法。

>>> import difflib 
>>> 
>>> def print_matches(a, b): 
...  s = difflib.SequenceMatcher(None, a, b) 
...  for block in s.get_matching_blocks(): 
...   print "a[%d] and b[%d] match for %d elements" % block 
...  print s.ratio() 
... 
>>> print_matches('01017', '14260') 
a[0] and b[4] match for 1 elements 
a[5] and b[5] match for 0 elements 
0.2 
>>> print_matches('14260', '01017') 
a[0] and b[1] match for 1 elements 
a[4] and b[2] match for 1 elements 
a[5] and b[5] match for 0 elements 
0.4 

它看起來好像它在第一個序列上與第二個序列匹配並且從匹配繼續。在這種情況下（'01017'，'14260'），右邊的匹配位於最後一個字符0上，因此右邊沒有進一步的匹配。在這種情況下（'14260'，'01017'），1s匹配和0仍然可以在右邊匹配，所以找到兩個匹配。

我認爲匹配算法是針對排序序列交換的。

Answer 2

最近我和difflib一起工作，雖然這個答案很晚，但我認爲它可能會爲hughdbrown提供的答案增加一點點刺激，因爲它顯示了視覺上發生的事情。

我去的代碼片段之前，請允許我引用的documentation

的想法是找到最長的連續匹配子是 不包含任何「垃圾」的元素;這些「垃圾」元素是在某種意義上不感興趣的元素，例如空白行或空白。 （處理垃圾是對Ratcliff和Obershelp算法的擴展。）然後將相同的想法遞歸地應用於匹配 子序列的左側和右側的片段 。 這不會產生最小的編輯序列，但確實傾向於 產生匹配「看起來正確」的人。

我覺得第一個字符串比較反對第二個，然後找到比賽看起來正確足夠的人。這在hughdbrown的答案中很好地解釋了。

現在嘗試，並運行此代碼段：

def show_matching_blocks(a, b): 
    s = SequenceMatcher(None, a, b) 
    m = s.get_matching_blocks() 
    seqs = [a, b] 

    new_seqs = [] 
    for select, seq in enumerate(seqs): 
     i, n = 0, 0 
     new_seq = '' 
     while i < len(seq): 
      if i == m[n][select]: 
       new_seq += '{' + seq[m[n][select]:m[n][select] + m[n].size] + '}' 
       i += m[n].size 
       n += 1 
      elif i < m[n][select]: 
       new_seq += seq[i:m[n][select]] 
       i = m[n][select] 
     new_seqs.append(new_seq) 
    for seq, n in zip(seqs, new_seqs): 
     print('{} --> {}'.format(seq, n)) 
    print('') 

a, b = '10101789', '11426089' 
show_matching_blocks(a, b) 
show_matching_blocks(b, a) 

輸出：

10101789 --> {1}{0}1017{89} 
11426089 --> {1}1426{0}{89} 

11426089 --> {1}{1}426{0}{89} 
10101789 --> {1}0{1}{0}17{89} 

在大括號（{}）的部分是匹配的部件。我只是使用SequenceMatcher.get_matching_blocks()將匹配塊放在花括號中以獲得更好的可見性。訂單逆轉時您可以清楚地看到差異。第一個訂單有4個匹配項，所以比例爲2*4/16=0.5。但是，當順序顛倒時，現在有5場比賽，所以比例變成2*5/16=0.625。該比率計算爲here in the documentation