Trie 데이터 구조: 방치된 보석

프로그래머로서의 삶의 첫 날부터 우리는 모두 데이터 구조를 다루어 왔습니다. 배열, 연결 목록, 트리, 집합, 스택 및 대기열은 일상적인 동반자이며 숙련된 프로그래머는 언제, 왜 사용해야 하는지 알고 있습니다. 이 기사에서 우리는 종종 무시되는 데이터 구조인 trie 가 단어 게임과 같은 특정 기능이 있는 애플리케이션 도메인에서 실제로 어떻게 빛나는지 볼 것입니다.

트라이 예제로 단어 게임

우선 간단한 단어 퍼즐을 생각해 보겠습니다. 4x4 글자판에서 모든 유효한 단어를 찾고 인접한 글자를 가로, 세로 또는 대각선으로 연결합니다. 예를 들어, 다음 보드에서 'W', 'A', 'I', 'T'라는 글자가 연결되어 "WAIT"라는 단어를 형성하는 것을 볼 수 있습니다.

모든 유효한 단어를 찾는 순진한 솔루션은 왼쪽 상단 모서리에서 시작하여 깊이 우선을 더 긴 시퀀스로 이동하고 첫 번째 행의 두 번째 문자부터 다시 시작하는 식으로 보드를 탐색하는 것입니다. 4x4 보드에는 수직, 수평 및 대각선 이동이 가능한 12029640개의 시퀀스가 ​​있으며 길이는 1자에서 16자입니다.

이제 우리의 목표는 이 유효한 단어 검사기, 즉 우리의 어휘를 구현하기 위한 최상의 데이터 구조를 찾는 것입니다. 명심해야 할 몇 가지 사항:

• 논리적인 관점에서 각 단어의 단일 사본만 있으면 됩니다. 즉, 어휘는 집합입니다.
• 주어진 단어에 대해 다음 질문에 답해야 합니다.
  • 현재 문자 시퀀스가 ​​유효한 단어로 구성되어 있습니까?
  • 이 시퀀스로 시작하는 더 긴 단어가 있습니까? 그렇지 않은 경우 깊이 우선 탐색을 포기할 수 있습니다. 더 깊이 들어가면 유효한 단어가 생성되지 않기 때문입니다.

두 번째 요점을 설명하기 위해 다음 보드를 고려하십시오. 사전에 "ASF"로 시작하는 단어가 없기 때문에 후속 동작을 탐색하는 것은 의미가 없습니다.

가능한 한 빨리 이러한 질문에 답할 수 있는 데이터 구조를 원합니다. ~O(1) 액세스 시간(시퀀스 확인용)이 이상적입니다!

다음과 같이 Vocabulary 인터페이스를 정의할 수 있습니다(GitHub 저장소는 여기 참조).

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

데이터 구조 대 대안 시도

contains() 메서드를 구현하려면 요소를 효율적으로 찾을 수 있도록 지원하는 데이터 구조가 필요하지만 isPrefix() 메서드는 "다음으로 큰 요소"를 찾아야 합니다. 즉, 어떤 방식으로든 정렬된 어휘를 유지해야 합니다.

해시 기반 세트를 후보 목록에서 쉽게 제외할 수 있습니다. 이러한 구조는 contains() 에 대한 지속적인 검사를 제공하지만 isPrefix() 에서는 성능이 매우 좋지 않습니다. 최악의 경우 전체를 스캔해야 합니다. 세트.

정반대의 이유로 정렬된 연결 목록을 제외할 수도 있습니다. 정렬된 연결 목록은 검색된 단어나 접두어보다 크거나 같은 첫 번째 요소까지 목록을 스캔해야 하기 때문입니다.

두 가지 유효한 옵션은 정렬된 배열 지원 목록 또는 이진 트리를 사용하는 것입니다.
정렬된 배열 지원 목록에서 이진 검색을 사용하여 존재하는 경우 현재 시퀀스를 찾거나 O(log2(n)) 비용으로 다음으로 큰 요소를 찾을 수 있습니다. 여기서 n 은 사전의 단어 수입니다.

표준 java.util.ArrayList 및 java.util.Collections.binarySeach 를 사용하여 항상 이와 같은 순서를 유지하는 배열 지원 어휘를 구현할 수 있습니다.

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

이진 트리를 사용하기로 결정했다면 구현이 훨씬 더 짧고 더 우아해질 수 있습니다(여기에도 코드 링크가 있습니다).

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

두 경우 모두 각 액세스 방법( contains() 및 isPrefix() )에 대해 O(log n) 성능을 기대할 수 있습니다. 공간 요구 사항에 관해서는 어레이 지원 구현과 트리 지원 구현 모두 O(n+M) 이 필요합니다. 여기서 n은 사전의 단어 수이고 M은 사전의 바이트 크기, 즉 길이의 합입니다. 사전의 문자열.

시도 응용 프로그램: 시도를 사용하는 시기와 이유

로그 성능과 선형 메모리는 나쁘지 않습니다. 그러나 더 나은 성능으로 이어질 수 있는 애플리케이션 도메인의 몇 가지 특성이 더 있습니다.

• 모든 단어가 소문자라고 안전하게 가정할 수 있습니다.
• 구두점, 하이픈, 악센트 등의 az 문자만 허용됩니다.
• 사전에는 복수형, 활용형 동사, 합성어(예: house –> housekeeper)와 같은 다양한 굴절 형태가 포함되어 있습니다. 따라서 많은 단어가 같은 어간을 공유합니다 .
• 단어의 길이는 제한되어 있습니다. 예를 들어, 4x4 보드에서 작업하는 경우 16자보다 긴 모든 단어는 버릴 수 있습니다.

여기서 trie("try"로 발음)가 나옵니다. 하지만 trie 는 정확히 무엇입니까? 시도는 책에서 발견되지만 표준 라이브러리에서는 거의 발견되지 않는 무시된 데이터 구조입니다.

동기 부여를 위해 먼저 Computer Science의 포스터 자식인 이진 트리를 살펴보겠습니다. 이제 우리가 이진 트리의 성능을 분석하고 연산 x 가 O(log(n)) 이라고 말할 때 우리는 지속적으로 로그 기반 2를 말하고 있는 것입니다. 하지만 이진 트리 대신 삼항 트리를 사용했다면 어떻게 될까요? 모든 노드에는 3개의 자식(또는 3개의 팬아웃)이 있습니다. 그런 다음, 우리는 log base 3에 대해 이야기할 것입니다. (그것은 일정한 요인에 의해서만 성능이 향상됩니다.) 본질적으로, 우리의 트리는 더 넓어지지만 더 짧아질 것이고, 우리가 완전히 내려갈 필요가 없기 때문에 더 적은 조회를 수행할 수 있습니다. 그래서 깊은.

한 단계 더 나아가 데이터 유형의 가능한 값 수와 동일한 팬아웃을 가진 트리가 있다면 어떻게 될까요?

이것이 시도의 동기입니다. 그리고 짐작하셨겠지만, 트리는 말하자면 트리입니다!

그러나 문자열을 정렬하는 데 사용하는 대부분의 이진 트리와 달리 전체 단어를 노드에 저장하는 트리의 각 노드는 단일 문자를 보유합니다. 알파벳의 길이와 동일한 최대 팬아웃이 있습니다. 우리의 경우 알파벳의 길이는 26입니다. 따라서 트리의 노드는 최대 팬아웃이 26입니다. 균형 이진 트리의 깊이는 log2(n) 이지만 트리의 최대 깊이는 단어의 최대 길이와 같습니다! (다시 말하지만 더 넓지만 더 짧습니다.)

트라이 내에서 동일한 어간(접두사)을 가진 단어는 어간에 해당하는 메모리 영역을 공유합니다.

차이점을 시각화하기 위해 다섯 단어로 구성된 작은 사전을 살펴보겠습니다. 그리스 문자가 포인터를 나타낸다고 가정하고 trie에서 빨간색 문자는 유효한 단어를 보유하는 노드를 나타냅니다 .

자바 트라이 구현

알다시피 트리에서 자식 요소에 대한 포인터는 일반적으로 왼쪽 및 오른쪽 변수로 구현됩니다. 왜냐하면 최대 팬아웃이 2로 고정되어 있기 때문입니다.

26글자의 알파벳을 인덱싱하는 시도에서 각 노드에는 26개의 가능한 자식이 있으므로 26개의 가능한 포인터가 있습니다. 따라서 각 노드는 26개의 하위 트리(포인터)의 배열을 특징으로 하며, 여기서 각 값은 null(해당 하위가 없는 경우)이거나 다른 노드일 수 있습니다.

그렇다면 트라이에서 단어를 찾는 방법은 무엇입니까? 다음은 String s 가 트리에 존재하는 경우 단어의 마지막 문자에 해당하는 노드를 식별하는 방법입니다.

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

LOWERCASE.getIndex(s.charAt(i)) 메서드는 단순히 알파벳에서 i번째 문자의 위치를 ​​반환합니다. 반환된 노드에서 부울 속성 node 는 노드가 단어의 마지막 문자, 즉 이전 예제에서 빨간색으로 표시된 문자에 해당함을 나타냅니다. 각 노드는 자식 수의 카운터를 유지하기 때문에 이 카운터가 양수이면 현재 문자열을 접두사로 갖는 사전에 더 긴 단어가 있습니다. 참고: 노드는 트리에서 해당 위치에 암시적이기 때문에 해당하는 문자에 대한 참조를 유지할 필요가 없습니다.

성능 분석

이러한 상황에서 trie 구조가 실제로 잘 작동하게 만드는 것은 단어 또는 접두어를 찾는 비용이 고정되어 있고 어휘 크기가 아니라 단어의 문자 수에만 의존한다는 것입니다.

우리의 특정 도메인에서는 최대 16자의 문자열을 가지고 있기 때문에 어휘에 있는 단어를 찾는 데 정확히 16단계가 필요합니다. 반면에 단어나 접두사가 trie에 없는 부정적인 대답은 얻을 수 있습니다. 최대 16단계에서도 가능합니다! 배열 기반 정렬 목록과 문자열 비교에 숨겨져 있는 트리 모두에 대한 실행 시간 복잡성을 계산할 때 이전에 문자열의 길이를 무시했다는 점을 고려하면 여기에서 무시하고 조회가 완료되었다고 안전하게 말할 수 있습니다. O(1) 시간에.

공간 요구 사항을 고려하면(그리고 사전의 M 바이트 크기로 표시했음을 기억), 두 문자열이 접두사를 공유하지 않는 경우 트라이에 최악의 경우 M 노드가 있을 수 있습니다. 그러나 사전에 높은 수준의 중복성이 있음을 관찰했기 때문에 수행해야 할 압축이 많이 있습니다. 예제 코드에 사용된 영어 사전은 935,017바이트이고 250,264개의 노드가 필요하며 압축률은 약 73%입니다.

그러나 이것에도 불구하고 압축된 시도는 일반적으로 트리나 배열보다 더 많은 메모리를 필요로 합니다. 이는 각 노드에 대해 최소 26 x sizeof(pointer) 바이트가 필요하고 개체 및 추가 속성에 대한 약간의 오버헤드가 필요하기 때문입니다. 64비트 시스템에서 각 노드에는 200바이트 이상이 필요하지만 문자열 문자에는 단일 바이트가 필요하거나 UTF 문자열을 고려하면 2바이트가 필요합니다.

시도 및 성능 테스트

그렇다면 성능은 어떨까요? 어휘 구현은 두 가지 다른 상황에서 테스트되었습니다. 20,000,000개의 임의 문자열을 확인하고 동일한 단어 목록에서 무작위로 생성된 15,000개의 보드에서 모든 단어를 찾는 것입니다.

4가지 데이터 구조가 분석되었습니다. 배열 기반 정렬 목록, 이진 트리, 위에서 설명한 트리, 문자 자체의 알파벳 인덱스에 해당하는 바이트 배열을 사용하는 트리(사소하고 쉽게 구현되는 성능 최적화). 다음은 ms 단위의 결과입니다.

보드를 풀기 위한 평균 이동 횟수는 2,188입니다. 각 이동에 대해 단어 조회 및 접두어 조회가 수행됩니다. 즉, 모든 보드를 확인하기 위해 32M 단어 조회 및 32M 접두어 조회가 수행되었습니다. 참고: 이러한 작업은 단일 단계로 수행할 수 있으며 설명의 명확성을 위해 분리된 상태로 유지했습니다. 그것들을 한 단계로 압축하면 보드를 푸는 데 걸리는 시간이 거의 절반으로 줄어들고 아마도 그 시도에 더 유리할 것입니다.

위에서 볼 수 있듯이 단어 조회는 문자열을 사용할 때에도 trie에서 더 잘 수행되며 알파벳 인덱스를 사용할 때 더 빠르며 후자는 표준 이진 트리보다 두 배 이상 빠릅니다. 빠른 trie-alphabet-index 솔루션은 목록과 트리보다 4배 이상 빠릅니다.

마무리

tri는 트리와 목록보다 훨씬 더 많은 메모리를 필요로 하는 매우 전문화된 데이터 구조입니다. 그러나 문자열의 첫 부분에 있는 제한된 알파벳 및 높은 중복성과 같은 특정 도메인 특성이 적용되는 경우 성능 최적화를 해결하는 데 매우 효과적일 수 있습니다.

참고문헌

시도와 알파벳에 대한 광범위한 설명은 Robert Sedgewick의 책 "Algorithms, 4th edition"의 5장에서 찾을 수 있습니다. Princeton의 컴패니언 웹 사이트에는 내 예제보다 더 광범위한 Alphabet 및 TrieST 구현을 위한 코드가 있습니다.

다양한 언어에 대한 트라이 및 구현에 대한 설명은 Wikipedia에서도 찾을 수 있으며 이 Boston University 트라이 리소스도 살펴볼 수 있습니다.