트라이

트라이는 문자열을 앞 글자부터 한 글자씩 따라 내려가며 찾아 줍니다. 앞부분이 같은 문자열들은 그 앞부분을 한 번만 저장해 함께 씁니다. 그래서 「이 글자들로 시작하는 문자열을 모두 달라」는 물음에 나머지 문자열을 훑지 않고 답합니다.

상세

이 절은 문자열 넷(car · cart · cat · dog)을 트라이에 넣어 보고 그 모양부터 봅니다. 그 모양 위에서 찾기와 넣기, 접두사로 찾기가 어떻게 도는지 따라갑니다. 끝으로 비용을 다른 자료구조와 견주고 트라이가 쓰이는 곳을 봅니다.

글자를 따라 내려가는 모양

트라이는 트리의 한 종류입니다. 트리는 맨 위의 뿌리 하나에서 아래로 갈라져 나가기만 하는 모양입니다. 갈라진 갈래끼리는 다시 만나지 않습니다.

트리에서 갈라지는 점 하나하나를 노드라고 부릅니다. 노드와 노드를 잇는 선은 간선이라고 부릅니다.

트라이에서는 간선 하나가 글자 하나를 뜻합니다. 뿌리에서 c 간선을 타고 a 간선을 타고 t 간선을 타면 cat 을 읽은 것입니다. 문자열은 노드 안에 들어 있지 않습니다. 뿌리에서 내려온 길이 문자열을 적습니다.

flowchart TD
    R["뿌리"] -->|c| C["c"]
    R -->|d| D["d"]
    C -->|a| CA["ca"]
    CA -->|r| CAR["car · 끝"]
    CA -->|t| CAT["cat · 끝"]
    CAR -->|t| CART["cart · 끝"]
    D -->|o| DO["do"]
    DO -->|g| DOG["dog · 끝"]

그림의 노드 이름은 뿌리에서 거기까지 내려오며 읽은 글자를 이어 붙인 것입니다. 간선 옆 글자가 그 간선이 뜻하는 글자입니다. 「끝」은 바로 아래 「끝 표시」 소절에서 풉니다.

car · cart · cat 셋은 c 노드와 ca 노드를 함께 지나갑니다. 앞부분이 같은 문자열끼리 그 앞부분의 노드를 나눠 쓰는 것입니다. 네 문자열의 글자는 모두 13개입니다. 노드는 뿌리를 빼고 8개입니다.

문자열의 앞부분을 접두사(prefix)라고 부릅니다. ca 는 car 의 접두사입니다. cat 의 접두사이기도 합니다. 트라이의 노드 하나는 접두사 하나를 뜻합니다. 그래서 트라이를 접두사 트리라고도 부릅니다.

트라이(trie)라는 이름은 꺼내 찾기를 뜻하는 영어 낱말 retrieval 의 가운데 네 글자 trie 를 딴 것입니다. 이 철자를 원래대로 읽으면 「트리」가 되어 tree 와 소리가 같습니다. 그래서 흔히 「트라이」로 읽어 트리와 가릅니다.

끝 표시

car 노드는 cart 로 가는 길 한가운데 있습니다. ca 노드도 car 로 가는 길 한가운데 있습니다. 그런데 car 는 넣은 문자열이고 ca 는 넣은 적이 없습니다.

모양만으로는 이 둘을 가를 수 없습니다. 그래서 노드마다 「여기서 끝나는 문자열이 있다」는 표시를 하나 둡니다. 이 표시를 끝 표시라고 부르겠습니다. 그림에서 「끝」이 붙은 노드가 끝 표시를 가진 노드입니다.

끝 표시 대신 값을 달 수도 있습니다. car 노드에 값 3 을 달면 「car → 3」을 담은 셈입니다. 이렇게 하면 트라이를 문자열 키로 값을 찾는 맵으로 씁니다.

찾기와 넣기

찾기는 뿌리에서 시작해 글자 하나마다 간선 하나를 탑니다. cart 를 찾으면 c · a · r · t 간선을 차례로 타고 cart 노드에 닿습니다. 닿은 노드에 끝 표시가 있으면 들어 있는 문자열입니다.

찾기가 실패하는 경우는 둘입니다. 첫째는 다음 글자로 가는 간선이 없을 때입니다. cow 는 c 노드에 o 간선이 없어서 거기서 멈춥니다.

둘째는 글자를 다 썼는데 끝 표시가 없을 때입니다. ca 는 ca 노드까지 잘 내려가지만 그 노드에 끝 표시가 없습니다. 그래서 ca 는 들어 있지 않은 문자열입니다.

flowchart TD
    S["뿌리에서 시작"] --> Q{"다음 글자로 가는 간선이 있나"}
    Q -->|없다| N["들어 있지 않다"]
    Q -->|있다| M["그 간선을 타고 한 층 내려간다"]
    M --> L{"글자가 남았나"}
    L -->|남았다| Q
    L -->|다 썼다| E{"끝 표시가 있나"}
    E -->|있다| Y["들어 있다"]
    E -->|없다| N

넣기는 찾기와 같은 길을 갑니다. 다른 점은 간선이 없을 때 멈추지 않고 새 노드를 만든다는 것입니다. 마지막 글자에 닿으면 그 노드에 끝 표시를 켭니다.

찾기와 넣기는 모두 문자열의 글자 수만큼만 내려갑니다. 트라이에 문자열이 넷 들어 있든 백만 개 들어 있든 cart 를 찾을 때는 간선 네 개를 탑니다. 들어 있는 문자열 수는 내려가는 횟수를 바꾸지 않습니다.

접두사로 찾기

트라이가 다른 자료구조와 갈리는 동작이 이것입니다. ca 로 시작하는 문자열을 모두 찾으려면 먼저 ca 노드까지 내려갑니다. 그다음 그 아래에 매달린 노드를 전부 훑으며 끝 표시가 있는 것을 모읍니다.

flowchart TD
    R["뿌리"] -->|c| C["c"]
    C -->|a| CA
    subgraph 훑음["ca 아래만 훑는다"]
        CA["ca"] -->|r| CAR["car · 끝"]
        CA -->|t| CAT["cat · 끝"]
        CAR -->|t| CART["cart · 끝"]
    end
    subgraph 안들름["들르지 않는 갈래"]
        D["d"] -->|o| DO["do"] -->|g| DOG["dog · 끝"]
    end
    R -->|d| D

훑는 범위는 ca 노드 아래 상자 안뿐입니다. d 로 시작하는 갈래는 들르지 않습니다. 모인 결과는 car · cart · cat 셋입니다.

자식 노드를 글자 순서대로 들르면 결과도 사전 순서로 나옵니다. 따로 정렬하지 않아도 됩니다. 입력창에 몇 글자를 치면 그 글자로 시작하는 후보를 늘어놓는 자동 완성이 이 동작입니다.

파이썬으로 옮긴 트라이

위에서 본 넣기와 찾기를 파이썬 코드로 옮깁니다. 노드 하나는 자식 노드를 담는 딕셔너리와 끝 표시 하나를 가집니다. 딕셔너리의 키가 간선의 글자입니다.

class Node:
    def __init__(self):
        self.kids = {}
        self.end = False

def insert(root, word):
    n = root
    for ch in word:
        n = n.kids.setdefault(ch, Node())
    n.end = True

def find(root, word):
    n = root
    for ch in word:
        if ch not in n.kids:
            return None
        n = n.kids[ch]
    return n

insert 는 글자마다 자식을 찾고 없으면 새 노드를 만듭니다. setdefault 가 그 두 일을 한 줄로 합니다. find 는 간선이 없으면 None 을 돌려줍니다. 다 내려가면 마지막 노드를 돌려줍니다.

이제 앞의 네 문자열을 넣고 찾아 봅니다.

root = Node()
for w in ["car", "cart", "cat", "dog"]:
    insert(root, w)

find(root, "car").end   # True
find(root, "ca").end    # False
find(root, "cow")       # None

car 는 끝 표시가 켜져 있어 True 입니다. ca 는 노드는 있지만 끝 표시가 꺼져 있어 False 입니다. cow 는 o 간선이 없어 노드 자체를 못 찾습니다.

접두사로 찾기는 찾은 노드 아래를 훑는 함수 하나를 더하면 됩니다.

def words(n, prefix):
    if n.end:
        yield prefix
    for ch in sorted(n.kids):
        yield from words(n.kids[ch], prefix + ch)

hit = find(root, "ca")
list(words(hit, "ca"))  # car, cart, cat

words 는 자식마다 자기 자신을 다시 부릅니다. 함수가 자기를 다시 부르는 이 방식이 재귀입니다. sorted 로 글자 순서대로 들르므로 결과가 사전 순서로 나옵니다.

다른 자료구조와 견준 비용

비용을 견주려고 글자 둘을 둡니다. 들어 있는 문자열의 수를 n, 찾는 문자열의 길이를 L 이라고 합니다.

입력이 커질 때 걸리는 시간이 어떻게 느는지를 시간 복잡도라고 합니다. O(L) 은 걸리는 시간이 L 에 비례해 는다는 뜻입니다.

견줄 상대는 둘입니다. 해시테이블은 키로 숫자 하나를 계산해 그 숫자로 저장 위치를 바로 정합니다. 문자열 키를 담을 때 가장 먼저 떠올리는 자료구조입니다.

다른 하나는 이진 탐색 트리입니다. 노드마다 왼쪽에 작은 값, 오른쪽에 큰 값을 매달아 둡니다. 찾을 때는 노드의 값과 견주며 내려갑니다.

값이 문자열이면 작고 큼은 사전 순서로 가립니다. car 는 세 번째 글자 r 이 t 보다 앞서서 cat 보다 작습니다.

이진 탐색 트리에서 견주는 횟수는 트리의 높이를 넘지 않습니다. 높이는 뿌리에서 가장 깊은 노드까지 내려가는 층 수입니다.

한쪽으로 치우치지 않게 양쪽 갈래의 높이를 고르게 맞춰 두면 높이가 log n 언저리로 유지됩니다. log n 은 n 이 두 배가 돼도 한 층만 는다는 뜻입니다.

해시테이블 칸의 「평균」은 보통 때 그렇다는 뜻입니다. 서로 다른 키가 같은 숫자로 계산되는 해시 충돌이 한곳에 몰리면 그 키들을 하나씩 견주느라 더 걸립니다.

이진 탐색 트리 칸에 L 이 곱해지는 것은 한 번 견주는 데 드는 일 때문입니다. 문자열 둘을 견주려면 앞 글자부터 차례로 읽어 처음 다른 글자를 찾습니다. 그래서 한 번 견줄 때 글자를 최대 L 개 읽습니다. 이것을 log n 번 하므로 L × log n 입니다.

첫 줄만 보면 트라이와 해시테이블은 둘 다 문자열 길이만큼 일합니다. 해시테이블도 숫자를 계산하려면 글자를 모두 읽어야 하기 때문입니다.

갈리는 것은 둘째 줄과 셋째 줄입니다. 해시테이블은 키를 흩어 놓아서 앞부분이 같은 키끼리 모여 있지 않습니다. 그래서 접두사로 찾으려면 전부 훑어야 합니다.

이진 탐색 트리는 둘째 줄과 셋째 줄의 일을 트라이처럼 해낼 수 있습니다. 이진 탐색 트리와 갈리는 것은 첫 줄입니다. 이진 탐색 트리는 들어 있는 문자열이 늘면 견주는 횟수 log n 도 함께 늡니다. 트라이는 앞에서 본 대로 들어 있는 문자열 수와 상관없이 간선 L 개만 탑니다.

메모리 비용

해시테이블에 넣으면 문자열 하나가 한 덩어리로 들어갑니다. 트라이에서는 같은 문자열이 글자마다 노드 하나로 쪼개져 들어갑니다. 그리고 노드마다 자식을 가리키는 포인터를 따로 들고 있습니다.

자식을 담는 방법에 따라 이 비용이 달라집니다. 하나는 글자 종류만큼 칸을 가진 배열입니다. 영어 소문자만 다루면 노드마다 26칸을 두고 a 는 0번 칸, b 는 1번 칸에 둡니다. 다음 글자를 바로 찾지만 대부분의 칸이 비어 있습니다.

다른 하나는 위 코드처럼 글자를 키로 하는 딕셔너리입니다. 빈칸은 없어집니다. 대신 노드마다 딕셔너리를 하나씩 따로 들고 있습니다. 그 딕셔너리들이 차지하는 메모리가 더해집니다.

접두사를 많이 나눌수록 노드가 덜 생깁니다. read · reader · reading 처럼 같은 말로 시작하는 단어가 많은 영어 단어 목록은 잘 나눕니다. x7qa · m2bz · 9kfe 처럼 무작위로 만든 식별자는 앞부분이 제각각이라 거의 나누지 못합니다. 그러면 글자 수만큼 노드가 생깁니다.

자식이 하나뿐인 노드가 줄지어 있으면 그 줄을 노드 하나로 합칠 수 있습니다. 앞 그림의 c 노드는 자식이 a 하나뿐이라 c 와 ca 를 노드 하나로 합칠 수 있습니다. 이렇게 합친 트라이가 래딕스 트리입니다.

트라이가 쓰이는 곳

접두사로 찾는 일이 잦은 곳에 트라이가 쓰입니다. 자동 완성이 첫째입니다. 그 밖에 둘을 더 봅니다.

인터넷에서 데이터를 나르는 장비인 라우터는 목적지 주소를 보고 다음에 넘길 이웃을 고릅니다. 그때 보는 표가 라우팅 테이블입니다. 표의 줄은 「주소가 이 비트들로 시작하면 이 이웃에게 넘긴다」 꼴입니다.

한 주소에 맞는 줄이 여럿일 수 있습니다. 그때는 주소와 가장 길게 겹치는 줄을 고릅니다. 이 규칙이 최장 접두사 일치입니다.

주소를 비트 하나씩 트라이에 담으면 이 규칙을 한 번 내려가는 것으로 풉니다. 비트를 따라 내려가며 끝 표시를 만날 때마다 그 줄을 기억합니다. 더 내려갈 간선이 없을 때 마지막으로 기억한 줄이 답입니다.

줄이 둘 있다고 합시다. 10 으로 시작하면 이웃 A, 1011 로 시작하면 이웃 B 입니다. 목적지 주소가 10110 으로 시작하면 두 줄이 다 맞습니다.

flowchart TD
    R["뿌리"] -->|1| N1["1"]
    N1 -->|0| N10["10 · 끝 · 이웃 A"]
    N10 -->|1| N101["101"]
    N101 -->|1| N1011["1011 · 끝 · 이웃 B"]
    N1011 -.- X["0 으로 가는 간선이 없어 멈춘다"]

내려가며 10 노드에서 이웃 A 를, 1011 노드에서 이웃 B 를 기억합니다. 다음 비트 0 으로 가는 간선이 없어 멈춥니다. 마지막에 기억한 이웃 B 가 답입니다.

컴파일러가 프로그램에 나오는 이름을 모아 두는 심볼 테이블도 트라이로 담을 수 있습니다. 심볼 테이블은 변수 이름 같은 문자열로 그 이름의 정보를 찾는 표입니다. 앞에서 본 「끝 표시 대신 값을 단다」가 그 방법입니다.

트라이가 안 맞는 데이터

문자열 전체로만 찾고 접두사로는 찾지 않는 데이터가 그렇습니다. 그때는 해시테이블도 같은 O(L) 로 찾습니다. 해시테이블은 문자열을 노드로 쪼개 들고 있지 않아 메모리를 덜 씁니다.

앞부분이 제각각인 키도 트라이와 맞지 않습니다. 앞의 무작위 식별자처럼 나눠 쓸 접두사가 거의 없으면 글자마다 노드가 생깁니다. 트라이가 아끼려던 메모리를 오히려 더 씁니다.

관련 항목

트라이가 속하는 상위 분류

자료구조 · 트리 · 탐색 트리 · 비선형 자료구조 · 추상 자료형

트라이를 이루는 구성 요소

노드 · 간선 · 루트 노드 · 리프 노드 · 자식 노드 · 포인터 · 접두사 · 문자열

트라이의 하위 종류

래딕스 트리 · 패트리샤 트라이 · 이진 트라이 · 접미사 트리 · 삼진 탐색 트리 · 이중 배열 트라이 · 해시 배열 매핑 트라이

트라이로 구현하는 추상 자료형

맵 · 집합 · 연관 배열 · 심볼 테이블

트라이와 겨루는 문자열 키 저장 방식

해시테이블 · 이진 탐색 트리 · 균형 이진 탐색 트리 · B-tree · 정렬된 배열 · 접미사 배열 · 스킵 리스트

트라이로 푸는 문제

자동 완성 · 최장 접두사 일치 · 라우팅 테이블 · 맞춤법 검사 · URL 라우팅 · 아호-코라식 알고리즘 · 검색 엔진 · IP 주소

트라이를 훑고 다루는 알고리즘

깊이 우선 탐색 · 너비 우선 탐색 · 재귀 · 사전식 순서 · 기수 정렬

트라이의 비용을 재는 지표

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 분기 계수 · 캐시 지역성