트라이

(Trie에서 넘어옴)

1 개요

우리가 여러 개의 문자열을 가지고 있을 때, 어떤 문자열이 그 문자열 중 하나인지 알아내는 방법은 뭐가 있을까?

단순하게 일일이 비교해보면 된다. 하지만 컴퓨터는 이러한 방법이 매우 비효율적이다. 예를 들어, 최대 길이가 [math]m[/math]인 문자열 [math]n[/math]개의 집합에서 마찬가지로 최대 길이가 [math]m[/math]인 임의의 문자열이 그 문자열들의 집합에 포함되는지를 일일이 확인하면 사전처리는 필요 없지만, 최악의 경우 [math]O(nm)[/math]의 비교 횟수가 필요하다.

이 문자열을 정렬시킨 뒤, 이진 탐색이라는 강력한 알고리즘을 사용하면 [math]O(m \log n)[/math]로 단축시킬 수 있지만, 정렬 과정 자체에 [math]O(n m \log n)[/math][1]의 시간이 걸리므로 사양이 안 좋은 컴퓨터라면 이것도 비효율적이다. 하지만 위의 시간 복잡도를 압도하는 알고리즘이 존재한다. 프레드킨이 이름 붙인 "Trie"[2]라는 자료구조가 지금부터 설명할 가장 효율적인 문자열 검색법이다.

2 구조

기본적으로 K진 트리[3]의 구조를 띠고 있다. 영어사전을 생각해보면 간단하다. 우리가 'cancel'이라는 단어를 찾으려면 우선 앞 글자 'c'의 색인을 찾을 것이다. 그 다음 'a', 'n', ... 순서대로 찾아가는 것이다. 이것을 논리적으로 컴퓨터에 적용한 구조가 바로 트라이 구조이다.[4] 이를테면 'tea'라는 문자열이 입력되었다면 순서대로 머릿글자 't'가 등록되고 그 다음 'e'가, 그 다음 'a'가 등록된다. 마지막에 문자열을 모두 찾았다면 그 위치에 "이곳에 문자열이 있소!" 하고 표시하면 되는 것이다. 그리고 그런 시작 문자열을 접두어(prefix)라고 부른다.

trie_example.jpg
[5]

이러한 트라이 구조는 찾고자 하는 문자열을 공간을 많이 사용하는 대신, 그 문자열의 길이의 속도만큼 초고속 탐색이 가능하다.

일반적으로는 동적 할당을 통해 생성하지만 Array를 통하여 구축하는 방법을 설명한다.
우선 트라이에 등록하고자 하는 문자열 p 가 있다고 하자. (편의상 이 문자열은 알파벳 소문자로만 구성되어 있다고 가정하자.)
그리고 trie의 루트는 언제나 0이다. 그리고 이 0 부터 시작하여 p[i]-'a' 에 대해 다음 노드로 이동 가능한지 여부를 판단한다.
이동 할 수 있다면 이동하고 이동 할 수 없다면 triesize에 1을 추가하여 새로운 노드를 만든 뒤 그곳을 가르키게 한다.
동적 할당을 활용할 수 있는 전문가라면, 할당 해준 뒤, 그 것을 가르키게 하면 된다.
이하 반복.

triesize는 코드 시작부에서 0으로 초기화 한다.

node = 0
for i in 0..p.length
if trie[node][p[i]-'a'] == 0
trie[node][p[i]-'a'] = ++triesize
node = triesize
else
node = trie[node][p[i]='a'];
check[node] = true; // 해당 노드에 문자열이 존재함을 알림

2.1 시간 복잡도

문자열 집합의 개수와 상관 없이 찾고자 하는 문자열의 길이가 시간 복잡도가 된다. 즉, 문자열의 길이가 [math]m[/math]이라면 시간 복잡도는 [math]O(m)[/math]. 그 이유는 간단하다. 트라이를 구현할 때, [math]n[/math][math]m[/math]이 상대적으로 작다면[6] 배열을 사용할 텐데, 현재 노드의 위치를 i, j번째 문자라고 한다면 trie[i][j]의 위치를 조회하는 건 [math]O(1)[/math]에 수행이 가능하다. 여기서 [math]m[/math]번을 수행하니 [math]O(m)[/math]의 시간이 걸리는 것이다. 하지만 [math]n[/math][math]m[/math]이 큰 경우에는, 메모리 확보를 위해 시간을 희생해서라도 n이 진짜 무식하게 큰 게 아닌 이상 의미없다. Map이나 이진 트리 등으로 트라이를 만들기도 한다. 이 경우엔 [math]O(m \log n)[/math]의 시간이 소모된다.

3 관련 알고리즘

  1. 이것은 사전처리이므로 한 번만 수행하면 된다. 후술할 트라이의 경우는 사전처리를 [math]O(nm)[/math] 안에 할 수 있다. 단, Map이나 이진 트리를 사용하는 경우 제외.
  2. 발음은 트리(tree)가 아니다. 트라이(try)다.
  3. 여기서의 K는 문자의 개수를 의미한다. 예를 들어 63개의 문자를 사용한다면 63진 트리가 되는 것이다.
  4. The Art Of Computer Programming 3 561P 숫자별 검색
  5. 사진 출처
  6. 여기서 [math]n[/math][math]m[/math]이 작다는 것은 노드의 개수로 인한 메모리 사용량이 일반 가정집에서 안정적으로 확보할 수 있는 256MB를 넘지 않는 걸로 한다.
  7. 오늘날 검색엔진의 주가 되는 알고리즘이다.