트라이 자료구조 (Trie)

한 줄 정의: 문자열의 각 문자를 트리의 간선으로 나타내어, 공통 접두사를 공유하는 문자열들을 하나의 경로로 압축해 저장하는 트리 형태의 자료구조.

쉽게 풀면

트라이는 단어들을 저장할 때 같은 접두사를 가진 단어끼리 트리의 경로를 공유하도록 만든 구조다. 예를 들어 'cat'과 'car'은 'ca'까지 같은 경로를 타고 가다가 마지막 글자에서 갈라진다. 이 덕분에 어떤 문자열이 저장된 단어들 중 하나로 시작하는지, 또는 특정 접두사로 시작하는 단어가 몇 개나 있는지를 매우 빠르게 찾을 수 있어, 자동완성 기능이나 사전 검색에 널리 쓰인다.

왜 중요한가

대량의 문자열 집합에서 접두사 기반 검색을 빠르게 처리해야 하는 문제는 검색엔진, 자연어처리, 네트워크 라우팅 등 여러 분야에서 공통으로 등장하기 때문에, 트라이는 효율적인 문자열 인덱싱 구조로서 알고리즘 논문에서 자주 비교 대상으로 다뤄집니다. 특히 대규모 어휘사전이나 스트리밍 데이터를 다루는 시스템 논문에서 성능 개선의 근거로 인용되는 경우가 많습니다.

논문에서는 이렇게 쓰입니다

"자동완성 기능 구현을 위해 사용자 검색어를 트라이에 저장하여 접두사 검색을 O(m) 시간에 처리하였다(m은 검색어 길이)."

문자열 접두사 검색이나 사전 조회가 필요한 응용에서 자료구조 선택의 근거로 쓰인다.

"라우팅 테이블의 IP 주소 최장 접두사 매칭을 위해 이진 트라이를 활용하여 조회 성능을 개선하였다."

네트워크 시스템 분야에서 IP 주소 검색 속도를 높이기 위해 트라이를 활용한 예문이다.

"형태소 분석기의 사전 조회 단계에서 트라이 기반 인덱스를 사용하여 대규모 어휘집합에 대한 검색 속도를 향상시켰다."

자연어처리 분야에서 형태소 분석 시 대규모 어휘 검색에 트라이를 적용한 예문이다.

조금 더 깊게 보면

기본적인 트라이는 노드마다 알파벳 크기만큼의 자식 포인터를 두는 방식이라 메모리 낭비가 발생하기 쉬운데, 이를 보완한 변형으로 압축 경로를 사용하는 패트리시아 트라이(radix trie)나 접미사 트리(suffix tree) 등이 있습니다. 성능을 비교할 때는 삽입·검색·삭제의 시간복잡도뿐 아니라 노드당 메모리 사용량도 함께 논의되는 경우가 많습니다.

주의할 점

트라이는 문자열 개수가 많고 알파벳 크기가 크면 각 노드가 자식을 가리키는 포인터를 많이 가져야 해서 메모리 사용량이 커질 수 있다.