편집 거리가

Question

편집 거리가 다른 하나 개의 문자열에 필요한 삽입, 삭제 또는 대체의 수를 찾습니다. 이 알고리즘에 스왑도 포함하고 싶습니다. 예를 들어 "사과"와 "아펠"여기 알고리즘을 참조 1.

Answer 1

의 편집 거리를 제공해야합니다.

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

추가, 스왑에 대한 삭제를 다른 비용을 제공 할 수 있습니다. 당신이 정의하는

m[i,j] = min(m[i-1,j-1] 
     + if s1[i]=s2[j] then 0 else cost_swap fi, 
     m[i-1, j] + cost_insert, 
     m[i, j-1] + cost_delete), i=1..|s1|, j=1..|s2| 

Answer 2

편집 거리가 Damerau - Levenshtein 거리이라고합니다. 가능한 구현은 Wikipedia page에서 찾을 수 있습니다.