6부_5장 N-gram으로 문장유사도 분석하기

01. 문장의 유사도 분석

어떤 두 문장(또는 단어)이 비슷한지, 서로 관련있는 문장인지 분석해본다.

방법 : 레벤슈타인 거리 계산, n-gram 사용 

 

 

02. 레벤슈타인 거리 

레벤슈타인 거리 (편집거리): 두 개의 문자열이 어느 정도 다른지 나타내는 것

 

예시_ "가나다라"와 "가마바라"는 얼마나 유사할까?

   -> "가나다라"를 가마바라"로 편집할 때 몇 번의 문자열 조작이 필요할지로 단어의 거리를 구한다.

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

문자열 조작을 나타낸 표에 따라, 문자열을 조작하기 위해선 2번의 조작이 필요하다.

=> 편집비용(조작횟수)는 2이고, 2는 레벤슈타인 거리이다. 

 

 

 

[실습1]_ 파이썬으로 레벤슈타인 거리를 계산하는 프로그램

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

단계1.  <코드>  

'''lev-distance.py'''

#레벤슈타인 거리 구하기
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+1)준비하기 --(#1)
    matrix= [ []for i in range(a_len+1)] #a길이+1 만큼의 크기의 배열준비
    for i in range(a_len+1) :
        matrix[i] = [0 for j in range(b_len+1)] #0으로 초기화(2차원배열)    
   
    #0일때 초기값을 설정 (#2)
    for i in range(a_len+1):
        matrix[i][0]=i   
    for j in range(b_len+1):
        matrix[0][j]=j
    
    #표 채우기 --(#3)
    for i in range(1,a_len+1):
        ac=a[i-1]  #a의 첫번째 글자(=[0]) 부터 시작
        for j in range(1, b_len+1):
            bc=b[j-1] #b의 첫번째글자(=[0]) 부터 시작
            cost=0 if (ac ==bc) else 1 #a[i-1]과 b[j-1] 이 같다면 비용(cost)은 0. 같지 않으면 1
            matrix[i][j] = min([  #min 함수 : 최소값을 돌려줌; 
            #a의 i번째까지의 문자와 b의 j번째까지의 문자를 비교해서, 삽입/제거/변경 비용 중 최소값으로 표를 채운다.
                matrix[i-1][j] + 1,     # 문자 삽입
                matrix[i][j-1] + 1,     # 문자 제거
                matrix[i-1][j-1] + cost # 문자 변경
            ])
    return matrix[a_len][b_len] #최종적으로는, 표의 오른쪽 아래에 있는 값이 최소거리(레벤슈타인 거리)가 된다.
    #ㄴ함수 calc_distance 끝


#"가나다라"와 "가마바라"의 거리 --(#4)
print("'가나다라'와 '가마바라'의 거리: ",end='')
print(calc_distance("가나다라", "가마바라"))

#실행 예
samples = ["신촌역","신천군","신천역","신발","마곡역"]
base = samples[0]
r = sorted(samples, key = lambda n: calc_distance(base, n)) #base(신촌역)과 samples의 각 원소 비교
for n in r:
    print(calc_distance(base, n), n)

(주석으로 자세한 설명 써놓음.)

 

 

단계2. <코드 설명>

1. 레벤슈타인 거리를 계산하기 위해 2차원 배열(matrix)를 준비한다. _(#1)

예를 들어, 글자 '가나다라'와 '가마바라'를 비교한다고 가정하면, 다음과 같은 배열을 만든다.

i/j	.	가	나	다	라
.
가
마
바
라

 

2. 그리고 위의 2차원 배열을 0행(열)일때의 초기값을 지정해준다.  _(#2)

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

 

3. 다음 알고리즘에 따라 표를 채우게 된다.  _(#3)

문자열a의 i번째까지의 문자 VS 문자열 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 (레벤슈타인 거리)

++ 표 채우는 원리 ++

 matrix[i][j] = min([  #min 함수 : 최소값을 돌려줌; 
            #a의 i번째까지의 문자와 b의 j번째까지의 문자를 비교해서, 삽입/제거/변경 비용 중 최소값으로 표를 채운다.
                matrix[i-1][j] + 1,     # 문자 삽입
                matrix[i][j-1] + 1,     # 문자 제거
                matrix[i-1][j-1] + cost # 문자 변경
            ])

이 부분 코드의 원리를 그림(표)로 작성해 보았다.

 

 

4. 샘플을 이용하여 레벤슈타인 거리를 테스트 해본다. _(#4)

위의 소스에서 테스트한 샘플들은

'가나다라'와 '가마바라' 를 비교하는 것과, 

"신촌역","신천군","신천역","신발","마곡역" 으로 테스트 해 보는 것이다. 

(위의 코드에서는 sorted 함수에 key를 lambda로 사용하여, 신촌역을 신촌역, 신천역, 신발, 마곡역 에 비교를 하는 과정을 거친다. )

 

 

단계3. <실행 결과>

샘플1. '가나다라'와 '가마바라'

'가나다라'와 '가마바라'의 라벤슈타인 거리는 2이다.

(위에서 언급했지만, 라벤슈타인은 문자열 a에서 b로 편집할 때 몇 번의 문자열 조작이 필요한지를 나타낸다.)

즉 , '가나다라'에서 '가마바라'로 편집하기 위해선 2번의 문자열 조작이 필요하다. 

 

샘플2.'신촌역','신천군','신발','마곡역'

'신촌역'과 '신촌역'의 라벤슈타인 거리는 0이고, (문자열 조작 필요 없음) 

'신촌역'과 '신천역'의 라벤슈타인 거리는 1이다.  ('촌'->'천' 의 문자열 조작 1번 필요)

'신촌역'과 '마곡역'의 라벤슈타인 거리는 2이다. ('신'->'마', '촌'->'곡' 의 문자열 조작 2번 필요)

 

 

지금까지는 라벤슈타인 거리를 사용하여 문장의 유사도를 구하였다.이번에는 다른방법으로 "N-gram"을 이용하여 유사도를 구해보자.

 

 

 

 

03. N-gram으로 유사도 구하기

N-gram : 텍스트에서 이웃한 N개의 문자 

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

 

 

예시_N-gram을 2문장으로 생각 시(2 -gram), 다음 2개의 문장은 어느 정도 유사할까?

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

우선 먼저, [A]문장과 [B]문장을 각각 글자 2개씩 끊는다.

>>>ngram(a,2) ['오늘','늘 ' ,' 강', '강남', '남에','에서',' 서', ' 맛', '맛있, '있는' ,'  는' ,' 스', '스파','파게', '게티',' 티를', '를 ', ' 먹', '먹었', ' 었다', '다.']  >>>ngram(b,2) ['강남', '남에', '에서', '서 ', '먹 ', '먹었', '었던', '던 ', ' 오', '오늘', '늘의', '의 ', ' 스', '스파', '파게', '게티', '티는' , '는 ', ' 맛', '맛있', '있었', '었다', '다.']

이렇게 끊은 단어를 비교하면 문장의 유사도를 알 수 있다.  이를 이용하여 실제 코드를 짜본다. 

 

 

[실습2]_ N-gram으로 유사도 구하는 파이썬 프로그램

파이썬으로 N-gram을 이용하여 유사도를 구하는 프로그램을 짜본다.

단계1.  <코드>  

def ngram(s, num):  #num : 몇글자씩 끊을 건지
    res=[]
    slen=len(s)-num+1 # slen : 끊었을 때 나오는 개수
    for i in range (slen):
        ss=s[i:i+num] #num만큼 s문자열에서 단어 자르기
        res.append(ss) #자른 단어는 res배열에 저장
    return res

def diff_ngram(sa,sb,num):
    a=ngram(sa,num)	#a문자열을 num단어씩 자른 배열
    b=ngram(sb,num) #b문자열을 num단어씩 자른 배열
    r=[]
    cnt=0
    for i in a:
        for j in b:
            if i==j:    #a에서 자른 단어가 b에도 있다면
                cnt+=1   #cnt++
                r.append(i) #중복되는 단어i를 r배열에 추가한다.
    return cnt/len(a), r #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. <코드 설명>

def ngram(s, num) 함수 

num만큼 묶음으로 문장을 잘라주는 함수

 

def diff_ngram(sa, sb, num) 함수

sa와 sb문장을 ngram 함수를 호출하여, 단어를 구분한 뒤, 

공통된 단어가 있는지 확인하고, 이를 배열로 return해준다. 또한, (중복되는 횟수/sa의 길이)='적중률' 또한 return한다.

 

 

 

 

단계3. <실행 결과>

샘플1. 

a와 b문장을 2-gram으로 비교시 0.76(76%), 3-gram으로 비교하면 0.45(45%)가 같다는 것을 알 수 있다.

 

샘플2.

a="머신러닝은 매우 재미있는 기술이라 공부하고 있습니다."

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

이 두 문장을 n-gram으로 비교해본다. 

유사도는 0.75(75%)로, 같은 내용을 순서만 바꾸는 것만으로도 유사도가 높게 나온것을 확인할 수 있다.

 

샘플3. 

a="파이썬 프로그래밍에서 중요한 것은 블록입니다."

b="겨울에는 충분한 수분을 보충해야 합니다."

위의 두 문장은 유사도가 떨어지는데, 2-gram시 유사도가 0.14(14%)로, 같은 것은 ['한','니다', '다.'] 밖에 없다. 

 

 

이처럼 N-gram을 이용하면 쉽게 문장의 유사도를 확인할  수 있다. 

 

 

 

< 결론 >

문장의 인용과 도용을 조사할 때는 텍스트 유사도를 확인하면 된다.

문장의 유사도를 확인하고 싶다면 레벤슈타인 거리 또는 N-gram을 활용하면 된다.

 

 

 

 

 

 

 

위 글은 [(파이썬을 이용한)머신러닝, 딥러닝 실전 개발 입문] 을 읽고 정리한 글입니다.