-
요즘 운영체제에서는 단어 몇글자만 치면 자동완성 기능을 제공하는데
자동완성의 기본 알고리즘이 바로 트라이다.
자동완성을 만들려면 사전에 입력한 단어들을 저장하고 빠른시간안에 탐색 할 수 있어야 한다. 하지만 문자열은 숫자로 이루어진 이진트리와 달리 원소 비교를 상수시간 내에 할 수 없으므로 특화된 자료구조가 필요하다. 이때 유용한 자료구조가 트라이다.
구조는 다음과 같다.
만약 내가 TR, THE, TRY, TREE라는 단어를 저장해두었다고 하자. 그러면 다음과 같은 트리가 형성된다. 각각의 단어의 공통된 접두사를 부모로 두는 방법이다. 하지만 공통된 접두사가 내가 입력한 단어가 아니라면 bool 값을 이용해서 표현해야한다. 그림에는 하얀색 바탕으로 표현했다. 위 자료구조의 시간 복잡도는 트리의 높이로 볼수 있고 트리의 높이는 단어의 최대 길이와 같으므로 O(L)로 정의 할 수 있겠다.
예를들어 내가 TRY라는 문자가 있는 지 확인하고 싶다면 첫 문자 T로 비교를 한 후 존재하면 R을 비교, 그 후에는 Y를 비교해서 내가 찾으려 하는 노드가 존재하는지, 그리고 존재하면 사전에 입력된 단어인지를 확인하면 된다.
위 자료구조의 단점은 메모리를 너무 많이 잡아먹는다는 것이다. 나는 지금 TR, THE, TRY, TREE 이렇게 네개만 입력했는데 벌써 6개의 node가 필요하니 단어의 개수가 늘어나면 추가 메모리가 더 많이 필요할 것이다.
문자열에 특화된 자료구조는 이번이 처음이다. 자주 써먹어야겠다.
