Levenshtein 거리 알고리즘

Question

def worddistance(source, target): 
    ''' Return the Levenshtein distance between 2 strings ''' 

    if len(source) > len(target): 
     source, target = target, source 
    #Now target becomes the larger string, if it is 0, surely len(source) is 0? 
    if len(target) == 0: 
     return len(source) 

    ### Continue on to calculate distance. 

두 매개 변수가 동일하면 0을 반환하는 것과 똑같지 않습니까?

나는 함수의이 부분의 길이가 0입니다 당신은 거의Wikibooks implementation에서 같은 스타일을 볼 수 있습니다 둘 경우

가

Answer 1

예, 코드가 0를 반환 달성하기 위해 노력하고 정확히 잘 모르겠습니다; 그러나 여기의 코더는 단순히 코드를 통해 생각하지 않았습니다.

당신은 단순히 그 두 번째 테스트를 변경할 수 있습니다

if not target: 
    return 0 

과 의미를 변경할 수 없습니다.

if not source: 
    return len(target) 

훨씬 더 의미가 있습니다 :

는

위키 구현은 그러나 소스 테스트합니다.

이 함수는 해당 행 다음에 더 많은 작업을 수행합니다. 그것은 단지 경계 검사 일뿐입니다. 수표가 사라지면 알고리즘은 여전히 ​​효율적으로 작동하지 않습니다. Wikibooks 버전은 [1]에서 [len(target)]까지 일련의 1 요소 목록을 생성 한 다음 마지막 요소를 반환합니다. 그래서 len(target).