텍스트 유사성을 판단하는 편집거리 알고리즘

Ailyn 2017. 4. 12. 10:21

#텍스트간의 유사성을 판단하는 : 편집거리 알고리즘 (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

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

참고 링크