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') 1과 일치하고 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