[17장] 트라이(trie)해 보는 것도 나쁘지 않다

자동완성 기능이 어떻게 동작하는지 궁금해본적이 있는가? 단어들을 어떤 자료 구조에 저장해야 효율적으로 구현이 가능할까? 케이스별로 한번 살펴보자

	검색과정	시간복잡도
정렬X 배열	모든 단어를 검색해야 한다	O(N)
정렬된 배열	이진 검색	O(logN)
해시 테이블	단어를 통짜로 해싱해서 메모리 위치를 결정하므로 일부의 단어로 찾는다는거 자체가 말이 안된다	X

정렬된 배열이 O(logN)으로 빠르긴 하다. 그런데 트라이 자료구조를 사용하면 O(1)의 속도로 원하는 단어에 접근이 가능하다! 실제로 트라이는 자동완성, 자동수정, IP주소 처리, 전화번호 처리 등의 애플리케이션에 쓰인다.

1. 트라이(trie)
트리의 한 종류로, 자동 완성 텍스트 기능에 매우 이상적인 자료구조. 근데 왜 발음이 트라이일까? 트라이는 추출(retrieval)이란 단어에서 유래했는데 trie를 트리라고 읽으면 보편적인 트리 자료 구조와 헷갈리므로 트라이라고 발음한다. 어떤 책에서는 트리픽스 트리, 디지털 트리라고도 부르나 트라이라는 이름이 가장 유명하다.

또한, 트라이의 구현방법이 매우 다양하기 때문에 참고서적에 따라 생김새가 조금씩 다를 수 있으나 어떤 모양새든 개념 자체는 거의 비슷하다.

1.1 트라이 노드(trie node)
트라이도 트리의 한 종류지만 이진 트리는 아니다. 즉, 자식 노드의 개수에 제한이 없다. 이 책에선 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 키는 알파벳이고 값은 트라이의 다른 노드다.

바로 뒤에서도 설명하겠지만 이런 모양새가 된다

코드 구현은 매우 간단한데, 해시 테이블만 포함시켜주면 된다

class TrieNode:
    def __init__(self):
        self.children = {}

1.2 트라이 클래스
완벽하게 트라이를 만드려면 루트 노드를 추적하는 Trie 클래스도 별도로 필요하다. 아래처럼 구현해서 새 Trie 생성시 빈 TrieNode가 루트가 되도록 설정하자.

class Trie:
    def __init__(self):
        self.root = TrieNode()

2. 단어 저장
자동완성에 많이 쓰는 자료구조라고 했으니 단어 저장이 가장 중요한 부분이다. 예를 들어, ace, act, bad, cat 이란 단어를 저장한다고 하면 트라이는 아래 구조가 된다.

2.1 asterisk(별표)
단어가 끝났음을 의미하는 용도로 '*' 키가 담긴 노드를 추가하는데, '*'는 단어의 일부도 단어일 수 있음을 나타내는데 필요해서 굳이 넣어주는 것이다. 예를 들어, [ ace, act, bad, bake, bat, batter, cab, cat, catnap, catnip ]을 포함하는 트라이를 만들면 아래처럼 되는데, bat - batter처럼 bat라는 단어가 batter의 일부분이 될 수 있음을 나타낸다.

3. 트라이 검색
트라이 연산의 꽃이자 목적인데, 어떤 단어의 앞부분인지 알아내는 알고리즘을 구현해보자.

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def search(self, word):
        currentNode = self.root

        for char in word:
            if currentNode.children.get(char):
                currentNode = currentNode.children[char]
            else:
                return None
        
        return currentNode

[1] currentNode라는 변수를 만든다(알고리즘 시작시 루트 노드를 가리킨다)
[2] 검색 문자열의 각 문자를 순회한다
[3] 각 문자를 키로 하는 자식이 있는지 본다
[4] 자식이 없으면 검색 문자열이 트라이에 없다는 뜻이다 ( return None )
[5] 자식이 있으면 currentNode에 해당 자식 노드를 할당하고 2~5단계를 반복한다
[6] 검색 문자열을 끝까지 순회했으면 검색 문자열이 있다는 뜻이다

4. 검색 효율성
위 코드의 루프를 보면 알겠지만 3글자면 3번 순회, 5글자면 5번 순회한다. 즉, 트라이 자체가 얼마나 큰지에 상관없이(트라이내 데이터가 100만개든 1억개든) 검색하는 단어의 갯수에 달려있다.

여기서 사소한 문제가 생기는데, O(N)이라고 표현하기엔 N은 자료구조 안의 데이터의 갯수를 의미하므로 오해의 소지가 있다. 또한 O(1)이라고 말하기엔 검색 문자열의 길이에 따라 달라지므로 엄연히 상수시간은 아니다. 그러므로 이 책에선 O(K)라고 표현하자. 뭐 어찌됐든 엄청나게 효율적이라는 것만은 알겠다.

5. 트라이 삽입

class Trie:
	# 생략...
    
    def insert(self, word):
        currentNode = self.root

        for char in word:
            if currentNode.children.get(char):
                currentNode = currentNode.children[char]
            else:
                newNode = TrieNode()
                currentNode.children[char] = newNode
                
                currentNode = newNode
        
        currentNode.children["*"] = None

삽입 알고리즘도 사실상 검색과 동일하다. 문자열을 하나씩 검색하며 자식이 있는지 확인하고 없으면 추가해나가면 끝.
[1] currentNode 변수 생성 (알고리즘 시작시 루트 노드를 가리킨다)
[2] 삽입 문자열의 각 문자 순회
[3] currentNode의 자식에 각 문자를 키로 하는 노드가 있는지 확인
[4] 자식이 있으면 currentNode를 해당 자식 노드로 업데이트, 2단계로 돌아간다
[5] 자식이 없으면 새로운 자식노드를 만들고 currentNode에 새로 만든 노드를 할당, 2단계로 돌아간다
[6] 삽입 문자열의 마지막 문자까지 삽입이 끝나면 마지막 노드에 "*" 자식을 추가해 단어가 끝났음을 알린다

결국 이 과정도 O(K)밖에 걸리지 않는다.

6. 자동 완성 개발
6.1 단어 수집 메서드
자동완성 개발에 도움을 줄 헬퍼 메서드가 필요하다. 아래 코드는 트라이 내 모든 단어를 배열로 반환하는 메서드다.

def collectAllWords(self, node=None, word="", words=[]):
        currentNode = node or self.root

        for key, chiildNode in currentNode.children.items():
            if key == '*':
                words.append(word)
            else:
                self.collectAllWords(chilldNode, word+key, words)
            
            return words

6.2 자동 완성 마무리

    def autocomplete(self, prefix):
        currentNode = self.search(prefix)
        if no currentNode:
            return None
        return self.collectAllWords(currentNode, prefix)

7. 자동 완성 업그레이드

근데 생각해보면 유저가 입력할 만한 단어를 전부 보여주는게 꼭 훌륭한 자동 완성 기능은 아니다.

예를 들어, bal 이라고 입력했을때 ball, balance 같은 단어말고 잘 안쓰이는 단어들( balter, balletomanes, ... )이 굳이 보여야 할까? 이러한 문제는 트라이를 아주 조금만 수정하면 된다.

"*"를 할당할 때, 값이 항상 null이었으나, 자주 쓰는 정도에 따라 score를 부여하고 스코어에 따라 일부만 보여주면 끝이다.