본문 바로가기
IT/데이터베이스

두 문자열의 유사도 측정방법

by yjacket 2011. 3. 9.
뜻이 정반대인 "I love you" 라는 문자열과 "I hate you" 라는 문자열의 유사도는 어떻게 구할까?

스펠링검사, 표절검사 같은 분야에 사용되어지는 Levenshtein distance algorithm (A.K.A edit distance)을 이용하여 문자열의 유사도를 측정해보자.

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, 출처는 sqlteam.com 이다.
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