파이썬 퍼지 levenshtein 비율 조기 종료있어?

Question

나는 100k 개의 문자열을 서로 비교하려고합니다. 문제 크기 (즉, 세트의 # 문자열)를 더 이상 줄일 수는 없습니다. 나는 비교하기 위해 Levenshtein 비율을 사용하고 있습니다. 비율이 0.9보다 크면 두 개의 문자열을 목록에 저장하려고합니다. 내 질문은 런타임 최적화에 관한 것입니다. 0.9가 나의 기준이기 때문에 Levenshtein.ratio()에이 값을 전달하고 부정적인 경우에 조기 종료를 기대할 수있는 방법이 있습니까? 초기에 종료 할 수있는 방법이 있으면 런타임을 저장할 수 있습니다. Levenshtein 알고리즘에서 전체 거리를 계산하기 전에 일찍 비율을 구할 수 있습니까?

Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio', 0.9) 

Answer 1

예, 가정 함하고 같은 조기 종료가 가능하다 : 예 :

import Levenshtein 
Levenshtein.ratio('lot of runtime','why not an early exit in this case by taking the intended ratio') 

뭔가 같은 존재입니다. 이 기능 자신을 추가 할 수 있도록

Levenshtein 모듈에 대한 소스 코드는 자유롭게 사용할 수 있습니다.

고려해야 할 또 다른 최적화가 있는데, 삼각형 부등식입니다. 문자열 A가 문자열 B와 20 % 유사하고 문자열 B가 문자열 C와 90 % 유사하다면 문자열 A가 문자열 C와 90 % 유사하지 않을 것임을 알 것입니다. 불가능할 수 있으므로 실제로 AC Levenshtein 거리를 계산합니다.