[ML] Levenshtein distance

string(문자열) 간의 차이를 측정하기 위한 measure임.

한 문자열이 다른 문자열로 변환되기 위해 필요한 최소한의 연산의 수를 나타냄.

여기서의 연산이란 다음 3가지로 구성됨.

• insertion (추가)
• deletion (삭제)
• substitution (치환)

 

참고로, Levenshtein distance는 symmetric을 성립하지 않아서 엄밀한 의미의 metric (or distance function)은 아님.

 

Levenshtein distance의 경우, 길이가 다른 string간의 차이도 측정하지만, 같은 길이의 string만으로 한정할 경우엔 Hamming distance가 보다 편함

Hamming Distance : https://dsaint31.me/mkdocs_site/DIP/cv2/etc/dip_metrics/#hamming-distance

BME228

구현방법

Dynamic Programming 기법으로 구현됨.

 

ref. : https://www.researchgate.net/publication/283041807_Structural_Off-line_Handwriting_Character_Recognition_Using_Approximate_Subgraph_Matching_and_Levenshtein_Distance/figures?lo=1

문자열 $A$,$B$가 주어진 경우의 Levenshtein distance은 다음으로 구함. ($m$은 문자열 $A$의 길이이고 $n$은 문자열 $B$의 길이)

1. 크기가 $(m+1) x (n+1)$인 matrix $D$를 생성.
2. matrix $D$의 첫 번째 행과 첫 번째 열을 0부터 m까지 증가하는 숫자들로 초기화.
3. matrix $D$의 나머지 위치 $D(i, j)$에 대해 다음으로 설정.
   1. $A[i]$와 $B[j]$가 같으면 $D[i][j] = D[i-1][j-1]$ : 어떤 연산도 수행할 필요 없음.
   2. $A[i] \ne B[j]$이면 $D[i][j] = \text{min}(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + 1)$ : $\text{min}$내의 각 항은 각각 deletion, insertion, substitution임.
4. matrix $D$를 모두 채운 후, $D[m][n]$이 결과 Levenshtein distance가 됨.

 

응용분야

• OCR
• string similarity 측정
• 철자 교정