트라이: 철자를 쓰는 트리

"해시맵은 'pippa'가 그 집합에 있는지 알려줘. 트라이는 'pip'으로 시작하는 단어를 전부 알려주고. 이 차이 하나가 우리가 써본 모든 자동완성을 굴려."

글자로 지은 트리

트라이(접두사 트리)는 문자열을 글자 단위로 저장해. 간선 하나가 글자 하나고, 루트에서 내려오는 각 경로가 접두사를 이루지. 접두사를 공유하는 단어들은 갈라지기 전까지 같은 경로를 함께 써. "cat", "car", "card"가 c→a→까지 같이 걷다가 거기서 갈라지는 식이야. 그리고 노드에 진짜 단어의 끝이라는 표시를 해두니까, 단어인 "car"와 단어로 가는 길목일 뿐인 "ca"를 구별할 수 있어.

비용이 쓸모 있게 달라

삽입과 조회는 글자마다 간선을 하나씩 걸으니까 O(L)이야. L은 키 길이고. 그리고 결정적으로 이 비용이 트라이가 단어를 몇 개 담고 있든 상관없어. 단어 열 개짜리 트라이든 천만 개짜리 트라이든 다섯 글자 단어는 다섯 단계에 찾아. 해시맵도 여기서는 빠르지만 그쪽 비용은 키 전체를 해싱하는 데 달려 있고, 트라이는 오직 키 길이에만 달려 있어.

킬러 기능: 접두사 쿼리

평범한 해시맵은 "pre로 시작하는 모든 키"를 바로 지원하지 않아. 트라이는 접두사 길이만큼 걸어서 그 노드에 도착한 다음 그 아래 서브트리를 순회하면 돼. 비용은 접두사 길이에 방문한 노드 수와 출력 크기를 더한 것으로 보는 게 정확해. 자동완성, 사전 접두사 조회, IP 최장 접두사 매칭에 쓸모가 있어. 다만 정렬된 문자열 구조나 접두사 인덱스 같은 다른 선택지도 있다는 건 알아 둬.

트라이는 문자열을 글자 경로로 저장하면서 접두사를 공유해. 조회와 삽입이 키 길이에 비례하는 O(키 길이)이고 저장된 키 개수와는 무관하지. 강점은 해시맵이 바로 주지 않는 'X로 시작하는 모든 단어' 같은 접두사 쿼리야. 자동완성, 맞춤법 검사, 라우팅에 써.

거래

트라이가 공짜는 아니야. 노드마다 자식 글자 맵이라는 오버헤드를 지고 있어서, 서로 관련 없는 문자열 몇 개만 담을 거면 평범한 해시 셋보다 메모리를 더 쓸 수도 있어. 절약은 많은 키가 접두사를 공유할 때라야 실제로 생기거든. 그리고 접두사가 필요 없는 순수한 정확 멤버십 확인이라면 해시 셋이 여전히 이겨. 늘 그렇듯이야. 트라이는 질의의 모양이 "접두사"일 때 제 몫을 하고, 아닐 때는 과한 도구야. 맞는 질의에 맞는 구조.

피파의 고백

자동완성을 해시 셋으로 만들어 보겠다고, 모든 키를 돌면서 key.startswith(prefix)를 확인하는 반복문을 짠 적이 있어. 키 하나 누를 때마다 O(n)이니 사전이 커지자 뚝뚝 끊기더라. 아빠가 트라이를 그려주니까 그 끊김이 사라졌어. 접두사 노드까지 한 번 걸어가서 그 아래 서브트리만 읽으면 되는 거였지. 여기서도 구조를 다시 보게 됐어. 해시 셋은 애초에 틀린 질문에 답하고 있었던 거야. '이 단어가 정확히 있나?'에는 환상적인데 '이걸 뭐가 이어받지?'에는 아무 힘이 없거든. 질의의 모양이 구조를 고르는 거야.

Code

삽입과 검색, 그리고 접두사 쿼리까지 갖춘 트라이·python

class Trie:
    def __init__(self):
        self.root = {}                  # 중첩 dict. '$' 가 단어 끝 표시

    def insert(self, word):             # O(len(word))
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # 문자당 엣지 하나 걷기/생성
        node["$"] = True                # 진짜 단어가 여기서 끝남 표시

    def search(self, word):             # O(len(word)) 정확-단어 조회
        node = self.root
        for ch in word:
            if ch not in node: return False
            node = node[ch]
        return "$" in node

    def starts_with(self, prefix):      # 해시맵에 없는 킬러 기능
        node = self.root
        for ch in prefix:
            if ch not in node: return []
            node = node[ch]
        words = []                      # 이 서브트리 안 모든 단어 모으기
        def collect(n, path):
            if "$" in n: words.append(prefix + path)
            for ch, child in n.items():
                if ch != "$": collect(child, path + ch)
        collect(node, "")
        return words

t = Trie()
for w in ["cat", "car", "card", "dog"]:
    t.insert(w)
print(t.search("car"))          # True
print(t.search("ca"))           # False — 접두사지 저장된 단어 아님
print(t.starts_with("car"))     # ['car', 'card'] — 접두사 쿼리, 트라이의 선물

Exercise

'to', 'tea', 'ted', 'ten', 'in', 'inn'을 트라이에 넣고 공유되는 구조를 그려 봐. 'tea', 'ted', 'ten'이 함께 쓰는 접두사 경로는 뭘까? 그다음 'te로 시작하는 모든 단어'를 찾을 때 비용이 왜 저장된 전체 단어 수가 아니라 접두사 길이와 방문한 서브트리 노드 수, 출력 크기에 달려 있는지 설명해.

Hint

'tea', 'ted', 'ten'은 t→e 경로를 함께 쓰다가 세 번째 글자에서 갈라져. 'te로 시작하는 모든 단어'는 'te' 노드까지 두 글자만 걸어간 뒤 그 아래 서브트리만 뒤져. 'to'나 'in', 'inn' 쪽 경로는 건드리지도 않지. 다만 결과를 만들어 내려고 방문한 노드와 출력한 글자 수는 비용에 포함해서 세야 해.

글자로 지은 트리

비용이 쓸모 있게 달라

킬러 기능: 접두사 쿼리

거래

피파의 고백

Code

External links

Exercise

Progress

댓글 0