반응형


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

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




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


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

 {}

N

E

X

T

T

E

 

 

 

 

X

 

 

 

 

T

 

 

 

 


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

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

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

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


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



참고 링크


반응형

+ Recent posts