Trie 자료구조를 통한 자동완성 검색엔진 구현 - boostcampwm-2022/web17-waglewagle GitHub Wiki
- 저희는 소그룹이 비슷한 이름으로 여러 개가 생성되면서 사용자가 분산되는 상황을 문제라고 인식하고, 키워드 자동 완성 기능을 개발하였습니다.
- 처음에는 정규 표현식을 통해서 검색어가 바뀔 때마다 모든 키워드를 탐색하고자 하였으나 성능적으로 비효율적이라고 생각되어서 알고리즘의 변화가 필요하였습니다.
- 검색 엔진에서 사용되는 알고리즘들을 조사, 비교하여 현재 프로젝트에 가장 적절한 알고리즘을 선정하기로 하였습니다.
- 정규 표현식과, 이진 탐색, 트라이 등의 방법을 고려하여 시간 복잡도를 분석하였습니다.
| N = 단어의 개수, M = 문자열 길이 |
사전 작업 시간 복잡도 |
탐색 시간 복잡도 |
| 전체 탐색(정규 표현식) |
X |
O(M * N) |
| 이진 탐색 |
O(N * M * logN) (정렬) |
O(M * logN) |
| 트라이 |
O(N * M) (트라이 생성) |
O(M) |
- 사전 생성 시간이 있고, 메모리를 많이 차지하는 단점이 있지만, 커뮤니티 접속 시 한번만 실행하면 되고, 탐색이 빈번하게 발생하는 검색 엔진 특성상 트라이가 가장 효율적이라고 결론을 내렸습니다.
- 결과적으로 탐색 시간 복잡도를 O(M * N)에서 O(M)까지 감소시켰습니다.(M: 문자열 길이, N: 단어의 개수)
⚠️ **GitHub.com Fallback** ⚠️