[자료구조 및 알고리즘] 트라이(Trie)

트라이(trie)

트라이(trie)란?

• 문자열의 집합을 표현하는 트리(Tree)임
• 정보 검색(Retrieval)에서 이름을 따옴
• 정보 검색에 사용된 자료구조로 1960년, E.Fredkin에 의해 소개됨
• 일반적인 자료구조인 Tree와 구분하기 위해 [trai]로 발음함
• 같은 접두사를 가진 문자열들은 노드를 공유해서 저장
• 리프 노드까지의 경로가 곧 단어임
• 단어는 리프 노드 수만큼 존재

트라이의 성질

• 단어 S를 삽입/탐색/삭제할 때 $O(|S|)$
  • 이때 |S|는 문자열 S의 길이를 의미함
• 문자열을 그냥 배열에 저장하는 것 보다 메모리를 최대 "4 x 글자의 종류"배 만큼 더 사용
• 이론적으로 트라이는 매우 빠른 시간복잡도
• 그러나, 실제로 트라이가 해시, 이진 검색 트리에 비해 훨씬 느림
  • 일반적인 상황에서는 해시나 이진 검색 트리를 사용하는게 좋으나 트라이의 성질을 사용해야 하는 문제가 여럿 존재

직관적인 예시

문자열 집합이 다음과 같다고 해보자

"cat", "car", "dog"

이 문자열 집합을 트라이에 저장하면 아래와 같다

• "cat"을 삽입하면 c -> a -> t 노드 생성
• "car"은 c -> a까지는 이미 존재하므로 그 노드를 재사용하고, r만 추가
• "dog"는 완전히 새로운 경로 d -> o -> g로 생성

트라이를 사용하는 이유

1. 빠른 검색 : 문자열 길이가 L일 때 검색은 O(L)
2. 접두사 검색 가능 : "ca"로 시작하는 모든 단어 찾기 가능
3. 중복된 접두사 저장을 줄여 메모리 절약 : 같은 접두사는 공유

구현

operations : 삽입(insert), 삭제(erase), 탐색(find)

const int ROOT = 1;				// 루트 노드는 항상 1번
int unused = 2;					// 노드 번호를 카운팅하는 숫자
const int MX = 10000 * 500 + 5; // 최대 등장 가능한 문자의 수
bool chk[MX};					// 리프 노드인지 체크
int nxt[MX][26];				// 트리

for(int i=0; i<MX; i++)
	fill(nxt[i], nxt[i]+26, -1); // 초반에 트리는 -1로 초기화

삽입(insert)

void insert(string& s){
	int cur = ROOT;
    for(char c : s) {
    	int idx = c - 'a';
    	if(nxt[cur][idx] == -1)
        	nxt[cur][idx] = unused++;
        cur = nxt[cur][idx];
    }
    chk[cur] = true;
}

탐색(find)

bool find(string& s){
	int cur = ROOT;
    for(char c : s) {
    	int idx = c - 'a';
    	if(nxt[cur][idx] == -1)
        	return false;
        cur = nxt[cur][idx];
    }
    return chk[cur];
}

삭제(erase)

void erase(string& s){
	int cur = ROOT;
    for(char c : s) {
    	int idx = c - 'a';
    	if(nxt[cur][idx] == -1)
        	return;
        cur = nxt[cur][idx];
    }
    chk[cur] = false;
}

---

접미어 트라이(suffix trie)

• 문자열의 모든 접미어를 트라이로 표현한 것

문자열에 대한 접미어 트라이가 있다면 다음을 쉽게 찾을 수 있다.

---

1. 부분 문자열 검사 (Substring Check)

아이디어:

1. 문자열 S의 모든 접미어를 트라이에 삽입
2. 검사할 문자열 P가 트라이에 존재하면, 이는 S의 부분 문자열임

예시:

문자열 S = "abac"의 접미어:

abac, bac, ac, c

트라이에 이 접미어들을 넣고 "bac"와 "aca"가 있는지 검사해보자.

단순히 한 문자씩 루트에서 대응되는 간선을 따라가면 된다

• "bac" -> (O)
• "aca" -> (X)

---

2. 두 접미어의 최장 공통 접두어 (LCP) 찾기

"abac"와 "ac"의 최장 공통 접두어를 찾아보자

아이디어:

1. 두 접미어의 끝 글자에 대응하는 노드를 선택한다
2. 그리고 가장 가까운 공통 조상을 찾는다
3. 루트에서 공통 조상까지의 경로가 최장 공통 접두어가 된다

---

3. 사전적 순서로 정렬된 k번째 접미어 찾기

트라이의 DFS를 이용하면 정렬 없이 사전순 순회 가능

아이디어

1. 문자열의 모든 접미어를 트라이에 삽입
2. 트라이를 DFS(사전순)으로 탐색하면서 접미어를 하나씩 꺼냄
3. K번째에 도달하면 반환