Tag: algorithm

Levenshtein Distance은 두 문자열의 유사도를 구할 때 사용할 수 있는 알고리듬이다. 이 알고리듬은 첫번째 문자열을 두번째 문자열로 변환하기 위해서 필요한 작업수를 구한다.

예로 George, Geordie 두 문자열을 생각해 보자. George를 Geordie로 바꾸기 위해서는 다음과 같이 2개의 문자 변환 작업이 필요하다.

1. George -> Geordie (‘g’를 ‘d’로 치환)
2. 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