[자료구조] 08. Trie(트라이)를 사용하여 검색 자동완성 기능을 구현해 본다.

17 Nov 2020 in Computer-Science

Trie(트라이)를 사용하여 검색 자동완성 기능을 구현해 본다.

Trie 란?

그림과 같이 트리구조를 가지며 문자열을 효율적으로 검색하고 저장하기위해 단어의 글자를 노드로 이어져있으며 단어의 끝에는 끝을 확인 할 수 있는 확인자가 있는 구조이다.

자동완성에서 Trie를 쓰는 이유?

String 구조를 트리에 담아 검색한다고 가정해보자

트리의 대표적인 구조인 이진탐색트리와 비교해보면 String의 길이를 M이라고 했을때, 시간복잡도는 O(M*log(N)) 이고

Trie의 경우 시간복잡도는 O(M)이 된다. 즉, 시간복잡도면에서 우월한 성능을 보이기 때문에 자동완성에서 Trie를 사용한다고 볼 수 있다.

구현 코드

1. 메인 코드

# 노드 설정
class Node():
    def __init__(self, value):
        self.value = value
        self.fin = False # 단어가 끝났을 경우 해당 단어를 집어넣는다.
        self.next = dict()

# 트라이 설정
class Trie():
    def __init__(self):
        self.head = Node(None)
     
    # 단어 삽입
    def insert(self, string):
        curr_node = self.head
        
        for word in string:
            if word not in curr_node.next:
                curr_node.next[word] = Node(word)
            curr_node = curr_node.next[word]
        
        curr_node.fin = string
    
    # 자동완성 
    def auto_complete(self, string):
        curr_node = self.head
        
        result = []
        
        for word in string:
            if word not in curr_node.next:
                return "추천 검색어가 없습니다."
            else:
                curr_node = curr_node.next[word]
        
        if curr_node.fin:
            result.append(curr_node.fin)
            
        stack = list(curr_node.next.values())
        
        while stack:
            v = stack.pop()
            
            if v.fin:
                result.append(v.fin)
            stack.extend(list(v.next.values()))
            
        return print(result)
    
    # 검색기록 출력
    def show_list(self):
        curr_node = self.head
        stack = list(curr_node.next.values())
        result = []
        
        while stack:
            v = stack.pop()
            
            if v.fin:
                result.append(v.fin)
            stack.extend(list(v.next.values()))
        return print(result)

2. 결과

# 초기화
T = Trie()

# 단어 삽입
T.insert('string')
T.insert('str')
T.insert('stress')
T.insert('star')
T.insert('singer')
T.insert('sign')
T.insert('starcraft')
T.insert('southkorea')
T.insert('south korea')

# 자동완성 기능
T.auto_complete('soo')
T.auto_complete('st')
T.auto_complete('star')
T.auto_complete('south')

# 검색기록 출력
T.show_list()

# Result

# 자동완성
'추천 검색어가 없습니다.'
['star', 'starcraft', 'str', 'stress', 'string']
['star', 'starcraft']
['south korea', 'southkorea']

# 검색기록
['south korea', 'southkorea', 'sign', 'singer', 'star', 'starcraft', 'str', 'stress', 'string']