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

저번 Trie를 이용한 검색 자동완성의 연장선의 글이다.

브랜드 이름 검색어 자동완성 with Trie

브랜드 이름 검색어 자동완성 with Trie

저번 검색어 자동완성의 경우, 검색어를 앞글자부터 Trie로 구성하기 때문에 중간에 나온 단어의 경우

검색어 자동완성에 노출되지 않는 문제가 있다.

(예를 들어 “디”라는 단어를 칠 때 “디올” 은 나올 수 있지만 “아디다스”는 나오지 않는 문제가 있다.)

 

suffix Trie는 이 문제를 해결하기 위한 자료구조로

기존 Trie(prefix) 에 넣는 단어의 말미(suffix)들을 추가로 넣는 작업을 수행한다.

이미지 출처 :  https://jindongpu.wordpress.com/2012/10/19/find-the-longest-palindrome-in-s/

가령 “ADIDAS” 라는 글자를 집어넣을 때는

"A D I D A S" -> 기존과 동일
"D I D A S" -> ADIDAS 의 suffix
"I D A S"
"D A S"
"A S"
"S"

라는 식으로 변경시켜 넣는다.

해당 변경점을 함수로 구현해보자.

def nameTokenize(test_name):
    name_token_list = []
    for i in range(len(test_name)):
        if test_name[i] == " ": #띄어쓰기가 맨처음일 경우 건너뛰기
            continue
        name_token_list.append(test_name[i:])
    return name_token_list

들어오는 str 변수를 한 글자씩 제외시켜 suffix를 구성해준다.

 

한글의 경우, 알파벳과 다르기 때문에 저번 글처럼

초성, 초성+중성, 초+중+종성 식으로 변형시켜주는데

그전에 suffix를 구분시켜준다.

저번 글에 나온 단어 → 초성, 초성+중성, 초+중+종성 함수~

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

결과는 아래와 같다.

여기에 suffix 함수를 추가해 입력을 변형시켜준다.

 

 

나머지는 동일하다.

위 함수의 결과 나온 suffix 단어들을 Trie에 동일하게 집어넣고, 결과로 보여준다.

 

trie의 node가 될 클래스를 먼저 정의해준다. 지난번과 다르게

prefix를 담을 리스트 변수와 suffix를 담을 리스트 변수를 따로 만들어 준다.

#node
class Node:
    def __init__(self):
        self.children = {}
        self.prefix_data = []
        self.suffix_data = []

각 노드는 검색어 자동완성을 위한 결과를 뱉기 위해 검색어를 저장하는데

저번 글의 경우, 모든 검색어를 다 저장했다. → 굳이 그럴 이유가 있나?

싶어서 상품수가 많은 순으로 n개만 정렬해 저장하기로 하자.

 

prefix_data, suffix_data 리스트에 상품수(merchan_count) 순으로 정렬해 삽입 후, (binary search 이용)

n개 이상이 되면 개수가 작은 순으로 하나씩 지워준다.

class Node:
    def __init__(self):
        self.children = {}
        self.prefix_data = []
        self.suffix_data = []
# binary search 를 이용해 상품수 순으로 정렬해 삽입
    def data_insert(self, data, text, count):
        left = 0
        right = len(data)
        while left < right:
            mid = (left+right) // 2
            if data[mid][1] == count:
                left = mid
                break
            else:
                if data[mid][1] < count:
                    left = mid+1
                else:
                    right = mid
        data.insert(left, (text, count))
# prefix 기준으로 삽입후, 검색어가 10개 이상일 경우 -> 10개로 맞춰 제거
    def prefix_data_insert(self, text, count):
        data = self.prefix_data
        self.data_insert(data, text, count)
        if len(self.prefix_data) > 10:
            self.prefix_data = self.prefix_data[-10:]
# suffix 기준으로 삽입후, 검색어가 10개 이상일 경우 -> 10개로 맞춰 제거        
    def suffix_data_insert(self, text, count):
        data = self.suffix_data
        self.data_insert(data, text, count)
        if len(self.suffix_data) > 10:
            self.suffix_data = self.suffix_data[-10:]

Trie를 구성할 차례다.

Trie의 Node 클래스를 이용해, Trie 자료구조를 구성하는데 필요한 메서드는 다음과 같다.

1. insert
   1. prefix_insert (영어 prefix 용 삽입 메서드)
   2. prefix_kor_insert (한글 prefix 용 삽입 메서드)
   3. suffix_insert (영&한 suffix 용 삽입 메서드)
2. query
   1. query (영단어 검색 메서드)
   2. query_kor (한글 검색 메서드)

class Trie:
    def __init__(self): # Trie를 Node로 구성
        self.head = Node()

1-a. prefix_insert (영어 prefix 용 삽입 메소드)

#Trie의 메소드
def prefix_insert(self, eng_name, merchan_count):
    text = eng_name.lower() # 대문자, 소문자 상관없이 검색을 위해 소문자로 일괄 변경
    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(eng_name, merchan_count)

1-b. prefix_kor_insert (한글 prefix 용 삽입 메소드)

#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)

1-c.suffix_insert (영&한 suffix 용 삽입 메소드)

#Trie의 메소드
def suffix_insert(self, text, name, merchan_count):
    text = text.lower()
    curr = self.head
    for t in text:
        if t not in curr.children:
            curr.children[t] = Node()
        curr = curr.children[t]
        curr.suffix_data_insert(name, merchan_count)

2-a. query (영단어 검색 메소드)

#Trie의 메소드
def query(self, text):
    text = text.lower()
    curr = self.head
    for t in text:
        if t not in curr.children:
            break
        else:
            curr = curr.children[t]
    
    data = {}
    data["prefix_result"] = curr.prefix_data[::-1]
    data["suffix_result"] = curr.suffix_data[::-1]
    return data

2-b. query_kor (한글 검색 메소드)

#Trie의 메소드
def query_kor(self, text):
    kor_text = return_brand_name_with_jamo(text)
    return self.query(kor_text)

이제 짠 코드가 제대로 동작하는지 확인해보자.

데이터는 다음과 같다.

먼저 insert&query (영어)

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)

결과를 살펴보면 의도한 대로 “APA” 로 시작하는 브랜드 (prefix_data)와

“APA”가 포함된 브랜드 (suffix_data)가 제대로 나오는 걸 확인할 수 있다.

이번엔 한글을 insert&query

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)

결과를 살펴보자면 “디”로 시작하는 브랜드(prefix_data)와 “디”가 포함된 브랜드(suffix_data)가

제대로 나오는 걸 확인할 수 있다.

 

 

지난번에 이어 suffix Trie를 살펴봤다.

이제 중간에 등장한 단어 결과도 보여줄 수 있다는 장점이 있지만, 여전히 발전시킬 여지는 있다.

 

만약 사용자가 오타로 검색을 한다면? (예를 들어 "아디다스"가 아니라 "아다디스"로 검색을 한다면)

여전히 검색 결과는 나오지 않을 것이다.

오타가 들어올 때, 사용자가 치려던 단어를 유추할 수 있을까? 좀 더 찾아봐야겠다.