문장의 유사도를 N-gram으로 분석하기

이번에는 레벤슈타인 거리 계산과 n-gram을 사용해 단어 또는 문장의 유사도를 분석하는 방법을 알아보자

 

레벤슈타인 거리

"레벤슈타인 거리(Lvenshtein distance)"는 두 개의 문자열이 어느 정도 다른지를 나타내는 것이다. 이를 "편집 거리(Edit Distance)"라고도 부른다. 철자 오류 수정, 비슷한 어구 검색 등에 사용되고 있는데 의학 분야에서는 DNA배열의 유사성을 판단할 때도 사용하고 있다. 

예를 들어 "가나다라"와 "가하마라"는 얼마나 비슷할까? 레벤슈타인 거리는 "가나다라"를 "가마바라"로 편집할 때 몇 번의 문자열 조작이 필요한지에 주목해서 단어의 거리를 구한다.

횟수	편집 조작	결과
0	-	가나다라
1	"나"를 하"로 변환	가마다라
2	"다"를 "마"로 변환	가마바라

이처럼 "가나다라"를 "가하마라"로 변경하려면 2번의 조작이 필요하다. 따라서 편집 비용(조작 횟수)은 2라고 할 수 있으며 이러한 2를 레벤슈타인 거리라고 부른다.

 

 

파이썬으로 레벤슈타인 거리를 계산하는 프로그램

레벤슈타인 거리를 구하는 방법은 간단하다. 파이썬으로 레벤슈타인 거리를 계산하는 프로그램은 다음과 같다.

 

<distance.py>

# 레벤슈타인 거리 구하기
def calc_distance(a, b):
    ''' 레벤슈타인 거리 계산하기 '''
    if a == b: return 0 # 같으면 0을 반환
    a_len = len(a) # a 길이
    b_len = len(b) # b 길이
    if a == "": return b_len
    if b == "": return a_len
    # 2차원 표 (a_len+1, b_len+1) 준비하기 --- (※1)
    matrix = [[] for i in range(a_len+1)]
    for i in range(a_len+1): # 0으로 초기화
        matrix[i] = [0 for j in range(b_len+1)]
    # 0일 때 초깃값을 설정
    for i in range(a_len+1):
        matrix[i][0] = i
    for j in range(b_len+1):
        matrix[0][j] = j
    # 표 채우기 --- (※2)
    for i in range(1, a_len+1):
        ac = a[i-1]
        for j in range(1, b_len+1):
            bc = b[j-1]
            cost = 0 if (ac == bc) else 1
            matrix[i][j] = min([
                matrix[i-1][j] + 1,     # 문자 삽입
                matrix[i][j-1] + 1,     # 문자 제거
                matrix[i-1][j-1] + cost # 문자 변경
            ])
    return matrix[a_len][b_len]
# "가나다라"와 "가마바라"의 거리 --- (※3)
print(calc_distance("가나다라","가하마라"))
# 실행 예
samples = ["신촌역","신천군","신천역","신발","마곡역"]
base = samples[0]
r = sorted(samples, key = lambda n: calc_distance(base, n))
for n in r:
    print(calc_distance(base, n), n)

프로그램을 실행한 결과는 다음과 같다.

 

 

이 코드에 대해 살펴보면 2차원 배열을 만들어 하나씩 채워나가는 걸 볼 수 있는데 이를 이해하기 위해 예시를 살펴보자

문자열 "delegate"와 "delete"를 calc_distance함수 안에 넣었다고 가정해보자. 위의 코드에서 0일 때 초기값을 설정한 후에 2차원 배열을 나타내는 표는 다음과 같이 된다.

왜 다음과 같은 숫자가 넣어질까?

일단 표 안에 있는 숫자는 문자를 몇 번이나 삽입, 삭제, 변경해서 같게 바꿀 수 있는지를 계산하여 그 최솟값을 나타내는 수이다.

예를 들어 d와 {} 같은 경우 한 개를 추가해야하기 때문에 1이다. 그리고 de와 {}는 2개를 추가해야 되기 때문에 코스트가 2가 되는 것이다.

i/j	{}	d	e	l	e	t	e
{}	0	1	2	3	4	5	6
d	1
e	2
l	3
e	4
g	5
a	6
t	7
e	8

 

 

다음 코드를 보기 전에 직접 문자열을 비교해보면서 직접 표를 채워보자.

d와 d는 같은 문자이므로 코스트가 0이고, d와 de는 하나를 지워야 하므로 코스트는 1이다. 그리고 d와 del은 두개를 지워야 하므로 코스트는 2이다. 

이런식으로 4번째 줄까지만 채워보면 아래와 같다.

i/j	{}	d	e	l	e	t	e
{}	0	1	2	3	4	5	6
d	1	0	1	2	3	4	5
e	2	1	0	1	2	3	4
l	3	2	1	0	1	2	3
e	4
g	5
a	6
t	7
e	8

 

 

테이블을 직접 채워보면 몇 가지 사실을 알 수 있다. 

만약 문자열 MICROSOFT와 NCSOFT 마지막 T끼리 비교했다면 T는 서로 일치하므로 그 전까지 비교했던 MICROSOF와 NCSOF의 편집거리를 가져오면 된다.

MICRO와 NCS를 비교할 경우, O와 S는 서로 같지 않으므로 MICR와 NC를 비교했을 때의 편집거리에 1을 증가시키면 된다.

여기서 첫 번째 규칙을 정리하자면 두 변수가 일치하는 경우 이전의 편집거리를 그대로 가져오면 되는 것이다.

즉, A[i] == B[j]일 때의 편집거리 D(i,j) = D(i-1,j-1)이다. 

    # 표 채우기 --- (※2)
    for i in range(1, a_len+1):
        ac = a[i-1]
        for j in range(1, b_len+1):
            bc = b[j-1]
            cost = 0 if (ac == bc) else 1
            matrix[i][j] = min([
                matrix[i-1][j] + 1,     # 문자 삽입
                matrix[i][j-1] + 1,     # 문자 제거
                matrix[i-1][j-1] + cost # 문자 변경
            ])

위의 코드에서 보면 matrix[i-1][j-1] + cost 가 ac == bc일때 cost가 0이 되서 결국 matrix[i][j] = matrix[i-1][j-1] + 0이 된다는 걸 알 수 있다. 테이블의 위치로 보면 같을 경우는 자신의 위치에서 왼쪽 대각선 위에 것을 가져오면 되는 것이다. 

 

이제 비교하는 두 문자가 다를 경우는 어떻게 해야 할까 

이전의 편집거리에서 1을 증가시켜야 하는데 즉, A[i] != B[j]이면 각 수정, 삽입, 삭제를 한 편집거리 중 최솟값을 가져오면 된다.

D(i,j) = min(D(i-1, j)+1, D(i,j-1)+1, D(i-1,j-1)+1)이다. 위 코드에서도 이 부분이 있는 걸 알 수 있다. 

주석을 보면 D(i-1, j)+1이 문자 삽입, D(i,j-1)+1이 문자 제거, D(i-1,j-1)+1는 문자 변경인걸 알 수 있는데 테이블을 보면서 알아보자

3번 : dele와 dele를 비교하는 경우로 마지막 e끼리 같으므로 왼쪽 대각선 위 cost 0을 그대로 복사해온다.

1번 : del와 d를 비교하는 경우로 마지막 문자가 다르므로 de과 d의 편집거리를 그대로 가져와서 추가 코스트를 더한 것이다. 

2번 : de와 del를 비교하는 경우로 마지막 문자가 다르므로 de과 de의 편집거리를 가져와서 l을 삭제한 코스트를 더한 것이다.

4번 : delet와 deleg를 비교하는 경우로 마지막 문자가 다르므로 dele와 dele의 편집거리를 가져와서 t를 g로 수정하는 코스트를 더한 것이다.

* 복사는 왼쪽 대각선 위 그대로, 추가 코스트는 왼쪽에서 +1. 삭제는 위쪽에서 +1, 수정은 왼쪽 대각선 위+1인 것을 알 수 있다. 

 

최종적으로 정리해보면 다음과 같다.

비교하는 마지막 문자가 같을 때 : 왼쪽 대각선 위 코스트를 그대로 가져온다.

비교하는 마지막 문자가 다를 때 : 추가 코스트 + 1, 삭제 코스트 + 1, 수정 코스트 + 1 한 것 중에 최솟값을 골라서 가져온다.

 

i/j	{}	d	e	l	e	t	e
{}	0	1	2	3	4	5	6
d	1	0	1	2	3	4	5
e	2	1	0	1	2	3	4
l	3	2	1	0	1	2	3
e	4	3	2	1	0	1	2
g	5	4	3	2	1	1	2
a	6	5	4	3	2	2	2
t	7	6	5	4	3	2	3
e	8	7	6	5	4	3	2

위의 테이블에서 우측 가장 하단에 빨간 숫자가 2가 뜻하는 것을 문자열 "delegate"가 문자열"delete"와 서로 같아지기 위한 연산의 횟수 즉, 레벤슈타인 거리의 답이 된다.

 

 

자 이제 대략 이해가 되었으면 코드 속 예제를 살펴보자

다음의 테이블은 <문자열 a와 b의 길이 + 1>의 크기를 가진 배열이다. 문자열 a의 i번째까지의 문자와 문자열 b의 j번째까지의 문자를 비교해서 삽입/제거/변경 비용 중 최소가 되는 값을 선택해서 표를 채워나간다. 최종적으로 표의 오른쪽 아리에 있는 값이 최소 거리가 되어 레벤슈타인 거리의 답이 된다. 

i/j	.	가	나	다	라
.	0	1	2	3	4
가	1	0	1	2	3
하	2	1	1	2	3
마	3	2	2	2	3
라	4	3	3	3	2

코드를 대략 설명하자면 이렇게 된다.

[ 1 ] : 2차원 테이블을 0으로 초기화한다.

[ 2 ] : 문자열 a의 i번째와 문자열 b의 j번째를 비교해 차례대로 최소 편집 조작 횟수를 구한다.

[ 3 ] : 레벤슈타인 거리를 테스트로 구해본다. 이어서 여러 '신촌역", "신천군", "신천역", "신발", "마곡역"으로 테스트하고 결과를 정렬해서 출력한다. 

 

 

N-gram으로 유사도 구하기

문장의 유사도를 구하는 다른 방법으로는 "N-gram"이 있다.

"N-gram"이란 텍스트에서 "이웃한 N개의 문자"를 의미한다. 서로 다른 2개의 문장을 N-gram으로 비교해보면 출현하는 단어의 종류와 빈도를 확인할 수 있다. 이를 활용하면 논문 도용 등을 확인할 수 있다. 또한 프로그램 코드에 적용해서 라이선스를 가지고 있는 코드를 복사해서 붙여넣지 않았는지 등도 확인할 수 있다. 

 

예를 들어, N-gram을 2문장(2-gram)으로 생각해보자. 다음의 2개의 문장은 어느 정도 유사할까?

[A] 오늘 강남에서 맛있는 스파게티를 먹었다. [B] 강남에서 먹었던 오늘의 스파게티는 맛있었다.

두 문장을 각각 글자 2개씩 끊으면 다음과 같이 된다.

파이썬을 이용한 머신러닝, 딥러닝 실전 개발 입문(개정판)

이렇게 끊은 단어를 비교해서 문장의 유사도를 알 수 있는데 실제로 프로그램을 만들어 비교해보자

 

<ngram.py>

def ngram(s, num):
    res = []
    slen = len(s) - num + 1
    for i in range(slen):
        ss = s[i:i+num]
        res.append(ss)
    return res
def diff_ngram(sa, sb, num):
    a = ngram(sa, num)
    b = ngram(sb, num)
    r = []
    cnt = 0
    for i in a:
        for j in b:
            if i == j:
                cnt += 1
                r.append(i)
    return cnt / len(a), r
a = "오늘 강남에서 맛있는 스파게티를 먹었다."
b = "강남에서 먹었던 오늘의 스파게티는 맛있었다."
# 2-gram
r2, word2 = diff_ngram(a, b, 2)
print("2-gram:", r2, word2)
# 3-gram
r3, word3  = diff_ngram(a, b, 3)
print("3-gram:", r3, word3)

실행보면 다음과 같다.

단어들의 순서를 변경한 문장들인데 두 문장을 2-gram으로 비교하면 0.76, 3-gram으로 비교하면 0.45가 같다는 것을 알 수 있다. 그럼 다음 문장은 어떨까?

머신러닝은 매우 재미있는 기술이라 공부하고 있습니다. 공부하면 재미있는 기술이라 머신러닝을 배우고 있습니다.

2-gram으로 확인해보면 유사도가 0.72이다. 같은 내용을 순서만 바꾸는 것만으로도 유사도가 높게 나온다. 다른 문장도 확인해

보자

본문과 전혀 관계 없는 내용이지만 카레는 맛있습니다. 카레는 본문과 전혀 관계 없이 맛있습니다.

2-gram으로 유사도가 0.71으로 나오는 걸 확인할 수 있다.

하지만 다음과 같이 아예 다른 주제의 글을 유사도가 떨어진다. 

겨울에는 매우 건조하므로 물을 자주 마셔야 합니다. 시작이 반이므로 뭐든지 도전해보세요.

2-gram으로 유사도가 0.07이고, 같은 것이 '므로', '로 ' 밖에 없는 관계 없는 문장이므로 유사도가 낮게 나오는 것이다.

 

이처럼 N-gram을 이용하면 쉽게 문장의 유사도를 확인할 수 있다. 문장을 도용했는지 확인하고 싶다면 이러한 N-gram을 활용해 유사도가 높은지 조사하면 된다. 검색 엔진 등에서도 N-gram을 활용해 웹 문서의 유사도를 확인하며 다양하게 활용할 수 있는 기술이다.

---

---

<참고 자료>

파이썬을 이용한 머신러닝, 딥러닝 실전 개발 입문(개정판)