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

스마트폰 등에서 쓰이는 자동완성 기능("catn"을 치면 "catnip", "catnap" 등을 추천)은 어떻게 동작하는가?

단어들 모두를 배열에 저장했다면 O(N)으로 느릴 것이고, 해시 테이블은 단어를 통째로 해싱해서 키로 삼아야 하므로 사용할 수 없다. 정렬된 배열을 사용한다면 O(logN)로 빨라질 것이다.

특수한 트리 기반 자료 구조인 트라이를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.

17.1 트라이

트라이는 자동 완성같은 텍스트 기반 기능에 이상적인, 트리의 한 종류이다.

트라이는 추출을 뜻하는 retrieval(리트리벌)에서 왔으니 '트리'로 발음해야 옳지만, 트리라는 발음이 모든 트리 기반 자료 구조에 보편적으로 쓰이므로 혼동을 막고자 '트라이'로 발음한다.

17.1.1 트라이 노드

트라이도 다른 노드를 가리키는 노드들의 컬렉션이다. 하지만 트라이는 이진 트리가 아니어서 자식 노드 개수에 제한이 없다.

책에서는 텍스트 처리 애플리케이션을 구현한다. 이 구현에서는 각 트라이 노드마다 키는 알파벳이고 값은 트라이의 다른 노드로 하는 해시 테이블을 포함한다.

class TrieNode {
  constructor() {
    this.children = new Map();
  }
}

17.1.2 트라이 클래스

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

class Trie {
  constructor() {
    this.root = new TrieNode();
  }
}

이렇게 구현하면 빈 TrieNode가 루트가 된다.

17.2 단어 저장

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

"ace", "bad", "cat"을 저장한다고 할 때, 트라이는 각 단어의 각 문자를 각각의 트라이 노드로 바꿔 세 개의 단어를 저장한다.

루트 노드에서 시작해 키 "a"를 따라가면 값은 키 "c"를 포함하는 자식노드를 가리킨다. 키 "c"는 다시 키 "e"를 포함하는 노드를 가리킨다. 이 세 문자를 하나로 연결해 "ace"가 된다. "bad", "cat" 역시 같은 방식을 따른다. 각 단어의 마지막 문자 역시 자식 노드를 갖는데, 키를 *로 하고 값은 null로 하는 자식 노드이다. 이늘 단어의 끝을 나타낸다.

이 상태에서 "ace"와 마지막 글자만 다른 "act"를 추가한다고 하자. 기존 키 "a", "c"는 그대로 놔두고, "c"의 자식노드로 "t"를 키로 하는 자식 노드를 추가 한다.

17.2.1 별표(asterisk)의 필요성

"bat"와 "batter"를 저장하고 싶다고 하자. "bat"를 저장하고 나서 "t"는 자식노드에 키를 *로 하는 노드와, t로 하는 노드 두가지를 가지고 있다. 즉 "bat" 자체가 하나의 단어이자 더 긴 "batter"의 접두사이다.

*는 단어의 일부도 단어일수 있음을 나타내는 데 꼭 필요하다.

17.3 트라이 검색

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

검색의 목적은 두 가지이다.

1. 문자열이 완전한 단어인지 알아내는 것,
2. 문자열이 최소한 어떤 단어의 접두사인지(즉, 어떤 단어의 앞부분인지) 알아내는 것.

접두사 검색 알고리즘은 다음과 같은 단계를 수행한다.

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

17.3.1 코드 구현: 트라이 검색

search(word) {
  let currentNode = this.root;
  for (const char of word) {
    if (currentNode.children.get(char)) {
      currentNode = currentNode.children.get(char);
    } else {
      return null;
    }
  }
  return currentNode;
}

currentNode에 루트 노드를 할당하고, for 반복문으로 검색하려는 단어의 문자를 순회한다.

각 반복문 안에서 현재 노드에 현재 문자를 키로 하는 자식이 있는지 확인한다. 있으면 현재 노드를 그 자식 노드로 업데이트 한다. 없다면 찾고자 하는 단어가 트라이에 없는 것이므로 null을 반환한다.

반복문을 끝까지 통과했으면 트라이에서 단어 전체를 찾은 것이므로 currentNode를 반환한다.

17.4 트라이 검색의 효율성

트라이 검색의 장점은 효율성이다.

17.3의 알고리즘은 검색 문자열의 각 문자를 한 번에 하나씩 살펴본다. 그리고 각 노드의 해시 테이블을 사용해 한 단계만에 적절한 자식 노드를 찾는다. 해시 테이블 룩업은 O(1)이므로, 알고리즘은 검색하려는 문자열의 문자 수 만큼 단계가 걸린다.

N이 사전 내 단어 수일 때 이진 검색은 O(logN)이다. 하지만 트라이 검색으로 세 글자 단어를 찾는다면 3단계면 된다.

트라이 검색은 빅 오로 나타내기 까다롭다. 단어의 글자 수마다 변하니 상수가 아니고, 따라서 O(1)이라 할 수 없다. N은 일반적으로 자료 구조 내 데이터 양을 말하는데, 트라이에서 N은 트라이 내 노드 수이다. 이는 찾으려는 단어의 글자 수보다 훨씬 크니 O(N)이라고 할 수도 없다.

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

O(K)가 상수는 아니지만, 검색 단어가 같다면 데이터가 얼마나 커지든 검색 속도에 영향을 끼치지 않는다는 점에서 상수 시간과 비슷하다. 알고리즘 속도에 영향을 끼치는 요인은 전체 데이터의 양이 아니라 입력 크기다. 그래서 O(K)가 효율적이다.

17.5 트라이 삽입

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

17.5.1 코드 구현: 트라이 삽입

insert(word) {
  let currentNode = this.root;
  for (const char of word) {
    if (currentNode.children.has(char)) {
      currentNode = currentNode.children.get(char);
    } else {
      const newNode = new TrieNode();
      currentNode.children.set(char, newNode);
      currentNode = newNode;
    }
  }
  currentNode.children.set("*", null);
}

앞부분은 search 메서드와 동일하고, currentNode에 현재 문자와 일치하는 자식이 없을 때 달라진다. 이 때는 현재 문자를 키로 하고 새 TrieNode를 자식으로 하는 새 키-값 쌍을 currentNode의 해시 테이블에 추가한다. 이어서 currentNode를 새 자식 노드로 업데이트한다.

새 단어를 모두 삽입할 때까지 반복문을 돌리고 종료되면 마지막 노드의 해시 테이블에 값이 null인 키 "*"를 추가한다.

삽입 역시 O(K)가 걸린다.

17.6 자동 완성 개발

자동 완성 기능을 좀 더 쉽게 개발하기 위해 이 기능을 돕는 단순한 함수를 먼저 만든다.

17.6.1 단어 수집

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

collectAllWords(node = null, word = "", words = []) {
  // node: 그 자손들에게서 단어를 수집할 노드
  // word: 빈 문자열로 시작하고 트라이를 이동하면서 문자가 추가된다.
  // words: 빈 배열로 시작하고 함수가 끝날 때는 트라이 내 모든 단어를 포함한다.

  let currentNode = node || this.root;

  for (let [key, childNode] of currentNode.children.entries()) {
    if (key === "*") {
      words.push(word);
    } else {
      this.collectAllWords(childNode, word + key, words);
    }
  }
  return words;
}

메서드는 node, word, words라는 인자를 받는다. node는 트라이 내 어떤 노드에서 단어 수집을 시작할지 명시한다. 만일 이 노드를 넘기지 않으면 메서드는 루트 노드에서 시작해 전체 트라이 내의 모든 단어를 수집한다.

word와 words 인자는 메서드 재귀 호출에 쓰이므로 처음에 명시하지 않아도 된다.
words 인자의 기본값은 빈 배열이고, 트라이에서 완전한 단어를 찾을 때마다 그 문자열을 배열에 추가해 함수 마지막에 반환한다.
word 인자의 기본값은 빈 문자열이고, 트라이 사이를 옮겨 다니며 word에 문자를 추가한다. "*"가 나오면 완전한 단어라는 뜻이니 words 배열에 추가한다.

currentNode가 루트 노드라고 가정하고, for문으로 currentNode의 자식 해시 테이블에 있는 모든 키-값 쌍을 순회한다.
이때 key는 항상 문자 하나짜리 문자열이고, childNode는 또 다른 TrieNode 인스턴스다.

else 절에서 collectAllWords 메서드를 재귀 호출하며 첫 번째 인자로 childNode를 전달한다. 이러한 방식으로 트라이를 순회한다.
두 번째 인자로 word + key를 전달한다. 단어를 완성하기 위해 트라이의 각 노드를 옮겨 다니며 현재 word에 key를 계속 추가한다.
마지막 인자로 words 배열을 넘겨주며 완전한 단어를 수집해 목록을 생성한다.

기저 조건은 키가 "*"일 때, 즉 한 단어를 완성했을 때이다. 이 때의word를 words 배열에 추가한다.

함수 마지막에서 words 배열을 반환한다.

17.6.2 재귀 연습(walk-through)

트라이에 "can"과 "cat"이 들어있다고 하자. 단어를 수집하기 위해 collectAllWords를 호출한다.

1. 첫 번째 호출

• word: ""
• words: []
• 호출 스택:

루트 노드의 자식 키가 c 하나다. 현재 호출을 호출 스택에 쌓아두고, 자식 노드인 c에 대해 collectAllWords를 재귀 호출한다. 이 때 인자로 "" + c, 즉 "c"와 words를 함께 전달한다.

2. 두 번째 호출

• word: "c"
• words: []
• 호출 스택: collectAllWords(null, "", words)

자식 키가 a 하나다. 이 노드를 a를 자식으로 갖는 노드라는 뜻에서 a 노드라고 호칭한다.
현재 호출을 호출 스택에 쌓아두고, 자식 노드인 a에 대해 메서드를 재귀 호출한다. 이 때 인자로 "ca", words를 함께 전달한다.

3. 세 번째 호출

• word: "ca"
• words: []
• 호출 스택: collectAllWords(null, "", words) > collectAllWords(a node, "c", words)

a 노드 해시 테이블엔 자식 키가 n, t로 두 개이다. 이를 n/t 노드라고 호칭한다.
현재 호출을 호출 스택에 쌓아두고, n 노드에 먼저 재귀 호출한다. 이때 인자로 "can", words를 함께 전달한다.

4. 네 번째 호출

• word: "can"
• words: []
• 호출 스택: collectAllWords(null, "", words) > collectAllWords(a node, "c", words) > collectAllWords(n/t node, "ca", words)

현재 노드의 자식 키는 "*"로 기저 조건이다. word인 can을 words에 추가한다.

5. 다섯 번째 호출

• word: "ca"
• words: ["can"]
• 호출 스택: collectAllWords(null, "", words) > collectAllWords(a node, "c", words)

가장 최근 호출을 팝하여 돌아간다. word 인자에 해당하는 "ca"는 그대로지만 words에는 "can"이 포함되어 있다.

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

반면 문자열을 수정하면 문자열 객체를 수정하는 것이 아니라 새 문자열을 생성한다. 따라서 word를 수정해도 이전에 호출한 스택에는 호출할 당시의 word의 값만 접근할 수 있다.

6. 여섯 번째 호출

• word: "ca"
• words: ["can"]
• 호출 스택: collectAllWords(null, "", words) > collectAllWords(a node, "c", words)

현재 호출을 스택에 쌓아두고, 다음 자식 키인 t노드에 재귀 호출한다. 이때 인자로 "cat", words를 함께 전달한다.

7. 일곱 번째 호출

• word: "cat"
• words: ["can"]
• 호출 스택: collectAllWords(null, "", words) > collectAllWords(a node, "c", words) > collectAllWords(n/t node, "ca", words)

현재 노드의 자식 키는 "*"로 기저 조건이다. word인 "cat"을 words에 추가한다.

이후 호출 스택에서 각 호출을 팝하며 words 배열을 반환하고 실행을 완료함으로써 호출 스택을 해제할 수 있다.

17.7 자동 완성 마무리

autocomplete(prefix) {
  let currentNode = this.search(prefix);
  if(!currentNode) {
    return null;
  }
  return this.collectAllWords(currentNode, prefix);
}

search 메서드로 prefix가 트라이에 존재하는지 검색한다. search 메서드는 접두사가 트라이에 없으면 null을 반환한다. 있으면 접두사의 마지막 문자가 들어 있는 트라이 노드를 반환한다.

이 노드에 collectAllWords를 호출하면 입력받은 prefix에 붙어 하나의 단어가 되는 완전한 단어를 모두 찾아서 수집한다. 이 배열이 자동 완성 옵션이다.

17.8 값을 포함하는 트라이: 자동 완성 업그레이드

사용자가 입력할 만한 단어를 전부 표시하는 건 꼭 훌륭하지만은 않다. 100개의 단어가 해당한다고 모두 보여줄 필요는 없으니, 널리 쓰이는 단어만 추려서 보여주는 편이 낫다.

가장 많이 쓰이는 단어 위주로 옵션을 표시하려면 트라이에 단어 인기도 데이터를 함께 저장해야 한다.

각 단어의 완성을 나타내는 노드인 "*"의 값으로 null을 할당했는데, 이 값에 인기도 데이터를 저장하면 된다. 이후 트라이 내 단어를 수집할 때 점수를 함께 수집해 인기도 순으로 단어를 정렬하면 된다.

17.9 마무리

이진 탐색 트리, 힙, 트라이라는 세 종류의 트리를 살펴 봤다. 이 외에도 많은 종류의 트리가 있다.

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