트라이(Trie) 문자열 탐색 트리 개념 정리 (Java)

트라이(Trie)

트라이(Trie)란 문자열의 집합을 표현하는 트리 자료 구조로,  문자열 특화 자료 구조의 대표적인 예이다.

 

트라이(Trie)를 왜 사용할까?

정수나 실수형 변수는 그 크기가 항상 정해져 있기 때문에 비교에 상수 시간O(1)이 걸린다고 가정해도 되는 반면, 문자열 변수는 비교하는 데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그렇기 때문에 정수나 실수 키에 대해서는 훌륭하게 동작하는 탐색 자료 구조들도 문자열을 키로 사용할 때는 시간이 너무 오래 걸릴 수 있다.

 

원소 간의 비교를 상수 시간에 할 수 있을 때는 N개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교를 할 수 있지만 문자열의 비교에는 그 길이에 비례하는 시간이 걸리므로 문자열 최대 길이 M을 곱한 O(MlgN)이 최종 시간 복잡도가 된다.

 

이와 같은 문제를 해결하기 위해 고안된 문자열 특화 자료구조의 대표적인 예로 바로 트라이(Trie)가 있다. 트라이는 트리 자료구조로 집합 내에서 원하는 원소를 찾는 작업을 O(M)시간만에 할 수 있다.

 

 

트라이(Trie) 동작 과정

다음 예시는 집합 S = {"LOO", "LE", "LEE", "SI", "SIE", "SIX"}를 저장하는 트라이의 예를 보여준다.

 

트라이 예시

 

그림에서 볼 수 있듯이 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리이다. 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다. 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결된다.

 

트라이(Trie) 노드 구조

• 트라이의 루트 노드는 항상 길이 0인 문자열에 대응되며, 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1씩 늘어난다.
• 그림에서 파란색으로 표시된 노드들은 종료 노드로 이 노드들은 해당 위치에 대응되는 문자열이 트라이가 표현되는 집합에 포함되어 있음을 나타낸다.
• 트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 만나는 글자들을 모으면 해당 노드에 대응되는 접두사를 얻을 수 있다는 것이다.
• 따라서 각 노드에는 대응되는 문자열을 저장할 필요가 없다. 트라이의 한 노드를 표현하는 객체는 (1)자손 노드들을 가리키는 포인터 목록과, (2)이 노드가 종료 노드인지를 나타내는 boolean 값 변수로 구성된다.

 

이 때 자손 노드들을 가리키는 포인터 목록은 동적 배열이 아니라 입력에 등장 할 수 있는 모든 문자에 각각 대응되는 원소를 갖는 고정 길이 배열로 구현된다. 예를 들어 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 26개짜리 포인터 배열을 가지고 있으며, 이 배열의 0번 원소는 대응되는 문자열의 맨 뒤에 글자 A를 붙일 경우 얻을 수 있는 문자열 노드의 포인터를 나타낼 것이다.

 

→ 이와 같은 구조는 메모리를 엄청나게 낭비하지만 다음 노드를 찾는 과정에서 어떤 탐색도 필요하지 않다는 장점을 가져다 준다. 

 

 

트라이(Trie) 구현하기

트라이(Trie)를 공부하는 책의 언어가 C++이기 때문에 포인터라고 표현했지만 Java에서는 주소값을 참조할 수 있는 참조형 변수를 사용해주면 된다. 

 

Java로 구현하기

트라이(Trie) 기본 구조

트라이(Trie)의 내부 구조는 2개의 상태로 이뤄져있다. 정적할당을 하는 배열을 사용해도 되고 Map을 사용해도 된다. Map을 사용할 경우 <Key, Value>를 <해당 노드에 입력될 문자열 , 다음 트라이 노드>의 값을 넣어준다.

1. 자손 노드(childNode)를 가리키는 자료구조
2. 이 노드가 종료 노드인지를 나타내는 boolean값

class TrieNode{
	Map<Character, TrieNode> childNode = new HashMap<>();
	boolean terminal;
}

 

insert() 메서드

추가로 TrieNode에 데이터를 넣어줄 insert() 메서드는 필수적으로 구현해줘야 한다. 문자열(str)을 입력받으면 루트 노드를 시작으로 자식 노드로 내려가면서 각 문자열에 해당하는 문자들을 순차적으로 저장해준다.

public void insert(String word) {
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c = word.charAt(i);

		// tmp childNode에 c없으면 추가 
		trieNode.childNode.putIfAbsent(c, new TrieNode());
		trieNode = trieNode.childNode.get(c);

		// 마지막 문자 terminal 
		if(i== word.length()-1) {
			trieNode.terminal = true;
			return;
		}
	}
}

 

contains() 메서드

문자열 탐색은 접두사가 일치하는 경우를 탐색해야 하는 경우도 있고 완전히 일치하는 문자열을 탐색하는 경우도 있으므로 주어진 상황에 맞춰 능동적으로 구현해줘야 한다. 

 

백준 14425번 문자열 집합을 예로, 특정 문자열(word)이 트라이(Trie)에 존재하는 문자열에 대한 여부를 조사해주는 메서드는 다음과 같은 형태로 구현할 수 있다.

1. word라는 문자열을 입력받아 Trie에 존재하는 문자열인지 탐색한다.
2. 모든 문자열을 탐색하기 전에 노드가 끊어지면 해당 문자열은 존재하지 않으므로 false를 반환한다.
3. 모든 문자열을 탐색했다면 word의 마지막 문자열이 terminal 노드이면 true 아니면 false를 반환한다.

public boolean contains(String word) { 
	TrieNode trieNode = this;
	for(int i=0; i<word.length(); i++) {
		char c= word.charAt(i);
		TrieNode node = trieNode.childNode.get(c);

		if(node == null) {
			return false; // 다음 문자가 없으면 false 
		}
		trieNode = node;
	}

	// 해당 단어로 종료하는 문자가 있는 경우 false
	return trieNode.terminal; 
}

 

트라이(Trie) 노드 최종 형태

class TrieNode{
	Map<Character, TrieNode> childNode = new HashMap<>();
	boolean terminal;

	TrieNode(){
		/* no-op */ 
	}

	public void insert(String word) {
		TrieNode trieNode = this;
		for(int i=0; i<word.length(); i++) {
			char c = word.charAt(i);

			// tmp childNode에 c없으면 추가 
			trieNode.childNode.putIfAbsent(c, new TrieNode());
			trieNode = trieNode.childNode.get(c);

			// 마지막 문자 terminal 
			if(i== word.length()-1) {
				trieNode.terminal = true;
				return;
			}
		}
	}

	public boolean contains(String word) { 
		TrieNode trieNode = this;
		for(int i=0; i<word.length(); i++) {
			char c= word.charAt(i);
			TrieNode node = trieNode.childNode.get(c);

			if(node == null) {
				return false; // 다음 문자가 없으면 false 
			}
			trieNode = node;
		}
		// 해당 단어로 종료하는 문자가 있는 경우 false
		return trieNode.terminal; 
	}
}

 

Go로 구현하기

go로 구현한 코드 보러가기

 

트라이(Trie) 기본 문제 풀어보기

백준 5052번 전화번호 목록

백준 14425번 문자열 집합

 

 

트라이(Trie) 응용

트라이의 최대 문제는 필요로 하는 공간이 너무 크다는 것이다. 알파벳 대문자만 저장한다고 해도 트라이의 각 노드는 26개의 포인터를 저장해야 한다. 포인터의 크기가 8바이트인 64비트 아키텍쳐라면 노드 하나를 표현하는데 200여 바이트를 사용해야 한다. 입력되는 문자열들이 접두사를 전혀 공유하지 않는 최악의 경우 트라이에는 입력되는 문자열들의 전체 길이만큼의 노드가 필요한데, 문자열 길이의 합이 1백만이라고 하면 무려 200MB의 메모리를 사용해야 한다.

 

트라이에서 메모리를 절약하기 위한 트리플 어레이트리(triple-array trie)와 같은 여러 기법들이 개발되어 있지만 이들은 코테나 알고리즘 대회에 사용하기에는 너무 복잡하고 작성하는데 오래 시간이 걸리는 경우가 대부분이다. 때문에 대회에서 트라이를 쓸 수 있는 경우는 다루는 문자열의 개수가 그렇게 많지 않은 경우로 제한된다. 

 

참고) 실제로 카카오 코테의 효율성 문제에서 트라이(Trie)를 사용하는 문제가 나왔는데 전체 문자열의 길이를 10,000으로 제한을 뒀다.

 

 

또한 이더리움 블록 state를 저장하기 위해 Trie 자료구조를 응용한 Merkle Patricia Trie을 사용한다.

 

---

※ 참고

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2