Trie

Trie는 단어 집합을 나타내는 문제를 해결하기 위해 만들어진 구조이다.

retrieval이란 단어에서 유래되었고 Tree 구조와 구별하기 위해서 '트라이'로 발음된다.

Trie는 기본적으론 트리 데이터 구조이지만 생성 및 사용 방법 측면에서 따라야 할 몇 가지 규칙이 있다.

 

Trie는 노드가 알파벳 문자를 저장하는 Tree와 같은 자료구조이다. 특정 방식으로 노드를 구조화하면 Tree의 분기 경로르 따라 이동하여 구조에서 단어와 문자열을 검색할 수 있다. 각 Trie는 가능한 알파벳 값에 대해 하나씩 다른 노드에 대한 링크가 있는 빈 루트 노드가 있다. Trie의 모양과 구조는 항상 연결된 노드의 집합이며 빈 루트 노드에 다시 연결된다. 주목해야 할 점은 Trie의 자식 노드 수가 가능한 총 값 수에 완전히 의존한다는 것이다. 예를 들어 알파벳을 표현하면 자식 노드의 총수는 가능한 총 문자 수와 직접 연결된다. 알파벳은 26자이므로 자식 노드의 총 개수는 26개이다. 그러나 만약 우리가 한글을 이용해서 단어를 자정하려고 한다면 자음의 수인 19개가 자식 노드의 총 개수이다. Trie의 크기는 Trie가 나타낼 수 있는 모든 가능한 값의 크기와 직접적인 상관관계가 있다. 

 

그렇다면 앞서 루트 노드가 비어있다고 말했는데 그럼 루트 노드에 단어들이 포함되지 않는 것이다. 그렇다면 어디에 있을까? 루트 노드의 자식 참조에 있다. 빈 루트 노드가 있는 Trie가 있다. 영어를 나타내는 Trie가 생성되면 단일 루트 노드로 구성되고 이 노드의 값은 일반적으로 빈 문자열 ""로 설정된다. 루트 노드는 26개의 참조를 포함하는 배열을 가지며, 모든 참조는 null을 가리킬 것이다. Trie가 커짐에 따라 해당 포인터가 다른 노드에 대한 참조로 채워지기 시작한다. 이를 이용하면 배열의 인덱스를 이용하여 노드에 대한 특정 참조를 찾을 수 있다. 예를 들어 26개의 슬롯이 존재하면 0을 통해 인덱스 배열을 보유하고 알파벳이 순서대로 있기 때문에 문자를 포함할 노드에 대한 참조가 여기 있다는 것을 알고 있다.

 

이제 실질적인 동작에 대해 알아보자. 예를 들어 pecked라는 단어를 목록에 추가하려면 어떻게 해야할까? 

1. 먼저 pecked가 Trie안에 있는지 확인해야한다.

2. 다음으로, 이 단어가 있어야하는 지점을 탐색했는데 단어가 아직 존재하지 않는 경우 단어가 있어야 하는 노드의 참조에  값을 삽입한다. 

단어가 있는지 확인하고 올바른 위치에 단어를 삽입하는 방법은 뭘까? 예를 들어 pie를 삽입한다면 첫 글자 p에 대한 포인터를 찾는다. 그리고 i,e도 똑같이 해준다.

 

해당 구조는 해쉬 테이블을 상기시킨다. 두 개의 공통점과 차이점이 있다.

Trie와 Hash table은 둘 다 후드 아래에서 배열을 사용하여 서로를 연상시키지만 해시 테이블은 링크드 리스트와 결합된 배열을 사용하는 반면 Trie는 포인터/참조와 결합된 배열을 상용한다. 또 해시 테이블엔 해시 함수가 필요하지만 Trie 구조에는 모든 키가 순서대로 표시될 수 있어 해시 함수가 필요하지 않고 문자열 값에 대한 몯느 분기 경로가 해당 키에 고유하여 교유한 검색이 가능하다. 그러나 해시 테이블과 달리 트라이의 단점은 null 포인터로 많은 메모리와 공간을 차지한다. 우리는 큰 Trie가 어떻게 크기가 커지기 시작하는지 상상할 수 있으며, 추가된 각 노드와 함께 26개의 null 포인터를 포함하는 전체 배열도 초기화 되어야 한다. 그리고 엄청 긴 word가 있으면 이것의 빈 참조는 절대 채워지지 않을 것이다. Honorificabilitudinitatibus라는 키가 있다고 생각하면 이것은 아마도 하위 분기가 추가 되지 않을 것이다.

 

Trie를 사용하면 몇 가지 큰 이점이 있다. 우선 Trie를 만드는 작업의 대부분은 초기에 발생한다. 노드를 처음 추가할 때 매번 배열에 메모리를 할당하는 무거운 작업을 수행해야 하기에 의미가 있다. 그러나 Trie가 커지면 노드와 해당 값 및 참조를 이미 초기화했을 가능성이 높아져 값을 추가할 때마다 더 적은 작업을 수행한다. Trie의 branch가 구축되었기 때문에 중간 노드를 추가하는 것이 훨씬 쉬워진다. Trie에 대한 pro column의 또 다른 사실은 단어의 문자를 추가할 때마다 노드 배열에서 26개의 가능한 인덱스만 봐야 한다는 것을 알고 있다는 것이다. 왜냐하면 영어엔 26개의 가능한 문자만 있기 때문이다. 그렇기에 이 숫자는 절대 변경되지 않는 상수 값이다.

 

시간 복잡도를 보면 Trie를 생성하는 걸리는 시간은 최악의 경우 Trie에서 가장 긴 키의 길이인 m과 트라이에 있는 키의 총 수인 n의 조합이므로 O(mn)이다.  검색, 삽입 및 삭제하는 시간 복잡도는 검색, 삽입 또는 삭제되는 단어 a의 길이와 총 단어 수 n에 따라 달라지므로 이러한 작업의 런타임은 O(an)이다. 

 

그렇다면 Trie는 어디에 사용이 될까? 사실 Trie는 독점적으로 거의 사용되지 않는다. 일반적으로 다른 구조와 조합하거나 알고리즘의 맥락에서 사용된다. 그러나 Trie의 형식과 기능에 대한 가장 좋은 예는 구글과 같은 검색 엔진에서 사용되는 것과 같은 자동 완성 기능이다. 내가 치는 단어의 하위 집합을 검색하는 방법을 상상하면 된다. 이진 검색 트리와 유사하게 분기를 탐색할 때마다 필요하지 않은 노드는 가지치기한다. 검색 엔진은 인기도에 따라 특정 용어를 반환하고 Trie 구조에서 특정 용어와 관련된 가중치를 결정하기 위한 몇 가지 추가 논리가 있을 수 있어 더 복접할 것이다. 그리고 Trie는 알고리즘을 일치 시키고 맞춤법 검사기와 같은 것을 구현하는 데에도 사용되며 기수 정렬 버전을 구현하는 데에도 사용할 수 있다. 

 

참조

- https://medium.com/basecs/trying-to-understand-tries-3ec6bede0014

Trying to Understand Tries