문장의 유사도 분석하기(레벤슈타인 거리, N-gram)

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)

/* result :
0 신촌역
1 신천역
2 신쵼
2 신천군
2 신발
2 마곡역
*/

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

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

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 = '강남에서 먹었던 오늘의 스파게티는 맛있었다.'

r2, word2 = diff_ngram(a, b, 2)
print('2-gram:', r2, word2)
# result : 2-gram: 0.7619047619047619 ['오늘', '강남', '남에', '에서', '서 ', ' 맛', '맛있', '는 ', ' 스', '스파', '파게', '게티', ' 먹', '먹었', '었다', '다.']

r3, word3 = diff_ngram(a, b, 3)
print('3-gram:', r3, word3)
# result : 3-gram: 0.45 ['강남에', '남에서', '에서 ', ' 맛있', ' 스파', '스파게', '파게티', ' 먹었', '었다.']