Trie 자료구조로 자동완성 검색엔진 만들기

Problem

• 소그룹의 활성도를 위해 키워드를 등록하고자 할 때 비슷한 키워드의 중복 생성 방지하여 그룹의 인원이 분할되지 않도록 하는 작업이 필요하게 되었다.

Think

• 처음에는 정규 표현식을 통해서 검색어가 바뀔 때마다 모든 키워드를 탐색하고자 하였으나 성능적으로 비효율 적이라고 생각되어서 알고리즘의 변화가 필요했다.

Solution

• 검색 엔진에서 사용되는 알고리즘들을 조사, 비교하여 현재 프로젝트에 가장 적절한 알고리즘을 결정했다.

Process

• 정규 표현식과, 이진 탐색, 트라이 등의 방법을 고려하여 시간 복잡도를 분석하니 아래와 같은 결과가 나왔다.

Result

• 사전 생성 시간이 있고, 메모리를 많이 차지하는 단점이 있지만, 커뮤니티 접속 시 한번만 실행하면 되고, 탐색이 빈번하게 발생하는 검색 엔진 특성상 트라이가 가장 효율적이라고 결론을 내릴 수 있었다.
• 결과적으로 탐색 시간 복잡도를 O(M * N)에서 O(M)까지 감소시킬 수 있었다.(M: 문자열 길이, N: 단어의 개수)