레벤슈타인 거리를 이용해서 두 문장 비교하기

레벤슈타인 거리를 이용해서 두 문장 비교하기

---

레벤슈타인 거리는 독일의 레벤슈타인이라는 사람이 고안한 알고리즘이다. 

레벤슈타인 거리란 두개의 문장을 2차원 배열로 나타내어서 각 문장의 각 글자들을 비교하여 몇개의 글자가 다른지 구분하는 방법이다. 

 

알고리즘

1.이런식으로 [문장길이+1][문장길이 +1] 만큼의 2차원 배열을 만들어 주어야한다. 

2. [0][n]과 [n][0]을 모드 0 ~ 문장길이 만큼 초기화 

3.

 (1). 두 문장의 첫단어와 첫단어가 같으면 cost를 0으로 주고 [i-1][j-1] + cost만큼을 [i][j]에 집어넣는다. 

 (2). 첫문장의 첫단어와 두번째 문장의 두번째 단어가 다르면 두번째 단어를 제거해주어야 한다. [i-1][j] + 1 = [i][j]에 집어 넣어준다. 

 (3). 첫문장의 두번째 단어와 두번째 문장의 첫단어를 보면 첫문장 보다 두번째 문장이 단어의 개수가 적으므로 한단어를 더 추가 시켜 주어야한다.  따라서 [i][j-1]+1 = [i][j]을 해주면 된다, 

4. [i][j]는 위의 세경우 중에 가장 값이 작은 것을 넣어준다. 

5. [배열 크기 -1 ] [배열크기 -1]의 값을 반환 시켜준다. 이값이 서로 다른 단어의 개수 

def leven(aText,bText):
    aLen = len(aText)+1
    bLen = len(bText)+1
    array = [ [] for a in range(aLen) ]
    for i in range(aLen):
        array[i] = [0 for a in range(bLen)]
    for i in range(bLen):
        array[0][i] = i
    for i in range(aLen):
        array[i][0] = i
    cost = 0
    for i in range(1,aLen):
        for j in range(1,bLen):
           if aText[i-1] != bText[j-1]:
               cost = 1
           else :
               cost = 0
           addNum = array[i-1][j] + 1 #추가
           minusNum = array[i][j-1] + 1 #감소
           modiNum = array[i-1][j-1]+cost #
           minNum = min([addNum,minusNum,modiNum])
           array[i][j] = minNum

    return array[aLen-1][bLen-1]
leven("가나다라", "가마바라")
samples = ["신발","신촌역","신천군","신천역","마곡역"]
result = sorted(samples, key = lambda x  : leven("신촌역",x))


for i in result:
    print(i, ":",leven("신촌역",i))