Computer Science/Algorithm

[책] 누구나 자료구조와 알고리즘 - 17장 트라이(trie)해 보는 것도 나쁘지 않다

지안22 2024. 1. 1. 18:37

 

https://product.kyobobook.co.kr/detail/S000001834743

 

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

누구나 자료 구조와 알고리즘 | 사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자 수학 용어와 전문 용어가 아니어도 이해한다 이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거

product.kyobobook.co.kr

 

다음으로 읽을 단원은 14장 이지만, 트라이가 궁금해 17장 먼저 읽기로 했다.

 

정리

스마트폰의 자동완성(autocomplete) 기능은 어떻게 동작하는걸까?

전체 단어 사전에 접근했을 때,

  1. 정렬되지 않은 배열에서 찾는다면 O(N)이 걸리고, (N이 전체 단어 개수를 뜻하기 때문에 매우 느린 연산이다.)
  2. 해시 테이블도 O(1)으로 찾을 수 있기는 하지만 모든 단어를 통째로 해싱해야하기 때문에 메모리 효율이 낮다.
  3. 정렬된 배열로 찾으면 O(logN)만에 찾을 수 있지만,
  4. 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다. - 트라이(trie)

트라이(trie)는 자동 수정(autocorrect)이나 IP 주소, 전화번호를 처리하는 어플리케이션 등에도 쓰인다.

 

트라이

  • 트라이(trie)는 텍스트 기반 기능에 이상적이다.
  • 트라이(trie)의 단어는 추출(retrieval)이라는 단어에 유래한다.
    • 사실 트리라고 발음하는게 맞지만 트리(tree) 자료구조가 존재하므로 "트라이"로 발음하게 되었다.
    • 프리픽스 트리, 디지털 트리 라고도 부르지만 "트라이"라는 이름이 가장 유명하다.
  • 교재마다 트라이의 구현이 조금씩 다르기 때문에 명쾌하게 이해되지 않을 수 있다.
    • 이 책에서는 가장 간단하고 이해하기 쉬운 구현을 택했다.

트라이 노드

대부분의 트리처럼 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다.

하지만 트라이는 이진 트리가 아니다. 자식 노드 개수에 제한이 없다.

이 책의 구현에서는 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 key는 알파벳, value는 트라이의 다른 노드이다.

class TrieNode:

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

 

트라이 클래스

완벽하게 트라이를 생성하려면 루트 노드를 추적하는(관리하는) Trie 클래스도 별도로 필요하다.

class Trie:

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

 

단어 저장

트라이에서 가장 중요한 부분은 단어 저장이다.

예제에서 "ace", "bad", "cat"을 저장해보겠다.

각 단어의 각 문자를 트라이 노드로 바꿔 세 개의 단어를 저장한다.

맨 마지막 노드(해시 테이블)에는 단어의 끝을 표시하기 위해 key에 "*", value에 nil(또는 아무거나)을 넣는다.

단어 "act" 추가
간소화된 버전

별표(asterisk)의 필요성

"batter", "bat"을 저장하고 싶을 때, "batter"는 "bat"을 포함하게 된다.

이 때, 별표의 필요성이 나타난다.

이 그림에서 별표(*)의 value(=nil)는 생략했다.

첫 번째 "t"는 키가 둘인 노드를 가리킨다. (한 키는 값이 널인) "*"고 나머지 한 키는 값이 또 다른 노드를 가리키는 "t"다.

트라이 검색

검색은 가장 대표적인 트라이 연산으로서 트라이에 어떤 문자열이 있는지 알아내는 것이다.

검색의 목적은 크게 두 가지인데, 하나는 문자열이 완전한 단어인지 알아내는 것 또 하나는 문자열이 최소한 어떤 단어의 접두사인지(= 어떤 단어의 앞부분) 알아내는 것이다.

둘 다 비슷하지만 후자인 접두사를 찾는 검색을 구현할 예정이다. 접두사를 찾다 보면 완전한 단어도 자연스레 찾을 수 있다.

1. currentNode 라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
2. 검색 문자열의 각 문자를 순회한다.
3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
4. 자식이 없으면 검색 문자열이 트라이에 없다는 뜻이니 None을 반환한다.
5. currentNode에 현재 문자를 키로 하는 자식이 있으면 currentNode를 그 자식 노드로 업데이트 한다. 이어서 2단계로 돌아가 검색 문자열 내 각 문자를 계속 순회한다.
6. 검색 문자열을 끝까지 순회했으면 검색 문자열을 찾았다는 뜻이다.

 

접두사 검색 알고리즘

코드

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

루프를 끝까지 통과했으면 트라이에서 단어 전체를 찾은 것이다.

True가 아니라 현재 노드를 반환하는 이유는 이후에 설명 할 자동 완성 기능을 지원하기 위해서다.

트라이 검색의 효율성

해시 테이블 룩업에는 딱 O(1)이 걸린다.

위의 알고리즘에서 각 노드의 해시 테이블을 사용해 한 단계만에 적절한 자식 노드를 찾는다.

따라서 알고리즘은 검색 문자열 내 문자 수 만큼의 단계가 걸린다.

  • 검색하려는 단어가 "cat"일 때 3단계가 걸린다.
  • 이는 정렬된 배열에 이진 검색을 수행하는 것보다 훨씬 빠르다.
  • N이 사전 내 단어 수일 때 이진 검색은 O(logN)이다.

트라이 검색은 빅 오로 나타내기 약간 까다롭다. 단계 수가 검색 문자열의 길이에 따라 달라지기 때문에 상수가 아니며, 따라서 O(1)이라 말할 수 없다. 또한 N은 일반적으로 자료 구조 내 데이터 양을 말하는데 O(N)은 오해의 소지가 있다. N은 트라이 내 노드 수를 뜻하며 이 값은 검색 문자열 내 문자 수보다 훨씬 크다.

많은 교재에서 이 복잡도를 O(K)라 부른다. K는 검색 문자열 내 문자 수다.

 

검색 문자열마다 길이가 다르므로 O(K)는 상수는 아니지만, 대부분의 알고리즘이 N에 비례하여 알고리즘 성능이 측정 되는 반면에 (N이 커질수록 알고리즘 속도가 느려진다.) O(K) 알고리즘에서는 트라이가 엄청나게 커지더라도 검색 속도에 영향이 없기 때문에 상수 시간과 비슷하다.

알고리즘 속도에 영향을 미치는 요인은 사용 가능한 전체 데이터(N)가 아니라 입력 크기(K)뿐이다.

그래서 O(K) 알고리즘이 매우 효율적인 것이다.

트라이 삽입

트라이에 새 단어를 삽입하는 과정은 기존 단어를 검색하는 과정과 비슷하다.

1. currentNode 라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
2. 검색 문자열의 각 문자를 순회한다.
3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
(1 ~ 3번 단어 검색하는 과정과 동일)
4. 자식이 있으면 currentNode를 그 자식 노드로 업데이트 하고 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
5. currentNode에 현재 문자와 일치하는 자식 노드가 없으면 자식 노드를 생성하고 currentNode를 이 새 노드로 업데이트 한다. 이어서 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
6. 삽입할 단어의 마지막 문자까지 삽입했으면 마지막 노드에 "*" 자식을 추가해 단어가 끝났음을 알린다.

"can" 삽입 전
"can" 삽입 후

코드

앞선 search 메서드와 거의 비슷하다.

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

문자가 트라이에 없으면 추가하고, 문자의 맨 마지막에는 "*"을 추가한다.

검색처럼 삽입도 O(K) 시간이 걸린다.

 

자동 완성 개발

단어 수집

Trie 클래스에 추가 할 다음 메서드는 특정 노드에서 시작해 트라이 내 모든 단어를 수집하여 배열로 반환하는 메서드다.

실제로 사전 전체를 나열할 일은 아주 드물다. 하지만 이 메서드는 트라이의 어떤 노드든 인수로 받아 그 노드부터 시작되는 모든 단어를 나열할 수 있다.

 

def collectAllWords(self, node=None, word="", words=[]):
    # 메서드는 인수 세 개를 받는다.
    # 첫 번째 인수인 node는 그 자손들에게서 단어를 수집 할 노드이다.
    # 두 번째 인수인 word는 빈 문자열로 시작하고
    # 트라이를 이동하면서 문자가 추가된다.
    # 세 번째 인수인 words는 빈 배열로 시작하고 
    # 함수가 끝날 때는 트라이 내 모든 단어를 포함한다.
    
    # 현재 노드는 첫 번째 인자로 전달받은 node다.
    # 아무것도 받지 않았으면 루트 노드다.
    currentNode = node or self.root
    
    # 현재 노드의 모든 자식을 순회한다.
    for key, childNode in currentNode.children.items():
    	# 현재 key가 *이면 완전한 단어 끝에 도달했다는 뜻이므로
        # 이 단어를 words 배열에 추가한다.
        if key == "*":
            words.append(word)
        else: # 아직 단어 중간이면
            # 그 자식 노드에 대해 이 함수를 재귀적으로 호출한다.
            self.collectAllWords(childNode, word + key, words)
            
    return words

word와 words는 재귀 호출에 쓰이므로 처음에는 명시하지 않아도 된다.

재귀 연습 (walk-through)

그림으로 보는 동작

"c", "a" 탐색은 생략.

 

배열은 값을 추가해도 메모리에서 계속 같은 객체이므로 배열을 호출 스택 위아래로 전달할 수 있다. (해시 테이블도 가능)

반면 문자열을 수정하면 컴퓨터는 원래 문자열 객체를 실제로 수정하는 대신 새 문자열을 생성한다.

따라서 word를 "ca"에서 "can"으로 업데이트 해도 이전 호출에서는 원래 문자열인 "ca"에만 접근할 수 있다. (일부 언어는 다르게 동작할 수 있다.)

 

자동 완성 마무리

Trie 클래스에 넣을 수 있는 기본 autocomplete 메서드다. 앞서 작성한 메서드 조각을 합칠 수 있는 메서드다.

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

자동 완성 업그레이드

위의 메서드에서는 사전에서 접두사와 일치하는 단어 전부를 출력했는데 이보다는 인기있는 단어만 갯수를 제한하여 보여줄 수도 있다.

(잘 알려지지 않은 단어는 사용할 확률이 낮으므로 의미있는 데이터가 아니기 때문에 제외하는 것이 더 낫다.)

위의 메서드에서 약간만 바꾸면 구현이 가능하다. 단어의 끝에 의미 없이 넣어놨던 "*" 대신 자주 쓰이는 인기있는 단어에 점수를 매겨서 넣고, 그 순서(우선순위)에 따라 제한된 단어 몇 개만 보여줄 수 있다. 

 

마무리

지금까지 이진 탐색 트리, 힙, 트라이라는 세 종류의 트리를 살펴봤다.

여러 종류의 트리가 어떻게 서로 다른 문제를 해결하는지 알아봤다.

각 트리마다 특정 상황에 유용하게 쓰일 만한 고유한 성질과 동작을 지닌다.

이 밖에 AVL 트리, 레드-블랙 트리, 2-3-4 트리 등 많은 종류의 트리가 있다.

 

트리에서 배운 내용들은 그래프를 이해하는 바탕이 된다.

아주 다양한 상황에서 유용하게 쓰이고 또 유명한 그래프를 다음 챕터에서 배울 예정이다.