Levenshtein Distance은 두 문자열의 유사도를 구할 때 사용할 수 있는 알고리듬이다. 이 알고리듬은 첫번째 문자열을 두번째 문자열로 변환하기 위해서 필요한 작업수를 구한다.
예로 George, Geordie 두 문자열을 생각해 보자. George를 Geordie로 바꾸기 위해서는 다음과 같이 2개의 문자 변환 작업이 필요하다.
- George -> Geordie (‘g’를 ‘d’로 치환)
- Georde -> Geordie (‘d’와 ‘e’ 사이에 ‘i’ 추가)
이미지 출처 : http://www.codeproject.com/Articles/162790/Fuzzy-String-Matching-with-Edit-Distance
다음은 VBScript로 이를 구현한 소스이다.
Function LevenshteinDistance(string1, string2)
Dim i, j, len1, len2, distance(), result
len1 = Len(string1) : len2 = Len(string2)
ReDim distance(len1, len2)
For i = 0 To len1 : distance(i, 0) = i : Next
For j = 0 To len2 : distance(0, j) = j : Next
For i = 1 To len1
For j = 1 To len2
If Asc(Mid(string1, i, 1)) = Asc(Mid(string2, j, 1)) Then
distance(i, j) = distance(i - 1, j - 1)
Else
distance(i, j) = Min3(distance(i - 1, j) + 1, distance(i, j - 1) + 1, distance(i - 1, j - 1) + 1)
End If
Next
Next
LevenshteinDistance = distance(len1, len2)
End Function
Function Min3(a, b, c)
Dim result
result = a
if (b < result) then result = b
if (c < result) then result = c
Min3 = result
End Function