[TM] Levenshtein Distance를 이용한 두 문자열의 유사도 측정

/********************************************************************************************
-- Title : [TM] Levenshtein Distance를 이용한 두 문자열의 유사도 측정
-- Reference : yjacket.tistory.com
-- Key word :  Levenshtein distance algorithm (A.K.A edit distance) 알고리즘 텍스트마이닝 text mining textmining
********************************************************************************************/

-- 1. 원리

비교 대상이 되는 두 문자열을 각 a, b 라 할 때,

a를 b로 수정하는데 필요한 문자의 추가, 삭제, 수정 횟수를 덧셈하면 그것이 곧 유사도가 된다..

즉, "I love you"가 "I hate you"가 되기 위해선

I love you

↓↓↓

I hate you 

"lov" 세글자가 "hat" 로 수정되야 한다.

문자바뀜횟수는 3회이고 따라서 레벤시테인 거리 알고리즘에 의한 유사도는 3 이라 볼 수 있다.

유사도는 0이면 완전히 일치하고, 0에서 멀어질수록 유사하지 않다고 볼 수 있다.

단, 의미 상의 유사도가 아님에 유의해야 한다.

-- 2. 알고리즘 구현

그리고 내가 필요해서 찾은 T-SQL 구현은 아래와 같으며 저자는 Arnold Fribble.

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END