트라이
트라이란?
트라이(Trie)는 문자열의 집합을 표현하는 트리 자료구조입니다.
원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리(STL set, Map) 등에서는 원소를 찾는데 O(logN)의 시간이 걸리게 됩니다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 됩니다.
따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것입니다.
이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)입니다.
쉽게말해, 문자열을 빠르게 탐색할 수 있는 자료구조입니다.
구현 방식
예시를 통해서 살펴봅시다.
다음 그림은 문자열 집합 {”rebro”, “replay”, “hi”, “high”, “algo”}를 트라이로 구현한 것입니다.
이처럼, 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리입니다.
한 문자열에서 다음에 나오는 문자가 현재 문자의 자식 노드가 되고, 빨간색으로 나타낸 노드는 문자열의 끝을 의미합니다.
그렇다면 트라이 구조가 문자열을 탐색하기 위한 자료구조이므로, 문자열을 탐색하기 위해서는 다음 글자에 해당하는 노드가 연결되어 있는지, 연결되어 있다면 그 노드를 타고 계속해서 따라가야 할 것입니다.
문자열의 끝에 도달했을 때 즉, 빨간색 노드가 나왓을 때 루트에서부터 내려가는 경로에서 만나는 글자들을 모으면 찾고자 하는 문자열을 확인할 수 있습니다.
예를 들어서, “rebro”를 찾는다고 해봅시다.
r → e → b→ r→ o 까지 진행한다면 빨간색 노드를 발견할 수 있습니다. 이때 접두사들을 차례 차례 이어 붙이면 r → re → reb → rebr → rebro로 찾고자 하는 문자열을 확인할 수 있습니다.
동작 과정
- 문자열을 루트에서부터 시작하여 한 글자씩 탐색합니다.
- 현재 글자에 해당하는 노드가 존재하면 그 노드로 이동합니다.
- 더 이상 탐색할 수 없을 때까지 1, 2 과정을 반복합니다.
- 탐색이 끝나면 마지막 노드에서부터 루트까지 거슬러 올라가면서 해당 노드에서 끝나는 문자열들을 찾아냅니다.
트라이의 경우 두 가지 방식으로 구현할 수 있습니다.
- Array를 이용하여 구현하기
- Map Inteface를 이용하여 구현하기
1번의 경우 빠르게 저장할 수 있고 탐색이 가능하다는 장점을 가지고 있지만, 필요한 메모리의 크기가 너무 크다는 것이 단점이다.
2번의 경우 메모리를 동적으로 할당함으로써 필요한 노드만 메모리를 할 수 있는 장점이 있지만, 메모리 제한이 빡빡한 경우 최적화 작업이 꽤나 까다로운 것이 단점이다.
특징
- K-진 트리 구조를 통해 문자열을 저장하는 방식
- 맨 앞의 접두어(prefix)부터 시작하여 단어 전체를 찾아과는 과정이므로 접두사 트리(Prefix-Tree)라고도 한다. (영어 사전 방식)
- 트라이(Trie)는 문자열 저장을 위한 공간을 많이 쓰지만 탐색에 매우 효율적이라는 특성을 갖는다.
장단점
장점
- 문자열을 빠르게 찾을 수 있습니다.
- 문자열을 집합에 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 시간 복잡도가 낮습니다.
단점
- 필요한 메모리의 크기가 너무 큽니다.
코드
코드의 양이 꽤 많기 때문에 주석으로 설명을 달아놨으니깐 천천히 보고 이해하길 바랍니다.
Array
import java.util.NoSuchElementException;
// 문자열이 전부 영어 소문자로만 이루어졌다고 판단하고 진행
// Root Node는 아무런 문자열(접두사)도 포함하지 않고 모든 문자열의 접두사들을 자식 배열로 갖고 있어야 한다.
public class Trie_Using_Array {
public static void main(String[] args) {
Trie_Using_Array trie = new Trie_Using_Array();
trie.insert("bar");
trie.insert("bag");
trie.insert("bark");
trie.insert("main");
trie.insert("battle");
trie.insert("show");
trie.insert("dog");
trie.insert("do");
trie.insert("door");
System.out.println(trie.find("bag") ? "Yes!, bag is exist!" : "No, bag does not exist..");
System.out.println(trie.find("baga") ? "Yes!, baga is exist!" : "No, baga does not exist..");
System.out.println("Trie 내 문자열 전체 출력");
trie.printTrie();
System.out.println("LPM 찾기!! ");
String input = "showroom";
System.out.println("[" + input + "] LPM - " + trie.getLPM(input));
input = "battlefield";
System.out.println("[" + input + "] LPM - " + trie.getLPM(input));
input = "d";
System.out.println("[" + input + "] LPM - " + trie.getLPM(input));
System.out.println("Trie 내 일부 문자 삭제 테스트");
try {
trie.delete("do");
trie.delete("doll");
} catch (Exception e) {
System.out.println(e.getMessage());
}
System.out.println("Trie 내 문자열 전체 출력");
trie.printTrie();
}
/////////////////////////////////////////////////////////////////////////
Node root;
static final int ALPHABET_SIZE = 26; // a-z는 26개
// Root Node의 내용 정의
public Trie_Using_Array() {
this.root = new Node();
this.root.val = ' ';
}
private static class Node {
Node[] child = new Node[ALPHABET_SIZE]; // 뒤로 연결되는 문자열 a-z 소문자를 index화하여 저장하는 배역(26개)
boolean isTerminal = false; // 현재 노드가 문자 완성이 되는 노드인지 여부
int childNum = 0; // 현재 노드에 연결된 문자열의 개수
char val; // 현재 노드의 값
}
private int charToInt(char c) {
return c - 'a'; // 여기서는 소문자만 있으므로 'a'를 빼면 된다.
}
// 전체 문자열을 쪼개서 각 Node에 저장하는 메소드
public void insert(String str) {
int length = str.length();
Node current = this.root; // 루트 부터 시작해서 내려감
for(int i = 0; i < length; i++) {
char c = str.charAt(i); // 전체 문자열의 일부 단어 추출
int num = this.charToInt(c); // 추출한 단어를 숫자로 변환
if(current.child[num] == null) { // 기존에 null이면 연결 문자열로 처음 추가되는 것
current.child[num] = new Node();
current.child[num].val = c;
current.childNum++;
}
current = current.child[num]; // 자식 노드로 넘어감
}
current.isTerminal = true;
}
// 사용자가 호출 시 사용, 간편히 문자열만 전달
// 반복문으로 노드를 순황하여 문자열 존재 여부 판단
public boolean find(String str) {
int length = str.length();
Node current = this.root; // 현재 노드 설정
for(int i = 0; i < length; i++) {
char c = str.charAt(i);
int num = this.charToInt(c);
// 문자열의 일부를 추출했는데 null이라면 false를 반환
if(current.child[num] == null) {
return false;
}
current = current.child[num];
}
return current != null && current.isTerminal; // 문자열의 마지막이라면 true
}
// 모든 저장된 단어의 내역을 알기 쉽게 프린트해주는 메소드
private char intToChar(int i) {
return (char)(i + (int)'a');
}
public void printTrie() { // 사용자가 간편히 호출만 하면 되는 메소드
this.printTrie(this.root, 0, new StringBuilder());
}
// 내부에서 재귀적으로 순환하여 노드에 저장된 값들 추출해주는 프린트
private void printTrie(Node node, int idx, StringBuilder sb) {
Node current = node;
Node[] child = current.child;
StringBuilder builder = new StringBuilder(sb);
// 루트 노드에는 저장된 것이 없으므로 그 외의 경우에만 append
if(!current.equals(this.root)) {
builder.append(intToChar(idx));
}
// 완성 노드라면 프린팅하면 된다.
if(current.isTerminal) {
System.out.println(builder);
}
// 완성 노드가 아니라면 isTermianl이 false일 것이고, 그렇다는 것은 자식 노드가 존재한다는 의미
// 완선된 노드들을 순환하기 위해 반복문 사용
for(int i = 0; i < ALPHABET_SIZE; i++) {
// null 이라면 거기에는 저장된 것이 없다는 의미이므로 건너 뜀
if(current.child[i] == null) {
continue;
}
printTrie(child[i], i, builder); // 재귀적으로 순환
}
}
/* 삭제하기
* 1) 삭제할 문자가 다른 문자의 접두사인 경우 -> isTerminal을 false 변경
* - Do는 Door의 접두사가 된다. 따라서, Do를 삭제한다면 D, o에서 o에 isTerminal만 false로 변경한다.
* - 단순히 삭제하면 Door또한 사라지게 된다.
* 2) 삭제할 문자가 Unique하여 다른 문자와 연관이 없는 경우 -> 관련 모든 노드 삭제
* 3) 삭제할 문자의 일부가 전체 삭제 문자의 접두사인 경우 -> 다른 문자에 영향가지 않는 곳까지만 삭제
* - Door를 삭제하려고 한다면 Do가 있으니, 전체 삭제를 할 수 없고 Door에서 뒤의 o,r만 삭제해야 한다.
* */
/*
* 재귀 함수를 사용하는 이유
* 1. 같은 매커니즘이 반복해서 사용될 때
* 1.1 같은 매커니즘이 여러 군데서 활용 -> 함수를 사용
* 1.2 같은 매커니즘이 하나의 결과를 도출하기 위해서 값이 바뀌면서 반복해서 사용될 때 -> 재귀 함수 사용
*
* 2. 재귀함수의 특징을 활용할 때
* 2.1 재귀 함수는 return으로 함수를 실행하지 않으면 쭉 진행해 나갔다가 반대로 돌아오면서 다시 실행하는 성격을 가지고 있다.
* 이를 태면, DFS를 보면 쭉 밑으로 진행해 나갔다가 다시 위로 올라갔다가 내려갔다가 하는 것을 반복한다.
* 2.2 재귀 함수 안에서 값을 수정한 것은 빠져 나올 때 이전 값으로 돌아오지만, 주소 값을 넘겨주는 매개 변수인 경우는 다르다.
* 매개 변수를 넘겨 줄 때 값 조정
* 1) 빠져 나오는 과정에서 값을 수정하고 싶다면 재귀 함수 안에서 수정해주면 된다.
* 2) 빠져 나오는 과정에서 값을 수정하지 않겠다면 함수의 매개 변수로 넘겨줄 때 연산(단항 연산 X)을 해준다.
*/
// 사용자가 호출시 사용하는 메소드
public void delete(String str) {
delete(this.root, str, 0);
}
// 내부적으로 재귀를 통해 삭제를 진행하는 메소드
private void delete(Node current, String str, int idx) {
int leng = str.length();
// 자식이 없는데 String의 length의 끝까지 오지 않았다면 예외 발생
// 끝까지 갔는데 해당 노드가 terminal가 아니라면 해당 단어를 저장하지 않은 것이므로 예외 발생
if(current == null || (current.childNum == 0 && idx != leng) || (idx == leng && !current.isTerminal)) {
throw new NoSuchElementException("Value " + str + " does not exist in Trie!");
}
// 문자열의 마지막에 다다른 경우
if(idx == leng) {
current.isTerminal = false;
// 자식이 없는데 문자의 마지막이었다면 해당 문자만 저장된 것이므로 null 처리
if(current.childNum == 0) {
current = null;
}
} else {
char c = str.charAt(idx);
int num = charToInt(c);
// 삭제 후 돌아오는 부분
delete(current.child[num], str, idx + 1);
// child가 null처리 되었다면 자식 노드의 수가 하나 줄어든 것이므로 -- 처리
if(current.child[num] == null) current.childNum--;
// 현재 노드의 자식이 없고, 단어의 마지막도 아니라면 삭제해야 한다.
if(current.childNum == 0 && !current.isTerminal) {
current = null;
}
}
}
// LPM을 찾는 메소드
public String getLPM(String input) {
// 반환할 String 값을 지정
String ret = "";
int leng = input.length();
Node current = this.root;
int matchIdx = 0;
for(int i = 0; i < leng; i++) {
char c = input.charAt(i);
int num = charToInt(c);
// 자식이 null이 아니면 해당 자식 노드로 이동
if(current.child[num] != null) {
ret += c; // 해당 value를 반환 값에 추가
current = current.child[num]; // 자식 노드로 이동
// 해당 자식 노드가 단어의 끝이라면 Trie에 저장된 것임.
// i + 1을 matchIdx에 저장하여 subString에 활용할 것으로 준비
// 해당 자식 노드가 단어의 끝이라면 Trie에 저장된 것임.
// i + 1을 matchIdx에 저장하여 subString에 활용할 것으로 준비
if(current.isTerminal) {
matchIdx = i + 1;
}
} else {
break;
}
}
// 반목물을 다 돌았는데 현재 위치가 단어의 마지막이 아니라면
if (!current.isTerminal) {
// matchIdx로 subString을 해야한다.
return ret.substring(0, matchIdx);
// 반목문을 다돌았는데 마지막이라면 해당 단어가 LPM
} else {
return ret;
}
}
}
// 참고한 사이트
// 겐지충 프로그래머 :: 자료구조 - 트라이(https://hongjw1938.tistory.com/24)Map Interface
import java.util.HashMap;
import java.util.Map;
import java.util.NoSuchElementException;
public class Trie_Using_Map {
public static void main(String[] args) {
// Trie 자료 구조 생성
Trie trie = new Trie();
// Trie에 문자열 저장
trie.insert("kakao");
trie.insert("busy");
trie.insert("card");
trie.insert("cap");
// Trie에 저장 된 문자열 확인
System.out.println(trie.search("bus")); // false
System.out.println(trie.search("busy")); // true
System.out.println(trie.search("kakao")); // true
System.out.println(trie.search("cap")); // true
}
/////////////////////////////////////////////////////////////////////////
static class Node {
// 자식 노드
Map<Character, Node> childNode = new HashMap<>();
// 단어의 끝인지 아닌지 체크
boolean isTerminal;
}
static class Trie {
// Trie 자료 구조를 생성할 때 rootNode는 기본적으로 생성
Node rootNode = new Node();
// Trie에 문자열 저장
void insert(String str) {
// Trie 자료 구조는 항상 rootNode부터 시작
Node node = this.rootNode;
// 문자열의 각 단어마다 가져와서 자식 노드 중에 있는지 체크
// 없으면 자식 노드 새로 생성
for(int i = 0; i < str.length(); i++) {
node = node.childNode.computeIfAbsent(str.charAt(i), key -> new Node());
}
// 저장 할 문자열의 마지막 단어에 매핑되는 노드에 단어의 끝임을 명시
node.isTerminal = true;
}
// Trie에서 문자열 검색
boolean search(String str) {
// Trie 자료 구조는 항상 rootNode 부터 시작
Node node = this.rootNode;
// 문자열의 각 단어마다 노드가 존재하는지 체크
for(int i = 0; i < str.length(); i++) {
// 문자열의 각 단어에 매핑된 노드가 존재하면 가져오고 아니면 null
node = node.childNode.getOrDefault(str.charAt(i), null);
if(node == null) {
// node가 null이면 현재 Trie에 해당 문자열은 없음
return false;
}
}
// 문자열의 마지막 단어까지 매핑된 노듣가 존재한다고해서 무조건 문자열이 존재하는게 아님
// busy를 Trie에 저장했으면, bus의 마지막 s단어에 매핑 된 노드는 존재하지만 Trie에 저장된 건 아니다
// 그러므로 현재 노드가 단어의 끝인지 아닌지 체크하는 변수로 리턴
return node.isTerminal;
}
void delete(String str, Node current, int idx) {
int leng = str.length();
if((current.childNode.isEmpty() && idx != leng) || (idx == leng && !current.isTerminal)) {
throw new NoSuchElementException("Value" + str + " does not exists!");
}
if(idx == leng) {
current.isTerminal = false;
if(current.childNode.isEmpty())
current = null;
} else {
char c = str.charAt(idx);
delete(str, current.childNode.get(c), idx + 1);
if(current.childNode.isEmpty() && !current.isTerminal)
current = null;
}
}
}
}
// 참고한 사이트
// [Java] Map Interface의 유용한 메서드를 알아보자!(https://codingnojam.tistory.com/39)
// [Algorithm] Trie를 Java로 구현해보자!(https://codingnojam.tistory.com/40)Reference
개발정리블로그