트라이 (컴퓨팅)

"A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이. 이 예제에는 모든 자식 노드가 알파벳 순으로 왼쪽에서 오른쪽으로 정렬되어 있지는 않다. (루트 노드와 't' 노드)

트라이(trie)는 컴퓨터 과학에서 탐색 트리의 일종이다. 동적 집합이나 연관 배열을 저장하는 데 사용되는 트리 자료 구조이다. 주로 문자열이 키인 경우가 많다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산된다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 루트는 빈 문자열에 연관된다. 일부 내부 노드가 키에 대응할 수도 있지만, 일반적으로 키는 단말에 연관되는 경향이 있다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 메모리에 최적화 된 경우는 기수 트리가 된다.

예시에서 키는 노드에, 값은 그 아래에 있다. 완전한 단어 키마다 연관된 임의의 정수가 있는 식이다. 트라이는 트리 모양인 결정적 유한 오토마타로 볼 수도 있다. 트라이 오토마타로 생성한 각 유한 언어(finite language)는 결정적 비순환 유한 상태 오토마타로 압축할 수 있다.

트라이는 문자열이 키인 경우가 흔하지만, 꼭 그래야 하는 것은 아니다. 어떻게 구성된 정렬된 리스트라도 비슷한 기능을 제공할 수 있는 동등한 알고리즘을 적용할 수만 있다면 상관 없다. 이를테면 숫자나 도형의 리스트로 구성한 순열 같은 것이 가능하다. 정수나 메모리 주소 같은 고정 길이 이진 자료를 표현하는 각각의 비트로 구성된 트라이를 특별히 비트 트라이라고 부른다.

역사와 어원

트라이의 개념은 1959년 René de la Briandais가 처음 설명하였다.^:336 트라이(trie)라는 용어는 에드워드 프레드킨이 2년 뒤에 붙인 이름인데, 이 때는 트리(/ˈtriː/)라고 불렀다. 그러나 말로 할 때 트리(tree)와 구분되지 않는 경향이 있었기 때문에 다른 사람들은 트라이(/ˈtraɪ/)라고 부르기 시작하게 되었다.

응용

다른 데이터 구조의 대체

트라이는 이진 검색 트리에 비해 몇 가지 장점이 있다.

해시 테이블을 대체하는 데도 사용할 수 있다. 다음과 같은 장점이 있다.

• 불완전한 해시 함수를 사용하는 해시테이블과 비교할 때, 자료에 접근할 때 최악의 경우 더 더 유리한 시간복잡도를 갖는다. m이 탐색할 문자열의 길이일 때 시간복잡도는 O(m)이다. 보통 해시테이블은 탐색 시간이 O(1)이고 해시 함수 평가 시간이 O(m)이지만, 불완전한 해시 테이블은 키 충돌이 일어날 수 있으므로, O(N)이 될 수 있다.
• 트라이에서는 키 충돌이 일어나지 않는다.
• 여러 값이 하나의 키와 연관되어 있지 않는 한 버킷이 필요 없다.
• 해시 함수가 없어도 된다. 키가 늘어날 때 해시 함수를 변경할 필요도 없다.
• 모든 항목이 키에 따라 사전순으로 정렬되어 있다.

반면 다음과 같은 단점도 있다.

• 조회는 해시 테이블보다 느릴 수 있다. 특히 주 메모리에 비해 임의 접근 비용이 큰 하드 디스크 드라이브와 같은 보조 기억장치에서 직접 읽는다면 더욱 그렇다.
• 부동소수점과 같이 문자열로 장황하게 표시되는 자료의 경우 무의미하게 길게 늘어진 접두사와 노드를 가질 수 있다. (한편 표준 IEEE 부동소수점 수는 비트 트라이로 처리할 수는 있다.)
• 트라이가 메모리를 더 소비할 수 있다. 대부분의 해시 테이블에서는 전체 항목을 하나의 메모리 청크에 올리곤 하지만, 트라이에서는 검색 문자열의 각 문자마다 메모리가 할당될 수 있다.

사전 표현

휴대 전화에서 쓰이는 것 같은 예측 문자나 자동 완성에 필요한 사전을 저장하는 것이 일반적인 응용 가운데 하나이다. 트라이에서 빠르게 조회, 삽입, 삭제할 수 있는 기능을 활용하는 응용이다. 그러나 각 키마다 부가적인 정보를 저장할 필요가 없이 키만 저장하면 되는 경우는 최소 결정 비순환 유한 상태 오토마타(DAFSA)가 트라이보다 적은 공간을 사용한다. DAFSA는 서로 다른 키에서 접미사를 공유하는 경우 동일한 가지를 이용하는 방식으로 압축하기 때문이다.

맞춤법 검사나 하이픈 연결 소프트웨어에 사용되는 알고리즘과 같은 근사 일치 알고리즘을 구현하는 데도 적합하다.

알고리즘

트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리이다. 탐색은 키 문자열과 연관된 값을 반환하고, 삽입은 문자열(키)과 그 값을 삽입한다. 키의 길이가 m일 때 탐색과 삽입 모두 O(m) 시간에 수행된다.

다음은 단순한 트라이의 노드를 표현할 수 있는 Node 클래스이다.

class Node:
   def __init__(self)
        # 이 구현과 같이 dict를 쓰면 하위 노드가 사전순 정렬되지 않는다.
        # 따라서 정렬의 예제와는 다르다. 대신 배열을 쓸 수 있다.
       self.children: Dict[str, Node] = {}  # 문자를 노드로 대응
       self.value: Optional[Any] = None

children은 문자에 관해 하위 노드를 담는 사전이다. 노드가 완전한 문자열을 가리킬 때 '단말' 노드라고 부른다.조회는 다음과 같이 한다.

def find(node: Node, key: str) -> Optional[Any]:
  """node 노드에서 key 키에 대응하는 값을 찾는다."""
  for char in key:
    if char in node.children:
      node = node.children[char]
    else:
      return None
  return node.value

조회를 약간 고치면 다음과 같이 활용할 수도 있다.

• 주어진 접두어로 시작하는 단어가 트라이에 있는지 확인( § 자동 완성 참조)
• 주어진 문자열의 접두사 가운데 가장 깊은 노드 찾기

삽입은 트라이의 루트부터 삽입할 문자열을 한 문자씩 따라가 트라이에 속하지 않은 경우 나머지를 새 노드로 만들어 붙이는 식으로 진행된다.

def insert(node: Node, key: str, value: Any) -> None:
    """키/값 쌍을 노드에 삽입"""
    for char in key:
        if char not in node.children:
            node.children[char] = Node()
        node = node.children[char]
    node.value = value

키 삭제는 느긋하게(키에 해당하는 노드에서 값만 지움, lazy) 할 수도 있고, 조급하게(불필요한 노드를 바로 삭제, eager) 할 수도 있다. 다음은 조급한 삭제의 코드이다.

def delete(root: Node, key: str) -> bool:
    """
    트라이의 루트 노드 root에서 key 키를 조급하게 삭제.
    """

    def _delete(node: Node, key: str, d: int) -> bool:
        """
        키[d]에 해당하는 노드를 비우고 하위 트라이가 비었으면 자식 key[d+1]를 삭제하고,
        node가 비었는지 반환
        """
        if d == len(key):
            node.value = None
        else:
            c = key[d]
            if c in node.children and _delete(node.children[c], key, d+1):
                del node.children[c]
        # Return whether the subtrie rooted at `node` is now completely empty
        return node.value is None and len(node.children) == 0

    _delete(root, key, 0)

자동 완성

주어진 접두사를 가진 키의 리스트를 반환하는데 활용할 수 있다. 접두사 검색에서 와일드 카드를 허용하는 방식으로도 수정할 수 있다.

def keys_with_prefix(root: Node, prefix: str) -> List[str]:
    results: List[str] = []
    x = _get_node(root, prefix)
    _collect(x, list(prefix), results)
    return results

def _collect(x: Optional[Node], prefix: List[str], results: List[str]) -> None:
    """
    주어진 접두사 `prefix`에 해당하는 노드 `x` 아래의 키를 `results`에 추가
    """
    if x is None:
        return
    if x.value is not None:
        prefix_str = ''.join(prefix)
        results.append(prefix_str)
    for c in x.children:
        prefix.append(c)
        _collect(x.children[c], prefix, results)
        del prefix[-1]  # delete last character

def _get_node(node: Node, key: str) -> Optional[Node]:
    """
    key 키로 노드를 탐색. 앞에서 정의한 `find` 함수와 같지만, 찾은 노드의 값 대신 노드 자체를 반환.
    """
    for char in key:
        if char in node.children:
            node = node.children[char]
        else:
            return None
    return node

정렬

키 집합으로 하위노드가 정렬된 트라이를 만들면 집합 전체를 사전순으로 정렬할 수 있다. 트라이를 전위_순회하면 사전순으로 말단을 출력할 수 있다. 이 알고리즘은 기수 정렬의 일종이다.

트라이는 폭발정렬(Burstsort)의 기본 자료구조이다. 효율적인 캐시 이용에 힘입어 2007년 기준으로는 가장 빠르다고 알려졌던 문자열 정렬 알고리즘이다. (이제는 더 빠른 것들이 있다.)

전문 검색

트라이의 특수한 형태로써 접미사 트리(suffix tree)라고 불리는 것은 빠른 전문(full-text) 검색에 활용하기 위해 모든 접미사를 색인하는데 이용할 수 있다.

구현 전략

Left-child, right-sibiling 트리로 구현된 트라이. 수직 화살표는 하위 노드 포인터, 점선 수평 화살표는 다음 노드 포인터이다. 이 트라이에 저장된 문자열 집합은 다음과 같다. {baby, bad, bank, box, dad, dance }. 사전 순으로 순회 할 수 있도록 정렬되어 있다.

트라이는 여러 가지 방법으로 표현할 수 있고 각각은 메모리 사용량과 연산 속도에서 장단점이 있다. 가장 기본적인 형태는 연결된 노드의 집합이다. 각 노드에 각각의 문자에 해당하는 하위 노드 포인터의 배열을 담는다. (문자가 영어 알파벳이면 26개가, 모든 바이트라면 256개가 되겠다) 이 방법은 간단하지만 메모리 낭비가 심하다. 매 노드마다 알파벳 256개의 노드를 4바이트 포인터로 저장하면 각 노드는 1킬로바이트를 소비한다. 만일 접두사가 거의 겹치지 않는다면, 노드는 저장된 문자열의 길이에 근사하게 필요해진다.^:341 다른 표현으로는 트리는 바닥에 가까워질수록 하위 노드가 줄어드는 경향이 있기 때문에, 대부분 널 포인터를 저장하느라 공간을 낭비하게 된다.

공간 효율 문제는 문자 축소(alphabet reduction)라 불리는 구현 기법으로 완화할 수 있다. 이 기법은 문자열을 원래의 문자보다 더 짧은 문자로 구성된 더 긴 문자열로 간주한다. 이를테면 n 바이트의 문자열은 2n 개의 4 비트 단위로 볼 수 있 의 문자열로 간주 될 수 있으며, 이 경우 트라이는 노드 당 16개의 포인터를 요구한다. 최악의 경우 조회에 필요한 노드 방문은 두 배로 늘어나지만 사용하는 공간은 8배 감소한다. ^:347–352

다른 구현에서는 노드를 3중짝 (symbol, child, next)으로 나타낸다. 노드의 자식을 단일 연결 리스트로 잇는다. 3중짝에서 child는 첫 번째 하위노드를, next는 상위 노드의 다음 하위 노드를 가리킨다. 하위 노드 집합은 이진 탐색 트리로 나타낼 수도 있다. Bentley와 Sedgewick이 개발한 삼항 탐색 트리가 하나의 사례이다. ^:353

ASCII 기준 256개의 포인터 배열 사용을 회피하는 또 다른 대안은 문자 배열을 ASCII 문자를 나타내는 256비트짜리 비트맵으로 저장해 노드 크기를 크게 줄이는 것이다.

비트 트라이

비트 트라이는 개별 비트가 하나의 문자를 구성하여 이진 트리의 일종이 된다는 점만 빼면 문자 트라이와 매우 비슷하다. 일반적으로 구현은 고정길이에서 첫 번째 1 비트를 찾는 특수한 CPU 명령(예 : GCC에서 __builtin_clz() intrinsic)을 이용한다. 이 값으로 그 앞의 0의 수를 얻어 비트 트라이에서 첫 항목을 가리키는 32 항목 또는 64 항목으로 구성된 테이블을 색인할 수 있다. 테이블을 얻고 나면 뒤따르는 비트에 따라 순차적으로 child[0] 또는 child[1] 적절하게 선택하여 검색을 진행한다.

느릴 것처럼 들릴 수도 있지만, 이 과정은 레지스터 종속성이 없기 때문에 캐시 지역성이 매우 높고 병렬화가 가능해 요즈음의 비순차적 명령어 처리를 지원하는 CPU에서는 뛰어난 성능을 발휘한다. 예를 들어 레드-블랙 트리는 이론적 성능은 훨씬 좋지만 캐시 지역성이 떨어지고, 요즘 CPU에서 다중 파이프 라인과 TLB 지연을 유발해 CPU 속도보다는 메모리 지연의 제약을 받는다. 반면 비트 트라이는 메모리에 거의 접근하지 않으며, 약간의 접근조차 읽기 뿐이기 때문에 SMP 캐시 일관성에 부하를 유발하지 않는다. 따라서 메모리 할당기(예: dlmalloc의 최신판과 그 영향을 받은 할당기들)와 같이 빠른 삽입 및 삭제를 수행하는 코드에서 점점 더 많이 채택하는 알고리즘이 되고 있다. 조회에서 최악의 경우 필요한 단계 수는 트리에서 빈(bin)을 색인하는데 사용되는 비트 수와 동일하다.

비트 트라이라는 용어는 종종 다른 용법으로, 정수 값을 담고 이진 접두값으로 정렬할 수 있는 이진 트리를 일반적으로 가리키는 말로 쓰이기도 한다. 이런 예로는 x-fast trie가 있다.

트라이 압축

트라이를 압축하고 공통 가지를 병합하면 다음과 같은 조건에서 성능을 크게 올릴 수 있다.

• (거의) 정적인 경우. 이를테면 한 번에 대량의 자료로 생성한 후에는 키 삽입이나 삭제가 없는 경우.
• 조회만 필요한 경우.
• 노드 별로 갖는 자료가 없거나, 노드가 자료를 공유하는 경우.
• 저장된 키의 표현형의 공간 안에서 매우 희소하여 이득이 압축 비용을 상회할 수 있는 경우.

예를 들면 훨씬 더 큰 고정 열거 집합의 부분집합인 경우 등의 매우 듬성듬성한 희소 비트셋이 있을 수 있다. 이 경우 트라이의 키는 전체 집합 안에서 1인 비트의 위치로 정해진다. 키는 각 원소의 정수 위치를 인코드하는 데 필요한 비트열에서 생성된다. 이런 트라이는 많은 가지가 제거된 형태를 갖는다. 공통 패턴 반복을 감지하거나 빈 공백을 채우고 나면 고유한 단말 노드(비트열)를 손쉽게 압축하여 저장하여 트라이의 전체 크기를 줄일 수 있다.

유니코드 문자 속성 검색에 쓰이는 빠른 순람표 구현에도 압축이 사용된다. 여기에는 대소문자표(예: 그리스 문자 Π에서 π로), 정규화나 조합(예: 독일어, a-움라우트에서 ä)에 쓰이는 순람표 등이 포함된다. 이런 응용에서는 매우 큰 일차원 희소 테이블(예 : 유니코드 코드 포인트)을 그 조합의 다차원 행렬로 변환한 다음 고차 행렬의 좌표를 압축되지 않은 트라이의 문자열 키로 사용해 표현하는 것과 유사하다. /*그러면 키의 마지막 차원을 압축하기 위해 고차행렬 내에서 공통 열을 찾아 병합하는 것으로 압축이 구성될 것이다.*/ 예를 들어, 행렬에서 열을 구성하는 전체 멀티 바이트 유니코드 코드포인트를 저장하는 것을 피하려면, 비슷한 코드포인트를 묶어서 다룰 수 있다. 고차 행렬의 각 차원은 다음 차원의 시작 위치를 저장하므로 오프셋(일반적으로 단일 바이트)만 저장하면 충분하다. 결과 벡터가 희소 벡터이면 그 자체로 압축할 수 있으므로, (트라이의 각 층과 연관된) 각 차원은 따로 따로 압축할 수 있다.

일부 구현은 동적 희소 트라이에서도 압축을 지원하지만, 압축된 세그먼트를 분할하거나 병합해야하는 경우 보통 상당한 비용을 수반한다. 압축과 갱신 속도는 일정량 상호 교환할 수 있다.

이러한 압축의 결과는 트라이를 유향 비순환 그래프(DAG)로 변환하려고 한 것처럼 보일 수 있다. DAG에서 트라이로의 역변환은 자명하고 항상 가능하기 때문이다. 그러나 DAG의 모양은 노드 색인에 쓸 키의 형식에 따라 결정되어, 결과적으로 압축이 제한된다.

다른 압축 전략으로는 자료 구조를 단일 바이트 배열로 풀어헤칠 수도 있다. 이 방법으로는 노드 포인터가 필요 없어지기 때문에 메모리 사용량이 크게 줄어 든다. 그러면 디스크에서 자료를 효율적으로 읽어오기 위해 메모리 매핑과 가상 메모리를 사용할 수 있게 된다.

또 다른 접근은 트라이를 pack하는 것이다. Liang은 자동 하이픈 연결에 적용된 각 노드의 자손이 메모리 인터리브될 수 있는 희소 pack된 트라이를 설명한다.

외부 기억장치 트라이

접미사 트리를 포함해 외부 기억 장치에 문자열 집합을 저장하는 데 적합한 변형 트라이가 몇 가지 있다. B-트라이라는 변종도 이 가운데 하나인데, B 트리와의 조합이다. 접미사 트리에 비해 제한된 연산만 가능하지만, 대신 더 작고 갱신 연산도 빠르다.

외부 링크

• NIST 알고리즘 및 자료 구조 사전: 트라이 (영어)