Ch.16 트라이(trie)해 보는 것도 나쁘지 않다 (도서 요약 "누구나 자료구조와 알고리즘")
검색 자동완성 기능은 "catn"이라고 입력하면 자동으로 "catnip"이나 "catnap" 같은 단어를 추천해준다. 단어를 자동으로 완성하기 위해 스마트폰은 전체 단어 사전에 접근한다.
하지만 영단어를 전부 배열에 저장했다면, "catn"으로 시작하는 단어를 찾기 위해 모든 단어를 검색해야 한다. O(N)이라 비효율적이다. 해시 테이블도 단어를 통째로 해싱해야 값을 저장할 메모리 위치가 결정되니 도움이 안 된다.
'정렬된 배열'에 단어를 저장하면 성능이 크게 개선된다. 배열에 단어가 알파벳순으로 들어 있으면 이진 검색으로 O(longN) 시간 안에 "catn"으로 시작하는 단어를 찾을 수 있다. 심지어 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 더 빨라질 수도 있다.
'트라이'는 자동 완성이나 자동 수정 같은 기능을 지원한다. 물론 IP 주소나 전화번호를 처리하는 애플리케이션 등에도 쓰인다.
16. 1 트라이
'트라이(trie)'는 트리의 한 종류이다. 자동 완성 같은 텍스트 기반 기능에 이상적이다.
트라이라는 단어는 사실 '추출(retrieval)'이라는 단어에 유래한다. 따라서 엄밀히 말해 "트리(tree)"로 발음해야 하지만, 트리는 모든 트리 기반 자료 구조에 보편적으로 쓰이는 용어이므로 혼동을 막기 위해 주로 "트라이(trie)"로 발음한다.
트라이의 구현 방식은 다양하다. 어떤 구현이든지 사용할 수 있다. 이번에는 가장 간단하고 이해하기 쉬운 구현으로 설명하겠다.
'트라이'도 대부분의 트리처럼 다른 노드를 가리키는 노드들의 '컬렉션'이다. 하지만 '이진 트리'와 다르게, 트라이 노드는 자식 노드의 개수에 제한이 없다. (이진 트리는 자식 노드의 개수가 2개뿐이다)
각 트라이 노드마다 '해시 테이블'을 포함하며, 해시 테이블에서 키는 '알파벳'이고, 값은 트라이의 '다른 노드'다.
루트 노드는 키가 "a"와 "b"와 "c"인 해시 테이블을 포함한다. 값은 이 노드의 자식인 다른 트라이 노드다. 자식 역시 마찬가지로 그 자식을 가리키는 해시 테이블을 포함한다.
해시 테이블에서 '키'는 문자열이고, '값'은 다른 트라이 노드의 인스턴스다.
16. 2 단어 저장
그렇다면 어떻게 단어를 저장할까?
"ace", "bad", "cat" 이라는 단어를 트라이에 저장해보자.
트라이는 각 단어의 각 문자를 각각의 트라이 노드로 바꿔 세 개의 단어를 저장한다. 예를 들어 루트 노드에서 시작해 키 "a"를 따라가면 키 "c"를 포함하는 자식 노드를 가리킨다. 키 "c"는 다시 키 "e"를 포함하는 노드를 가리킨다. 이 세 문자를 하나로 연결하면 단어 "ace"가 된다.
단어들의 마지막 문자에도 자식 노드가 있다.
키가 ' * '인 해시 테이블은 값으로 null을 넣는다. 이는 단어의 끝을 나타낸다.
만약 "act"란 새로운 단어를 추가하고 싶다. 이미 존재하는 기존 키 "a", "c"는 그대로 두고 키 "t"를 포함하는 새 노드를 추가한다.
이제 자식 노드가 "e"와 "t" 둘이다. 이렇게 함으로써 "ace"와 "act" 둘 다 유효한 사전 단어가 됐다.
각 해시 테이블의 키를 그 자식 노드를 가리키는 화살표 옆에 표시했다.
만약 트라이에 "bat"와 "batter"을 저장하고 싶다고 하자. "batter"
첫 번째 "t"는 키가 둘인 노드를 가리킨다. 한 키는 값이 null인 ' * ' 이고, 나머지 한 키는 값이 또 다른 노드를 가리키는 "t"다. 즉 "bat" 자체가 하나의 단어임과 동시에 더 긴 "batter" 의 접두사임을 나타낸다.
' * ' 은 단어의 일부도, 단어일 수 있음을 나타낸다.
더 복잡한 예제로 "ace", "act", "bad", "bake", "bat", "batter", "cab", "cat", "catnap", "catnip"을 포함하는 트리다.
실제 프로그램에 쓰이는 트라이는 단어를 수천 개 포함한다. 자동 완성 기능을 개발하려면 먼저 기초 트라이 연산부터 분석해야 한다.
16. 3 트라이 검색
트라이에 어떤 문자열이 있는지 알아보는 '검색'은 가장 대표적인 트라이 연산이다.
검색의 목적은 크게 두 가지다.
(1) 문자열이 완전한 단어인지 알아내는 것
(2) 문자열이 최소한 어떤 단어의 접두사인지 알아내는 것
먼저 접두사를 찾는 검색을 구현하면 완전한 단어도 자연스레 찾을 수 있다.
접두사 검색 알고리즘은 다음과 같은 단계를 수행한다.
예를 들어 트라이에서 "cat"을 검색해보자.
currentNode라는 변수를 만들고, currentNode에 루트 노드를 할당한다. (예제에선 문자열의 첫 번째 문자인 "c"를 가리킨다.) 루트 노드에 키가 "c"인 자식이 있으니 currentNode를 그 키의 값으로 업데이트 한다.
이어서 다음 문자인 "a"를 가리키며 검색 문자열 내 문자들을 계속 순회한다.
currentNode에 키가 "a"인 자식이 있는지 검사한다. 그리고 그 자식을 새로 할당한다. 계속해서 문자열 내 다음 문자인 "t"를 찾는다.
검색 문자열 "t"를 가리키는 중이다. currentNode에 "t"라는 자식이 있으니 그 자식을 따라간다.
검색 문자열 끝까지 도달했으니 트라이에서 "cat"을 찾았다.
16. 4 트라이 검색의 효율성
트라이 검색의 장점은 엄청난 효율성이다.
검색 문자열의 각 문자를 한 번에 하나씩 살펴본다. 그러면서 각 노드의 해시 테이블을 사용해 한 단계만에 적절한 자식 노드를 찾는다. 해시 테이블 룩업에는 딱 O(1) 시간이 걸린다. 따라서 알고리즘은 검색 문자열 내 문자 수 만큼 단계가 걸린다.
이는 정렬된 배열에 이진 검색을 수행하는 것보다 훨씬 빠르다. 이진 검색은 O(logN)인 반면, 트라인 검색은 검색하려는 단어 내 문자 수 만큼의 단계만 걸린다. 단어 "cat"은 3단계면 된다.
트라이 검색은 빅 오로 나타내가 약간 까다로운데, 단계 수가 검색 문자열의 길이에 따라 달라지기 때문에 상수가 아니라 O(1)이라 말할 수 없다. 또한 N은 일반적으로 자료 구조 내 데이터 양을 말하는데 O(N)은 오해의 소지가 있다. N은 트라이 내 노드 수를 뜻하기 때문이다. (검색 문자열 내 문자 수는 더 적다)
그래서 이 복잡도를 O(K)라 부른다. K는 검색 문자열 내 문자 수다.
트라이 구조에서 검색 문자열마다 길이가 다르므로 O(K)가 상수는 아니지만, 상수 시간과 비슷하다. 상수가 아닌 알고리즘은 대부분 처리해야 할 데이터양에 따라 좌우되는데 O(K) 알고리즘에서는 트라이가 엄청나게 커지더라도 검색 속도에 영향이 없다. 문자 3개로 된 문자열이면 트라이가 얼마나 크든 항상 3단계만 걸리기 때문이다.
알고리즘 속도에 영향을 미치는 용인은 사용 가능한 전체 데이터가 아니라 입력 크기뿐이다. 그래서 O(K) 알고리즘은 매우 효율적이다.
16. 5 트라이 삽입
트라이에 새 단어를 삽입하는 과정은 기존 단어를 검색하는 과정과 비슷하다.
currentNode라는 변수를 만들고, 검색 문자열의 각 문자를 순회한다. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다. 자식이 있다면 current Node를 그 자식 노드로 업데이트하고 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
만약 currentNode에 현재 문자와 일치하는 자식 노드가 없으면 자식 노드를 생성하고 currentNode를 이 새 노드로 업데이트 한다.
삽입할 단어의 마지막 문자까지 삽입했으면 마지막 노드에 ' * ' 자식을 추가해 단어가 끝났음을 알린다.
16. 6 마무리
지금까지 '이진 탐색 트리', '힙', '트라이'라는 세 종류의 트리를 살펴봤다. 이 밖에 많은 종류의 트리가 있다. 각 트리마다 특정 상황에 유용하게 쓰일만한 고유한 성질과 동작을 지닌다.
다음은 마지막 자료 구조로 넘어갈 것이다. 트리에 대해 배운 내용은 '그래프'를 이해하는 바탕이 된다.
해당 글은 '누구나 자료구조와 알고리즘' 책의 내용을 기반으로 작성되었습니다.
오로지 학습용으로 작성하였음을 밝힙니다.
더 자세한 내용을 확인하고 싶다면 해당 저서를 참고하시길 바랍니다.