레벨슈타인 거리를 계산 ＆ N - gram으로 유사도 구하기

레벨슈타인 거리 알고리즘

레벤슈타인 거리는 두 단어 또는 문장의 차이를 통해 거리를 수치로 나타내는 것이다.
철자 오류 수정, 비슷한 어구 검색 등에 사용되고, 의학 분야에서는 DNA 배열의 유사성을 판단할 때도 사용하고 있다.

예를 들어
‘가나다라’를 ‘가마바라’로 수정할 때 몇 번의 수정이 필요한 지를 거리로 나타낼 수 있다.

 

0 가나다라
1 가’마’다라
2 가마’바’라

 

‘가나다라’-> ‘가마바라’는 거리가 2임을 알 수 있다.

코드로 알아보자.

 

def calc_distance(a, b):
    if a == b:
        return 0
    a_len = len(a)
    b_len = len(b)
    if a == "":
        return b_len
    if b == "":
        return a_len
    # 2차원 표 (a_len+1, b_len+2) 준비하기
    matrix = [[] for i in range(a_len+1)]
    for i in range(a_len+1):
        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
    # 표 채우기
    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]

print(calc_distance('가나다라', '가마바라'))
# result : 2

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 알고리즘

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개의 문자를 의미한다.
서로 다른 2개의 문장을 N-gram으로 비교해보면 출현하는 단어의 종류와 빈도수, 유사도를 확인할 수 있다.
N-gram은 논문 도용, 소스코드간 유사도 등에도 사용할 수 있다.

 

2문장씩 끊었을때의 유사도는 0.76, 3문장씩 끊었을때의 유사도는 0.45로 2문장씩 끊었을 때의 유사도가 더 높았다.
N개의 문장을 끊을지는 hyper parameter가 될 것 같다. 유사도를 구할 문장에따라 적절한 값을 입력하면 좋은 결과가 있을 것 같다.