[머신러닝] 문장 유사도 분석을 위한 Levenshtein Distance(편집거리 알고리즘) 행렬 구하기

 

 

두 문장의 유사도를 알기 위해 "레벤슈타인 거리"라는 알고리즘을 사용할 수 있습니다. 

 

 

대학시절 이산수학 과목에서 배웠는데 잊어버리기도했고 문장 유사도 분석을 해야하기 때문에 다시 정리할까 합니다.

 

 

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

 

 

이러한 공식을 가지고 있다고 합니다.

 

 

하지만 너무 어려우니 저는 매트릭스에 값 채우는 법만 빠르게 알아보겠습니다

 

 

레벤슈타인 알고리즘은 2차원 매트릭스를 생성하는데 비교하는 글자의 수에 따라서 정방행렬이 될 수도 있고, 아닐 수도 있습니다.

 

 

비교하려는 두 개의 문자 또는 문장의 길이가 같으면 정방행렬, 그렇지 않다면 정방행렬이 아니게 됩니다.

 

 

규칙은 간단합니다. 2차원 매트릭스의 행과 열을 a[i], b[j]라 할때 a[i] == b[i]이면 왼쪽 위 대각선 값을 그대로 가져오고, 그렇지 않으면 왼쪽, 위쪽, 왼쪽 위 대각선 셋 중 가장 작은 값에 +1을 해준값을 가져오면 됩니다.

 

 

그렇게 모든 값을 채운 후 2차원 행렬의 오른쪽 가장 아래 값이 레벤슈타인 거리가 됩니다.

 

 

예시로 "kitten"과 "sitting"의 레벤슈타인 거리가 얼마인지 알아보겠습니다.

 

 

맨 처음 각 행에 원하는 글자를 넣고 숫자를 채워줍니다.

 

 

 

 

첫 번째 행인 s를 채워주겠습니다. 위에서 말한대로 a[i] == b[j]이면 왼쪽 위 대각선의 값을 그대로 가져오고 아니라면 왼쪽, 위쪽, 왼쪽위 대각선에서 가장 작은 값에서 +1을 해줍니다.

 

두 번째 행인 i를 채울 때에는 같은 알파벳인 i 가 있습니다. 그래서 a[i] == b[j]를 만족해 왼쪽위 대각선의 값을 그대로 가져옵니다.

 

 

그렇게 같은 방법으로 끝까지 진행하다 보면 다음과 같이 매트릭스가 채워지게 됩니다.

(색상별로 칠한 것은 a[i] == b[j]일때를 나타냈습니다)

 

 

그렇게 가장 아래에 있는 값은 3이므로 (빨간색 배경) 레빈슈타인 거리는 3이 됩니다.

 

 

kitten에서 sitting으로 변환하는데 최소 횟수는 3임을 알 수 있습니다.

 

---

 

참고한 블로그

https://hoonzi-text.tistory.com/116

편집거리 알고리즘을 통한 검색어 자동완성 보정 (ft . Levenshtein Distance)