Ailyn의 기술 블로그

#텍스트간의 유사성을 판단하는 : 편집거리 알고리즘 (Levenshtein distance)

https://en.wikipedia.org/wiki/Levenshtein_distance

두 문자열의 유사도를 판단하는 알고리즘으로 비교하려는 문자열을 기준으로 문자열을 삽입/삭제/변경(수정)을 몇 번이나하여 동일하게 바꿀 수 있는 지를 계산하여 유사도의 판단 기준으로 삼는 알고리즘이다.

예시) next과 text의 유사도를 알고 싶다면?

ㄱ. T를 N으로 바꾸는 방법

(방법1) T를 삭제(+1)하고 N으로 수정(+1)한다. : 비용2

(방법2) T에 N을 추가(+1)하고 (TN) T를 삭제(+1)한다. : 비용 2

(방법3) T를 N으로 수정(+1)한다. : 비용1

이런 방식으로 모든 칸의 비용을 계산한 뒤, 최소 비용의 값을 구하면 된다.

참고 링크

• http://soooprmx.com/wp/archives/6486
• http://juggernaut.tistory.com/entry/%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%B0%A8%EC%9D%B4%EC%A0%90-%EB%B0%9C%EA%B2%AC-%EC%A0%84%EB%9E%B5Diff-Strategies