VBScript : Levenshtein Distance

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

예로 GeorgeGeordie 두 문자열을 생각해 보자. 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

Related posts:

  1. VBScript: URLEncode, URLDecode 함수 ASP에 URL을 인코딩하려면 Server 객체의 URLEncode 메쏘드를 사용하면 된다. 그럼...
  2. ASP에서 CodePage 고찰 ASP에서 CodePage 설정에 따라 문자열이 어떻게 처리가 되는지를 살펴보자. <%@...
  3. VBScript: 크기가 정해지지 않은 DynamicArray 클래스 DynamicArray 클래스 Class DynamicArray '************** Properties ************** Private aData '****************************************...
  4. JavaScript Code Improver – obfuscator에 상반되는 툴 JavaScript Code Improver Cannot read your own JavaScript code?Cannot find...
  5. [vbscript] 문자열 앞,뒤의 White Space를 제거하는 TrimEx 함수 VBScript의 문자열 처리 함수 중 Trim이란게 있다. 문자열 앞,뒤의 스페이스를...