참고
트라이(Trie) - Prefix Tree
NOTE
Trie ⇒ 기존에 사용되던 자료구조로는 문자열 검색에 있어 여러 제약사항과 성능이슈가 있어서 나온 트리 자료구조!
{"rebro", "replay", "hi" , "high", "algo"} 의 트라이구조 (일단 참고만 하자)
트라이(Trie) 자료구조가 없었을 시절
NOTE
•
배열(Array)
◦
배열이나 리스트에 문자열을 저장하고, 검색할 때마다 전체를 순회하면서 검색
◦
이 방법은 효율성이 떨어져 큰 데이터셋에서는 사용하기 어려움
•
해시 테이블
◦
‘apple’이라는 단어의 뜻을 알고싶다면, 빠르게 검색이 가능하다.
◦
하지만 해시 충돌, 접두사 검색, 부분 문자열 검색, 사전 순 정렬에 제약이 있다.
◦
접두사 / 부분 문자열 검색
▪
‘ppl’처럼 단어의 중간 부분만 알고 있을 떄, 자동완성하기 어려움
◦
문자열을 알파벳 순서대로 정렬
▪
해시 테이블은 키를 사전 순으로 정렬하지 않기 때문에, 별도의 작업이 필요함.
트라이(Trie) 특징
NOTE
Tree의 일종으로 “문자열의 키”를 효율적으로 저장하고 검색하기 위한 자료구조다!
•
접두사 검색(Prefix Search)
◦
사용자가 입력한 접두사를 가진 모든 가능한 단어나 문구를 찾는다.
◦
사용자가 “app”을 입력하면 “app”, “apple”, “application”등이 결과로 나올 수 있다.
•
자동완성(Auto-Completion)
◦
자동 완성 기능은 접두사 검색을 기반으로 동작한다.
◦
접두사 검색과 같이 사용자가 입력한 부분 문자열(접두사)를 기반으로 가능한 모든 완전한 문자열을 찾아서 제안합니다.
◦
단순 접두사 검색보다 더 다양한 변수(사용 빈도, 사용자 행동 등)을 고려하여 결과를 제공한다.
•
사전 검색(Dictionary Lookup)
◦
사용자가 완전한 단어나 문구를 입력하여 해당 단어가 사전에 있는지 확인하고, 있다면 관련 정보를 제공한다.
◦
ex) “apple”을 검색한다 ⇒ “apple”이라는 단어의 뜻, 발음, 동의어, 등이 제공될 수 있다.
◦
사전 검색은 완전한 단어에 대한 정확한 정보를 제공하려고 한다. 여기에는 단어의 정의, 발음 등이 포함될 수 있다.
◦
완전한 단어 검색이라면 해시 테이블이 더 일반적이나, 사전 순 정렬이 필요하면 Trie가 더 효율적
트라이(Trie) 로 자동완성 기능 만들기
NOTE
a를 입력한 경우
a의 subtree를 모두 검색한다.
abo를 입력한 경우
a → b → o의 subtree를 모두 검색한다.
트라이(Trie) 장/단점
NOTE
•
장점
◦
문자열을 빠르게 찾을 수 있다.
◦
문자열을 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색 모두 O(n)만에 가능하다.
•
단점
◦
필요한 메모리의 크기가 너무 크다.
◦
문자열이 모두 영소문자로 이루어진다 해도, 자식 노드를 가리키는 26개의 노드가 필요하다.
◦
최악의 경우에는 총메모리가 O(node 크기 * node 배열 개수 * 총 node 개수)가 된다.
◦
이 단점을 해결하기 위해 보통 map이나 vector를 사용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하지만 최적화가 힘들다.
트라이(Trie) 구현
NOTE
public class Node {
public Map<Character, Node> children;
public boolean isEndOfWord;
public Node() {
this.children = new HashMap<>();
this.isEndOfWord = false;
}
}
Java
복사
children → 다음으로 올 수 있는 문자
isEndOfWord → 끝 문자인가?
public class Trie {
private Node root;
public Trie(Node root) {
this.root = root;
}
// 삽입
public void insert(String word) {
Node current = this.root;
for (char c : word.toCharArray()) {
if(! current.children.containsKey(c)) current.children.put(c, new Node());
current = current.children.get(c);
}
current.isEndOfWord = true;
}
// 탐색
public Node search(String word){
return search(this.root, word);
}
private Node search(Node node, String word) {
// 빈 문자열이 왔다면, 마지막 문자인지 확인
if(word.isEmpty()) return node.isEndOfWord ? node : null;
// 다음 검색할 문자 탐색
char c = word.charAt(0);
Node child = node.children.get(c);
if(child == null) return null;
return search(child, word.substring(1));
}
// 자동완성
public List<String> autoComplete(String prefix) {
Node currentNode = this.root;
// prefix만큼 node탐색
for (char c : prefix.toCharArray()) {
Node child = currentNode.children.get(c);
if(child == null) return new ArrayList<>();
currentNode = child;
}
return searchStartWith(currentNode, new StringBuilder(prefix));
}
private List<String> searchStartWith(Node node, StringBuilder prefix) {
List<String> result = new ArrayList<>();
// 마지막 문자면 추가
if(node.isEndOfWord) result.add(prefix.toString());
// prefix가 탐사한 노드의 subtree 모두탐색 (DFS 방식)
for (Map.Entry<Character, Node> entry : node.children.entrySet()) {
prefix.append(entry.getKey());
result.addAll(searchStartWith(entry.getValue(), prefix));
prefix.deleteCharAt(prefix.length() - 1);
}
return result;
}
}
Java
복사
구현 코드
Trie trie = new Trie(new Node());
// Test insert and search
trie.insert("apple");
trie.insert("app");
trie.insert("banana");
System.out.println(trie.search("apple") != null); // true
System.out.println(trie.search("app") != null); // true
System.out.println(trie.search("appl") == null); // true
System.out.println(trie.search("ban") == null); // true
// Test autoComplete
List<String> completions;
completions = trie.autoComplete("app");
System.out.println(completions); // [apple, app]
completions = trie.autoComplete("ban");
System.out.println(completions); // [banana]
completions = trie.autoComplete("z");
System.out.println(completions); // []
Java
복사
테스트 코드
트라이(Trie) 성능 분석
NOTE
•
시간복잡도
◦
접두어를 탐색하는 부분 ⇒
▪
p는 접두어길이
◦
재귀적 탐색 부분(searchStartWith) ⇒
▪
n은 트라이의 부분노드, 최악의경우 전체탐색
•
공간 복잡도
◦
재귀의 깊이는 트라이의 최대 높이나 깊이에 비례한다.
◦
트라이의 깊이 (문자열의 최대 길이)를 d라고 할 때 ⇒