2023. 12. 20. 15:04ㆍ카테고리 없음
프로젝트를 진행하는 과정에서 우리 고객님들(?)의 요구사항 중에 "문장자동완성" 기능이 있었다.
맞다. 다들 예상했듯이 우리가 흔히 사용하는 카톡에서 주로 보는 그 기능이다.
그래서 오늘은 단어검색/문장자동완성기능에 많이 사용하는 트라이(Trie) 자료구조에 대해 알아보고자 한다.
우리가 기본적으로 사전에서 단어를 찾을 때(요즘 사전을 쓰나?) 그 단어가 있는 페이지 번호를 기억하고 있지 않는 이상, 대부분 아래와 같은 과정을 거칠것이다.
이 일련의 과정을 프로그램으로 구현한 것이 트라이(Trie)라는 자료구조다.
이것을 트리로 표현하면 다음과 같다.
"월드오브워크래프트" 게임 내의 명사로 이루어 사전(Data)을 만들어보자.
["월드오브워크래프트", "얼라이언스", "호드", "아서스", "아키몬드", "말가니스", "말퓨리온"]으로 이루어진 사전(Data)을 구성하면, 같은 접두사는 같은 노드로 겹쳐서 저장되는 특성 때문에 위와 같은 그림이 나온다.
그리고 보통 노드의 끝에 bool isEnd 이런 변수를 두어 어떤 문자열의 끝이라는 flag로 사용한다.
위 그림과 같이 트라이(Trie) 형식의 트리에 문자열을 저장하면, 검색 시 딱 문자열의 길이에 해당하는 시간만 소요되기 때문에 매우 효율적이다.
만약, "말퓨리온"을 검색한자고 가정한다면, 같은 접두사 즉, 같은 부모 노드를 가지기 때문에 "말가니스"를 비교 후, "말퓨리온"을 비교하는 것이 아니라, "말" → "퓨" → "리" → "온" 이렇게 검색할 수 있다.
오늘은 트라이(Trie)에 대해 간략하게 알아보았다.
공부하는 식빵맘 님과 4Legs_Archives 님의 블로그를 참고하였으며, 직접 코딩을 해보고 코드에 대한 내용도 추가하도록 하겠다.