Trie: 구글 자동 완성의 비밀!

Trie: 구글 자동 완성의 비밀!

혹시 검색어, 채팅 추천이 어떤 원리로 운영되는 지 궁금하신 적 있으신가요?
현실적으로는 프론트, 백, 데이터 프로세싱 등의 다방면의 접근이 필요하지만
그 중 백에서 사용 되는 모델은 트라이(Trie)를 기반으로 하는 것이 많습니다!

이는 트라이의 기능이 검색어를 효율적으로 찾는 것에 도움이 되기 떄문인데요.
우리는 여기서 Basic 한 Trie에 간단히 대해서 알아보겠습니다.

※ 현재 대부분 기업은 Basic이 아닌 훨씬 최적화, 변형된 트라이를 사용합니다.

트라이는 어떤 기능을 하나요?

트라이는 String-search, Substring-search 등을 수행합니다
이 중 String-search 기능을 예로 설명하겠습니다.
우리는 검색어 관리팀이고, n개 낱말의 리스트를 가지고 있다고 합시다.
가진 리스트는 {‘한국은행’, ‘한국만세’, ‘일본’, ‘국장’, ‘국물’,…, ‘국뽕’}

이 때, 한 유저가 기존의 리스트에 ‘국뽕‘이라는 낱말이 있는 지가 궁금합니다.
핵심: 어떻게 하면 리스트에서 이 낱말이 있는 지를 효율적으로 알 수 있을까요??
※ 다음으로 넘어가기 전에 혼자 한 번 고민해봅시다!

Brute-force 하게 해봅시다.

image

어렵게 생각하지 말고 리스트 안의 것 모두를 우리의 Query인 ‘국뽕’과 하나씩 비교합시다
한국은행과 국뽕을 먼저 비교하고, 다음은 한국만세, 다음은 일본 … 등등
n-1번 까지 있던 모든 글자와는 틀렸다는 것을 확인하고 마지막에서 와서야 겨우
‘국뽕’과 비교를 할 수 있게 되고, 우리는 ‘국뽕’이라는 낱말이 있다는 것을 발견합니다.

이를 시간 효율성에 비추어 생각하면 최악의 경우는 O(N*M)입니다.
이 때, N = 리스트의 길이, M = 쿼리 낱말의 길이입니다.
운좋게, 쿼리가 하나 일 경우에는 이 Brute-force 방법도 참아 줄만 합니다만

만약 궁금한 게 하나의 쿼리가 아니라, [‘국뽕’, ‘일본’, ‘나라’, ..] 처럼 K 개 쿼리의 리스트이면,
각각 쿼리도 똑같은 과정을 거치기에 시간효율성은 O(N* M *K)가 될 것입니다.
위의 시간 효율성은 굉장히 비효율적이며, 현실에서도 적용하기 어렵습니다.
이것을 해결하기 위해서 아래와 같은 트라이(Trie)라는 구조가 고안되었습니다.

트라이의 구조

트라이의 아이디어는 낱말을 하나 하나 글자로 쪼개어 트리로 저장한다입니다.
예를 들면 ‘한국은행’ -> [‘한’, ‘국’, ‘은’, 행’], ‘일본’ -> [‘일’, ‘본’]
과 같이 모두 쪼갠 후에 아래와 같은 과정을 거쳐 트리 형태로 저장을 합니다.

Trie를 만드는 단계:
만드는 단계는 아래와 같은 두 가지 경우로 진행됩니다.

  1. 낱말을 글자로 쪼갠 후 노드에 공통되는 글자가 있으면 그 글자 노드로 진행
  2. 낱말을 글자로 쪼꺤 후 노드에 그 글자가 없다면, 글자에 해당되는 노드를 만들고 진행

아래는 Trie를 만드는 과정 중 ‘한국만세’ 라는 낱말을 넣는 차례입니다.

image

아래는 Trie를 만드는 과정 중 ‘일본’ 이라는 낱말을 넣는 차례입니다.

image

Trie를 다 만든 단계:
위의 과정이 모두 끝나면 아래와 같습니다.

image

Query를 찾는 단계:
우리가 찾고싶은 쿼리는 ‘국뽕’이라고 한다면 먼저 ‘‘을 가진 노드를 찾고
‘에 해당하는 다음 노드로 넘어간다음, ‘‘이라는 노드를 찾으면 됩니다

image

이번에는 ‘일본’이라는 낱말을 찾는 경우입니다.

image

이번에는 ‘나라’ 라는 낱말을 찾는 경우인데, 첫 번째 노드부터, ‘나’ 라는 글자가
존재하지 않습니다. 따라서 여기엔 ‘나라’ 라는 낱말는 없다 라는 걸 바로 알 수 있습니다

image

트라이의 장단점

장점:
Query를 찾을 때, Brute-force를 이용하는 것보다 좋은 time-complexity를 가집니다.
특히, 처리하는 Query의 수가 많아지면 질수록 이 구조은 정말 유용합니다.

구현하는 것도 어렵지 않고 아이디어도 간단해서 여러 응용을 하기 좋습니다.
예로: Visted 같은 변수를 추가해서, 갯수를 추적하는 것도 가능합니다.

단점:
space-complexity면에서는 기존의 것보다 비효율적입니다.
대부분 구현과정에서 Map을 쓰게 되는데, 이 때 space가 꽤 듭니다.

쿼리가 워낙 적으면 오히려 시간이 걸릴 수도 있다.
일단 이 구조는 만들 때도 String hash를 하기 때문에 시간이 걸립니다.
따라서 쿼리 양은 되게 적고, 저장되어있는 단어는 상대적으로 많을 때
오히려 Brute-force한 것보다도 더 안좋은 execution-time을 가질 수도 있습니다.

실제 구현 by Python

구현 아이디어:

  1. linked-list
  2. Dictionary
  3. iteration
  4. Tree

Code:

class Trie:

    def __init__(self):
        self.root = {}

    def insert(self, s):
        cur = self.root
        while s:
          if s[0] not in cur: cur[s[0]] = {}
          cur = cur[s[0]]
          s = s[1:]
        cur[0] = {}

    def find(self, s)->bool:
        cur = self.root;
        while s:
            if s[0] not in cur: return False
            cur = cur[s[0]]
            s = s[1:]
        if 0 in cur: return True
        else: return False