트라이(Trie)
위키백과에 트라이는 "검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조" 라고 정의 되어있다.
트라이는 실무에 매우 유용하게 쓰이는 자료구조로서, 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다. 트라이는 검색을 뜻하는 'retrieval' 의 중간 음절에서 용어를 따왔다. 트라이는 트리와 유사하지만 지금까지 우리가 주로 살펴본 이진 트리의 모습이 아닌 다진 트리(m-ary Tree)의 형태를 띤다.
트라이는 각각의 문자 단위로 색인을 구축한 것과 유사한데, 예를 들어 다음과 같은 trie에서 단어 apple을 찾는다고 가정해보자. 수백 개의 문자가 있다고 할 때 이 경우 트라이 탐색을 하면 단 다섯번 만에 apple 문자열의 존재 여부를 파악할 수 있다. 문자열의 길이 만큼만 탐색하면 되기 때문이다. NLP에서는 형태소 분석기에서 분석 패턴을 트라이로 만들어두고 자연어 문장에 대해 패턴을 찾아 처리하는 등으로 활용한다.
해당 그림은 apple. appera. appeal 등으로 트라이를 구성한 것이다. 여기서 만약 apple을 찾는다면, a-> p -> p 순으로 문자별 일치하는 노드를 찾아 내려가면 된다. apple이므로 그 다음은 l 노드를 찾아 내려가면 될 것이고, 만약 appera를 찾는다면 e 노드를 찾아 내려가면 된다. 이런 식으로 루트부터 a -> p -> p -> l -> e 까지 내려가면 단어 apple을 찾을 수 있다. 이처럼 트라이에서는 각 문자열의 길이 만큼만 탐색하면 원하는 결과를 찾을 수 있다.
트라이는 문자열을 위한 트리의 형태이기 때문에 사실상 문자 개수만큼 자식이 있어 그림과 같이 나타내보면 상당히 많은 자식 노드를 갖고 있는 트리임을 확인할 수 있다.
출처 : 파이썬 알고리즘 인터뷰 (책만github.com/onlybooks/algorithm-interview)