편집거리 알고리즘을 통한 검색어 자동완성 보정 (ft . Levenshtein Distance)

저번 검색어 자동완성 글 말미에 오타가 들어가 있는 경우, 제대로 된 단어로 유추될 수 있으면 좋겠다는 생각을 했는데 마침 적당한 알고리즘이 있어서 실제로 실습해봤다.

브랜드 이름 검색어 자동완성 2 (with Suffix Trie)

레벤 슈타인 알고리즘이라고… 이름부터 어렵지만 막상 까 보면 생각보다 별거 없는 알고리즘이 있다.

두 문자열이 얼마나 다른지 값으로 나타내주는 알고리즘으로

• 문자를 삽입, 삭제, 치환하여 다른 문자열로 변형하는데 필요한 최소 횟수
• 철자 검사기 등에서 두 문자열이 어느 정도 유사한지 값으로 나타내는 방법의 하나
• 1965년 러시아의 브라디미르 레벤 슈타인이 고안함
• 같으면 0, 다르면 1 이상

위와 같은 특징을 가지고 있다.

출처 : https://zetawiki.com/wiki/레벤슈타인_거리

 

그럼 어떻게 두 문자열이 다른지 알아내냐?

S: 원래 스트링 T: 비교 스트링이라 했을 때 S -> T로 변환하는데 필요한

삽입, 삭제, 대치 연산의 최소 비용(최소 편집 횟수)을 구함으로써 판단한다.

(비용이 작게 나올수록 유사도가 큼)

식은 아래와 같이 쓴다.(고 한다.)

출처 : https://en.wikipedia.org/wiki/Levenshtein_distance

머.. 이런 거 난 잘 모르겠고, 정리하자면

(출처 : https://renuevo.github.io/data-science/levenshtein-distance/ )

 

두 단어의 길이로 된 행렬을 만들고

삽입이 필요 : 현재 칸의 왼쪽 값 + 1

삭제가 필요 : 현재 칸의 위쪽 값 + 1

수정이 필요 : 현재 칸의 대각선 값 + 1

 

만약 adiddas → adidas로 변환한다면 “d” 하나만 삭제하면 되므로 편집 거리는 1 이 된다.

 

행렬로 표현해보자.

빈 문자열과 각 문자들 간의 편집거리는 문자 길이만큼이므로 먼저 값을 채워준다.

adidas의 a와 adiddas를 비교했을 때 모습

a / ad → d가 하나 추가되므로 min(위, 옆, 대각선 값) + 1 = 0 + 1 = 1

a / adidda → a 가 같으므로 대각선 값을 그대로 가져오기 = 5

계속 진행해보면

행렬의 마지막 부분이 두 단어의 편집 거리의 최종 값이다.

adidas와 adiddas의 최종 편집 거리는 1로 이걸 코드로 옮겨보자.

text = "adidas"
compare_text_list = ["adiddas", "adidus","addiss","dadiffs"] 

def levDistance(text1, text2):
    row_len = len(text1)+1
    col_len = len(text2)+1
    mat = [[0 for n in range(col_len)] for r in range(row_len)]

    for i in range(row_len):
        mat[i][0] = i
    for j in range(col_len):
        mat[0][j] = j
    
    for i in range(1, row_len):
        for j in range(1, col_len):
            a = text1[i-1]
            b = text2[j-1]

            match = 0 if a == b else 1
            replace = mat[i-1][j-1] + match
            insert = mat[i-1][j] + 1
            delete = mat[i][j-1] + 1

            mat[i][j] = min(replace, insert, delete)
    return mat[-1][-1]

for compare in compare_text_list:
    print(text, compare, levDistance(text, compare))

 

위 예시 행렬과 동일한 결과가 나온 걸 확인할 수 있다.

더 자세한 설명은 아래의 링크에서 확인하자.. (솔직히 아래의 블로그 글이 더 잘 설명했다.)

https://renuevo.github.io/data-science/levenshtein-distance/

[DataScience] Levenshtein Distance (편집거리 알고리즘) - 문장 유사도 분석을 어떻게 하는가?

 

이 함수를 이전 suffix Trie에 추가해보자.

 

 

먼저 데이터를 불러와 주고…

위에서 정의한 함수를 선언해준다.

def levDistance(text1, text2):
    row_len = len(text1)+1
    col_len = len(text2)+1
    mat = [[0 for n in range(col_len)] for r in range(row_len)]

    for i in range(row_len):
        mat[i][0] = i
    for j in range(col_len):
        mat[0][j] = j
    
    for i in range(1, row_len):
        for j in range(1, col_len):
            a = text1[i-1]
            b = text2[j-1]

            match = 0 if a == b else 1
            replace = mat[i-1][j-1] + match
            insert = mat[i-1][j] + 1
            delete = mat[i][j-1] + 1

            mat[i][j] = min(replace, insert, delete)

    return mat[-1][-1]

levDistance("adidas","adiddas") // 결과는 1

이전 블로그 글의 Node 클래스와 Trie 클래스를 선언하는데 달라지는 부분은 Trie 클래스의 편집 거리 추가 부분이다.

class Trie:
    ...
    def query(self, text):
        text = text.lower()
        curr = self.head
        for t in text:
            if t not in curr.children:
                self.suggest(curr, text) # 노드를 타고 들어가다 발견하지 못하면(ex.오타)
                break
            else:
                curr = curr.children[t]
        
        data = {}
        data["prefix_result"] = curr.prefix_data[::-1]
        data["suffix_result"] = curr.suffix_data[::-1]
        return data
    # 오타와 가장 비슷한 단어를 현재 노드의 단어중 고르기
    def suggest(self, node, text): 
        candidate_ = node.prefix_data[::-1]
        
        lev_list = []
        for can_text in candidate_:
            lev_distance = levDistance(can_text[0].lower(), text.lower())
            lev_list.append((can_text[0], lev_distance))
        
        lev_list = sorted(lev_list, key=lambda x : x[1])
        
        print("do you mean \\"{}\\" ?".format(lev_list[0][0]))

위 코드가 잘 동작하는지 테스트해보자.

먼저 데이터를 삽입하고

trie = Trie()

for i, rows in df.iterrows():
    eng_name = rows['eng_name']
    merchan_count = rows['merchan_count']

    eng_name_token_list = nameTokenize(eng_name)
    
    trie.prefix_insert(eng_name, merchan_count)
    
    for eng_name_token in eng_name_token_list[1:]:
        trie.suffix_insert(eng_name_token, eng_name, merchan_count)

“adidaas”를 검색해보자.

 

오…

한글에 대해서도 동작 하나 보자.

한글의 경우, 이전 글에서 적어 놨듯이 자모음이 순차적으로 검색되기 때문에 분해가 필요하다.

from jamo import h2j, j2hcj, j2h, j2hcj

def return_brand_name_with_jamo(text):
    return_value = ""
    for t in text:
        jamo_list = j2hcj(h2j(t))
        if len(jamo_list) == 2:
            return_value += jamo_list[0]
            return_value += j2h(*jamo_list)
        else:
            return_value += jamo_list[0]
            for i in range(2,len(jamo_list)+1):
                han = j2h(*jamo_list[:i])
                return_value += han
    return return_value

text = "아디다스"
return_brand_name_with_jamo(text)

해당 자모음 분해 문자열을 넣는 함수, 검색 함수를 Trie 클래스에 만들어 넣어준다.

class Trie:
    ...
    def prefix_kor_insert(self, kor_name, merchan_count):
        text = return_brand_name_with_jamo(kor_name)
        curr = self.head
        for t in text:
            if t not in curr.children:
                curr.children[t] = Node()
            curr = curr.children[t]
            curr.prefix_data_insert(kor_name, merchan_count)

		def query_kor(self, text):
        kor_text = return_brand_name_with_jamo(text)
        return self.query(kor_text)

		def query(self, text):
        text = text.lower()
        curr = self.head
        for t in text:
            if t not in curr.children:
                self.suggest(curr, text) # 노드를 타고 들어가다 발견하지 못하면(ex.오타)
                break
            else:
                curr = curr.children[t]
        
        data = {}
        data["prefix_result"] = curr.prefix_data[::-1]
        data["suffix_result"] = curr.suffix_data[::-1]
        return data

    # 오타와 가장 비슷한 단어를 현재 노드의 단어중 고르기
    def suggest(self, node, text): 
        candidate_ = node.prefix_data[::-1]
        
        lev_list = []
        for can_text in candidate_:
            lev_distance = levDistance(can_text[0].lower(), text.lower())
            lev_list.append((can_text[0], lev_distance))
        
        lev_list = sorted(lev_list, key=lambda x : x[1])
        
        print("do you mean \\"{}\\" ?".format(lev_list[0][0]))

넣고 테스트해보자.

trie = Trie()

for i, rows in df.iterrows():     
    kor_name = rows['kor_name']
    merchan_count = rows['merchan_count']
    
    kor_name_token_list = []
    kor_suffix = nameTokenize(kor_name)
    for suffix in kor_suffix:
        kor_name_token_list.append(return_brand_name_with_jamo(suffix))
        
    trie.prefix_kor_insert(kor_name, merchan_count)
    
    for kor_name_token in kor_name_token_list[1:]:
        trie.suffix_insert(kor_name_token, kor_name, merchan_count)

오… 오타에 동작하는 구만!

하지만 엄청난 결점을 발견했다. Trie의 경우, 앞 단어부터 검색하기 때문에

“아다디스” 같은 단어의 경우 “ㅇ아ㄷ다…” 식으로 타고 내려간다. 그래서

아디다스가 아니라 아담스가 먼저 나오게 되는데 이건 내가 원하던 결과가 아니다..

그래서 레벤 슈타인 알고리즘에 “전치” 가 추가된 알고리즘이 있는데 이름은

Damerau-Levenshtein distance - Wikipedia

Damerau–Levenshtein distance - Wikipedia

위 레벤슈타인 알고리즘에

앞 뒤 글자를 바꿨을 때 값이 최소면 해당 값을 가져다 +1 해준다.

코드는 아래와 같다.

text = "adidas"
compare_text_list = ["adidus","addiss","dadiffs", "adiads"] 

def levDistance(text1, text2):
    row_len = len(text1)
    col_len = len(text2)
    mat = [[0 for n in range(col_len)] for r in range(row_len)]

    for i in range(row_len):
        mat[i][0] = i
    for j in range(col_len):
        mat[0][j] = j
    
    for i in range(1, row_len):
        for j in range(1, col_len):
            a = text1[i-1]
            b = text2[j-1]

            cost = 0 if a == b else 1
            replace = mat[i-1][j-1] + cost
            insert = mat[i-1][j] + 1
            delete = mat[i][j-1] + 1

            mat[i][j] = min(replace, insert, delete)
            
						# 추가된 부분
            if j > 1 and j-1 < len(text1) and i > 0 and i-1 < len(text2):
                if text1[i] == text2[j-1] and text1[i-1] == text2[j]:
                    mat[i][j] = min(mat[i-1][j-1], mat[i-2][j-2]+cost)

    # for i in range(row_len):
    #     print(mat[i])       

    return mat[-1][-1]
# levDistance("유사도나 분석 할까요", "얼마나 분석이 될까요")

for compare in compare_text_list:
    print(text, compare, levDistance(text, compare))

 

그렇지만 이 방법은 문자열과 문자열을 직접 비교할 때 말곤 사용할 수 없다.

이번 경우는 “아다디스” → “아디다스”인데 이미 “아다..” 로 나온 문자 열중엔 아디다스가 나올 수 없으므로

결과는 동일하다.

근데 이제 Trie 가지고 검색어 자동완성 글 적는 게 약간 지겨워져서 글은 여기까지!