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

레벤슈타인 또는 N-gram과 같은 방법을 사용해 텍스트 유사도를 분석하는 방법을 살펴보자

 

레벤슈타인 거리

: 두 개의 문자열이 어느 정도 다른지를 나타내는 것으로 "편집 거리(Edit Distance)"라고도 부른다.

철자 오류 수정, 비슷한 어구 검색 등에 사용되고 있으며 두 개의 문자열을 동일하게 만들기 위해서 몇 번의 문자열 조작이 필요한지에 주목하여 단어의 거리를 구한다.

 

ex) "가나다라"와 "가마바라"의 유사도 분석

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

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

 

 

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

레벤슈타인 거리를 구하는 방법은 다음과 같다.

 

<lev-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)

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

실행 결과

 

---

N-gram으로 유사도 구하기

N-gram

: 텍스트에서 "이웃한 N개의 문자"를 의미한다

서로 다른 2개의 문장을 N-gram으로 비교해보면 출현하는 단어의 종류와 빈도를 확인할 수 있다.

논문 도용 등에 사용된다.

 

ex) 아래 두 문장의 유사도 확인하기

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

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

 

<ngram-test.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)

실행결과는 다음과 같다

실행 결과

이처럼 N-gram을 이용하면 쉽게 문장의 유사도를 확인할 수 있다. 문장을 도용했는지 확인하고 싶다면 N-gram을 활용해 유사도가 높은지 조사하면 된다.