트라이(Trie) 자료구조
- 문자열 검색을 위한, 트라이(Trie) 자료구조 기본 스터디
문자열을 저장하는 자료구조에서, 가장 효율적인 문자열 검색 알고리즘은 무엇일까? 가장 단순한 방법은 하나하나 찾아서 비교할 수 있지만 매우 비효율적인 방법이다. 문자열 검색에 좋은 알고리즘이 바로 "Trie"(트라이) 알고리즘인데, 이번 글에서는 트라이에 대해서 간략하게 공부하고, 트라이를 직접 구현하여 문자열 검색 엔진을 구현해본다.
1. 트라이(Trie) 개념 정리
2. 오픈소스 라이브러리
3. 실무 구현 사례가 있는가?
1. 트라이(Trie) 개념 정리
1.1. 트리(Tree)
트리(Tree)는 노드(Node)와 에지(Edge)로 구성되는 계층 관계를 나타내는 자료구조이다.
노드
엣지
루트 : 가장 상위의 노드
리프 : 가장 마지막 노드
트리에는 많은 종류가 있는데, 일반적으로 바이너리 트리 등이 있다. 이번 글에서 다루는 트라이도 트리의 한 종류이다.
1.2 트라이(Trie)
트라이(Trie)는 보통 Prefix Tree, digital search tree, retrieval tree라고도 부른다. 트라이는 retrieval tree에서 나온 단어이다. 트라이는 문자열을 Key로 사용하는 동적인 Set 또는 연관 배열을 저장하는 트리의 확장된 자료구조인데, 좀 쉽게 설명하면 영어 사전을 생각해보면 된다. "springboot"이라는 단어를 검색하기 위해서는 제일 먼저 "s"를 찾고, 그다음에 "p", "r"... 의 순서로 찾으면 된다. 이 개념을 적용한 것이 트라이인데 문자열을 빠르게 검색할 수 있다. 개념에 대한 정리는 위키피디아를 참고하였다.
https://en.wikipedia.org/wiki/Trie
샘플 예시
springboot, springcloud, springmvc, sports 의 문자열을 저장하는 트라이 자료구조는 아래와 같다.
1.3 트라이(Trie) in Java
트라이 자료구조를 직접 구현해보자.
https://github.com/sieunkr/data-structures/tree/master/java-trie
해당 소스는 아래 링크를 참고하였다. Baeldung 를 참고하였다.
http://www.baeldung.com/trie-java
1.4 Radix 트라이(트리)
"Radix 트라이"는 "트라이"에서 메모리 효율성을 좋게 만든 자료구조이다. Compact Prefix Tree라는 용어로 사용하기도 한다. 그냥 트라이와 Radix트라이를 비교하면 아래와 같다.
자세한 정보는 위키피디아를 참고하자.
https://en.wikipedia.org/wiki/Radix_tree
참고로!
해당 글에서는 Radix트라이와 Radix 트리를 따로 구분하지는 않았지만, Radix 트라이와 Radix 트리는 구조적인 차이점이 있다.
Radix 트리 : 모든 노드에 데이터가 포함된다. 트리의 높이만큼 비교한다.
Radix 트라이 : 리프 노드에만 데이터가 포함된다. Radix 트리보다는 검색 성능이 더 빠르지만, Radix트리보다는 상대적으로 메모리가 더 필요하다.
이런 차이가 있는데, 필자는 아직 정확히 이해하지는 못하였다. 일부 문서에서는 Radix트리와 Radix 트라이를 동일한 자료구조로 혼용해서 사용하기도 한다. 위키피디아에서도 Radix 트라이(Trie)로 검색하면 Radix 트리(Tree)로 리다이렉트 된다.
그래서, 해당 글에서는 Radix트리와 Radix트라이의 차이점에 대해서 자세히 다루지는 않는다. 혹시, Radix 트리와 Radix 트라이에 대해서 명확하게 개념을 정리할 수 있는 개발자가 있다면, 해당 글에 피드백을 남겨주길 바란다.
1.5 Suffix 트리
생략
1.6 시간 복잡도
생략
정말 좋은 트라이 자료구조이지만, 실서비스에 사용하기 위해서는 해결해야 하는 이슈가 있다.
Lock 없이 동시에 검색 조회
조회 기능 차단 없이 노드를 동적으로 추가
동시성을 지원하는 트라이 자료구조를 직접 구현해도 되지만, 짧은 프로젝트 일정에서 모든 기능을 구현하기에는 빡씨다.
2. 오픈소스 라이브러리 활용
업계에 사용 가능한 "동시성을 지원 트라이 자료구조 라이브러리"가 많지 않은데 이 글에서는 "concurrent-trees"라는 오픈소스를 정리한다. 실제로 업무에서도 사용 중이다.
https://github.com/npgall/concurrent-trees/blob/master/documentation/ReleaseNotes.md
주요 인터페이스와 구현체는 아래와 같다.
RadixTree
ReversedRadixTree
InvertedRadixTree
SuffixTree
모든 코드는 아래와 같이 디펜 던 시를 추가하였다.
build.gradle
dependencies {
compile('com.googlecode.concurrent-trees:concurrent-trees:2.6.1')
}
2.1 RadixTree
가장 기본이 되는 인터페이스이고, 구현체는 ConcurrentRadixTree이다.
Exact 매칭
Key Starts With
테스트 데이터 입력
RadixTree <Integer> tree = new ConcurrentRadixTree<Integer>(new DefaultCharArrayNodeFactory());
tree.put("springboot", 1);
tree.put("springcloud", 2);
tree.put("springmvc", 3);
tree.put("sports", 77);
springboot, springcloud, springmvc, sports라는 데이터를 Insert 하였다. 참고로 아래 출력은 PrettyPrinter를 사용하였다.
Exact 매칭
exact 매칭, 즉 모든 단어가 정확히 일치하는 경우를 검색하기 위해서는, getValueForExactKey 메서드를 사용하면 된다.
System.out.println("springboot (exact match): " + tree.getValueForExactKey("springboot"));
System.out.println("springcloud (exact match): " + tree.getValueForExactKey("springcloud"));
System.out.println("springmvc (exact match): " + tree.getValueForExactKey("springmvc"));
System.out.println("sports (exact match): " + tree.getValueForExactKey("sports"));
Key Starts With
prefix 매칭, 즉 시작하는 단어가 일치하는 경우 검색은, getKeyValuePairsForKeysStartingWith 메서드를 사용해보자. 아래 코드는 spring으로 시작하는 단어를 검색하는 소스이다
StreamSupport.stream(tree.getKeyValuePairsForKeysStartingWith("spring").spliterator(), false)
.forEach(System.out::println);
결과
2.2 ReversedRadixTree
구현체는 ConcurrentReversedRadixTree 이다.
Exact 매칭
Key Ends With
테스트 데이터 입력
ReversedRadixTree는 일반 RadixTree 와는 다르게, 문자가 거꾸로 입력된다
Exact 매칭
생략
Key Ends With
getKeyValuePairsForKeysEndingWith 메서드를 사용해보자
StreamSupport.stream(tree.getKeyValuePairsForKeysEndingWith("boot").spliterator(), false)
.forEach(System.out::println);
결과
2.3 InvertedRadixTree
아래 구문에서 springcloud와 springboot를 찾고 싶다면 어떻게 하면 될까??
"springcloud builds on springboot by providing a bunch of libraries that enhance the behaviour of an application when added to the classpath."
이럴 때 사용할 수 있는 기능이 InvertedRadixTree이고 구현체는 ConcurrentInvertedRadixTree이다.
Exact 매칭
Key Starts With
Find Keywords In External Documents
2.1의 RadixTree와 유사하지만, Scanning for Keywords in External Documents 기능이 추가된 것이다.
getKeyValuePairsForKeysContainedIn 메서드를 사용해보면 아래와 같다.
StreamSupport.stream(tree.getKeyValuePairsForKeysContainedIn("springcloud builds on springboot by providing a bunch of libraries that enhance the behaviour of an application when added to the classpath.").spliterator(), false)
.forEach(System.out::println);
결과
자세한 스펙은 아래 링크를 참고하자.
2.4 SuffixTree
만약 저장된 키 중에서, 특정 문자를 포함하고 있는 키를 검색하고 싶다면 어떻게 할까? 예를 들어서 springboot, springcloud, sports 등의 문자열이 저장되어 있는데, ring라는 문자열이 포함된 키를 찾고 싶다면?? 이때 사용할 수 있는 기능이 바로 SuffixTree이다. 참고로 필자는 SuffxTree 가 문자열의 끝을 검색하는 자료구조로 알고 있었는데... 잘못 알고 있었던 것 같다. 자세한 개념은 아래 링크를 참고하자.
https://en.wikipedia.org/wiki/Suffix_tree
근데 해당 인터페이스가 메모리를 매우 많이 잡아먹을 것 같다. 저장된 자료구조는 아래와 같다.
ring를 포함하고 있는 키를 찾아보자
StreamSupport.stream(tree.getKeyValuePairsForKeysContaining("ring").spliterator(), false)
.forEach(System.out::println);
결과
2.5 정리
간단하게 concurrent-trees를 테스트해보았다. 실무에서도 사용하기 적합한 것으로 생각되지만, 해당 라이브러리 마지막 업데이트가 작년 6월이다. 아쉽지만, 해당 라이브러리도 오래 쓰지는 못할 수도 있다.
3. 트라이(Trie) 적용 사례
이 글은, 트라이를 메모리에 저장해서 사용하는 방법에 대한 글이다. 혹시, 트라이(Trie) 자료구조를 저장할 수 있는 대중적인 오픈소스 미들웨어가 있는지 궁금하다. 지금까지 찾아봤을 때는 없는 것 같지만, 혹시라도 트라이를 오픈소스 스토리지에 저장해서 사용한 사례가 있다면 피드백을 주길 바란다. 또한 Elastic Search으로 대체가 가능한지도 궁금하다.
혹시 트라이를 실무에서 사용한 좋은 사례가 있다면, 피드백 부탁드립니다.
