difflib.SequenceMatcher의 예상치 못한 동작 get_matching_blocks()

Question

나는 fuzzywuzzy으로 실험 중이 었으며 많은 경우에 잘못된 결과가 발생했습니다. 디버깅을 시도하고 설명하기 어려운 get_matching_blocks()를 사용하여 시나리오를 만났습니다.

get_matching_blocks()는 삼중 튜플을 반환해야한다 내 이해 (I, J, N) 인덱스 i에서 제 문자열 길이 n의 서브 문자열 길이의 서브 스트링과 정확하게 일치해야 n은 색인 j의 두 번째 문자열에 있습니다.

>>> hay = """"Find longest matching block in a[alo:ahi] and b[blo:bhi]. If isjunk was omitted or None, find_longest_match() returns (i, j, k) such that a[i:i+k] is equal to b[j:j+k], where alo <= i <= i+k <= ahi and blo <= j <= j+k <= bhi. For all (i', j', k') meeting those conditions, the additional conditions k >= k', i <= i', and if i == i', j <= j' are also met. In other words, of all maximal matching blocks, return one that starts earliest in a, and of all those maximal matching blocks that start earliest in a, return the one that starts earliest in b.""" 
>>> needle = "meeting those conditions" 
>>> needle in hay 
True 
>>> sm = difflib.SequenceMatcher(None,needle,hay) 
>>> sm.get_matching_blocks() 
[Match(a=5, b=8, size=2), Match(a=24, b=550, size=0)] 
>>> 

그런데 왜 위 코드가 일치하는 블록을 찾지 못합니까?

Answer 1

잘 보이지 않을 수 있지만 hay과 needle이 일치하지 않습니다. 당신은

sm = difflib.SequenceMatcher(None, needle, hay) 

이어야한다

sm = difflib.SequenceMatcher(None,needle, sms) 

있어? 또한 레코드의 경우 get_matching_blocks()에 의해 반환 된 목록의 마지막 요소는 더미 형식 (len (a), len (b), 0)입니다.

아마 그냥 붙여 넣기의 실수, 그러나 실제 코드를 귀하의 질문에 (내가 SequenceMatcher() 방법을 생각하고있다)

---

SequenceMatcher는 "정크 발견"을 끊었다 업데이트하십시오 - 두 번째 문자열에있는 경우 최소 200 자, 의 정크은 (count-1)이 전체 길이의 1 % 이상인 모든 문자입니다. official bug ticket (즉 this comment)에서 의견

버그 이유는 추론은 : 제 2 시퀀스는 긴 다음 적어도 200 개 아이템에서의 경우 두 번째 순서 시간을 1 % 이상 발생 된 모든 항목 쓰레기로 취급됩니다. 이것은 'else :'및 'return'과 같은 반복 코드 행 을 대상으로했지만 에 공통적 인 항목이 필요한 작은 알파벳은 치명적일 수 있습니다.

나는 또한 나 자신에게 위의 저자에 의해 제공 인용 코드 예제를하게됩니다 :

여기

렌의 (a) == (200), LEN (B) == 199 : 여기

>>> print(SM(None, 'x' + 'y'*199, 'y'*199).ratio()) 
>>> 0.9975 #correct 

렌 (a) == 199, LEN (b) == 200 (우리 a 및 b 스위치)가 두 경우 모두 동일한 출력을 제공한다 명백하게

>>> print(SM(None, 'y'*199, 'x' + 'y'*199).ratio()) 
>>> 0 #wrong 

. 수동으로 False로 설정해야합니다 - 여기에 올바른 행동 -

이 버그는 내가 언급 선택적 매개 변수, autojunk을 추가하여 고정 했다.