[CS기초] 트라이(Trie)

트라이(Trie) 자료구조

트라이는 문자열을 효율적으로 처리하기 위해 고안된 트리 형태의 자료구조입니다.

 

트라이의 특징

장점

• 단어 S를 삽입(insert), 탐색(search), 삭제(erase)할 때 시간복잡도가 이론적으로 O(len(S))로, 문자열 길이에 비례하여 연산 시간이 결정된다.
  • 이는 문자 하나당 처리 시간이 이론적으로 O(1)이라는 점에서 효율적이다.

단점

• 메모리를 매우 많이 사용한다.
  • 일반 배열로 문자열을 저장하는 방법에 비해 최대 4 x (문자 종류 수)배의 메모리를 더 사용합니다.
  • 예를 들어 각 단어가 알파벳 대문자로만 구성되었을 때는 최대 104배 정도의 추가 메모리를 사용하게 됩니다.
• 실제 구현에서는 해시(Hash), 이진 탐색 트리(Binary Search Tree)에 비해 연산이 느린 편이다.
  • 개별적인 문자 연산 자체는 빠르지만, 트라이에서 정점 이동이 매우 큰 배열을 따라 이루어지기 때문에 CPU 캐시(cache) 적중률이 낮아 실제 성능이 떨어지게 됩니다.

 

트라이의 활용 예시

트라이는 시간이나 공간 복잡도 면에서 큰 장점이 없어 보이지만, 특정 문제에서는 매우 효율적으로 사용될 수 있습니다.

• 접두사(prefix) 판별
• 자동 완성(auto-completion)
• 추천 검색

 

트라이의 주요 연산

트라이의 연산에는 크게 삽입(insert), 탐색(fetch), 삭제(erase)가 있습니다.

• 삽입(insert): 트라이에 문자열을 추가한다.
  • 각 문자에 대해 정점이 존재하지 않는 경우 새롭게 추가해 가며 단어 끝으로 이동한다.
  • 단어의 끝에 '단어 표시'를 추가해 해당 단어가 트라이에 존재함을 명시한다.
• 탐색(fetch): 문자열이 존재하는지 확인한다.
  • 단어 끝에 '단어 표시'를 반드시 해줘야 정확한 탐색이 가능하다.
  • 특정 단어의 경로가 존재하지만 끝에 '단어 표시'가 없다면, 해당 단어는 존재하지 않는 것으로 간주한다.
• 삭제(erase): 특정 단어의 끝에 있는 '단어 표시'를 지운다.
  • 트라이 구조 유지를 위해 정점(node)은 삭제하지 않고 남겨둔다.
  • 이로 인해 삽입과 삭제가 자주 반복되는 환경에서는 사용되지 않는 정점들이 쌓여 메모리 낭비가 심해질 수 있다.

 

파이썬에서 트라이의 구현

# 알파벳 대문자를 처리하는 트라이 구현
# 각 문자의 idx: ord('S') - 65
ROOT = 1
unused = 2
MX = 10000 * 500 + 5
chk = [False] * MX
nxt = [[-1] * 26 for _ in range(MX)]

# 문자→인덱스 변환 함수
def c2i(c):
    return ord(c) - 65

# insert: 문자열 추가 함수
def insert(s):
    global unused
    cur = ROOT
    for c in s:
        # 자식 정점이 없는 경우 새롭게 추가
        if nxt[cur][c2i(c)] == -1:
            nxt[cur][c2i(c)] = unused
            unused += 1
        # 자식 정점으로 이동
        cur = nxt[cur][c2i(c)]
    # 문자열 끝에 도달했다면 단어 표시
    chk[cur] = True

# erase: 문자열 삭제 함수
def erase(s):
    cur = ROOT
    for c in s:
        # 없는 단어를 지우려고 할 경우 return
        if nxt[cur][c2i(c)] == -1:
            return
        cur = nxt[cur][c2i(c)]
    # 해당 단어의 단어 표시 해제
    chk[cur] = False

# find: 문자열 탐색 함수
def find(s):
    cur = ROOT
    for c in s:
        # 탐색할 단어가 없는 단어인 경우 return
        if nxt[cur][c2i(c)] == -1:
            return False
        cur = nxt[cur][c2i(c)]
    # 해당 단어 표시 여부에 따라 존재 여부 반환
    return chk[cur]