[자료구조] 접두사에 강한 트라이(Trie)

코테 공부를 하다가 접두사 관련 시간 초과가 계속 나서 문제를 찾아보다가 Trie자료구조를 알게되었다. 일반 검색할때 자동완성에 이러한 자료 구조가 쓰여졌다는 것이 흥미로웠다. 그래서 ChatGPT에 물어보았다.

---

ChatGPT 답변

Trie 자료구조는 문자열이나 텍스트 데이터를 효율적으로 저장하고 검색하는 데 사용되는 트리 기반 자료구조입니다. 주로 접두사와 관련된 문제를 해결하는 데 유리한 특징을 가지고 있습니다. 예를 들어, 많은 단어들에서 같은 접두사가 있을 때, 그 부분을 공유하여 공간을 절약하고 빠르게 검색할 수 있습니다.

Trie의 구조

Trie는 각 노드가 문자를 가지고 있으며, 루트에서부터 자식 노드를 따라가면서 하나의 문자열을 구성합니다. 이때, 각 노드는 해당 문자가 접두사가 되는 위치에 있습니다. 루트는 공백으로 시작하고, 자식 노드로 한 글자씩 연결되며, 각 문자열은 트리의 경로에 따라 형성됩니다.

간단한 예:

다음의 단어들이 있다고 가정합시다: cat, can, dog, dot.

1. cat을 삽입하면 루트에서 c -> a -> t 노드로 이어집니다.
2. can을 삽입하면 기존의 ca까지는 동일하므로, n 노드만 추가됩니다.
3. dog는 d -> o -> g가 새로운 경로로 만들어집니다.
4. dot은 do까지는 동일하므로, t 노드만 추가됩니다.

Trie는 이렇게 중복되는 접두사를 공유하여 공간을 절약하며, 단어를 트리 구조로 저장합니다.

Trie 자료 구조 예시

    (root)  
    /   \\  
  c       d  
 / \\      \\  
a   a       o  
/    \\      \\  
t      r      g

Trie의 장점

1. 빠른 검색: Trie를 사용하면 특정 문자열의 존재 여부나 특정 접두사로 시작하는 문자열을 빠르게 검색할 수 있습니다. 문자열의 길이에 비례하는 시간복잡도를 가집니다.
2. 효율적인 메모리 사용: 같은 접두사를 가진 단어들이 많은 경우, 접두사 부분을 공유함으로써 메모리 사용을 절약할 수 있습니다.
3. 자동 완성 기능: Trie는 접두사 검색에 특화되어 있어, 자동 완성 기능이나 추천 시스템에 유리합니다. 특정 접두사로 시작하는 모든 단어를 쉽게 찾을 수 있기 때문입니다.
4. 사전 구현에 적합: 문자열이 많은 사전과 같은 구조를 구현할 때 매우 유용합니다. 예를 들어, 사전에서 단어 검색 또는 특정 패턴에 맞는 단어 검색을 빠르게 수행할 수 있습니다.

Trie의 단점

1. 많은 메모리 사용: 중복되는 접두사가 많은 경우에는 메모리 절약이 가능하지만, 그렇지 않을 경우 메모리 사용량이 커질 수 있습니다. 특히 알파벳이나 문자 세트가 큰 경우, 각 노드마다 많은 자식 노드를 가질 수 있기 때문에 메모리 낭비가 발생할 수 있습니다.
2. 구현 복잡성: Trie는 다른 자료구조에 비해 구현이 비교적 복잡할 수 있으며, 특히 문자열 삭제 같은 연산을 구현할 때 주의가 필요합니다.

Trie의 활용 사례

1. 자동 완성 및 검색: 웹 브라우저의 주소창이나 검색 엔진에서 자동 완성 기능을 구현할 때 Trie가 자주 사용됩니다. 사용자가 입력한 부분적인 단어나 접두사에 해당하는 결과를 빠르게 제공할 수 있습니다.
2. 사전(dictionary) 검색: 영어 단어 사전이나 단어 게임에서 Trie를 사용하여 빠르게 단어를 검색할 수 있습니다. 예를 들어, Scrabble 게임에서 특정 패턴에 맞는 단어를 빠르게 찾는 데 유용합니다.
3. IP 주소 라우팅: 네트워크에서 IP 주소를 관리하고 라우팅하는 데도 Trie가 사용될 수 있습니다. IP 주소도 일종의 문자열로 처리할 수 있기 때문입니다.
4. 데이터 압축: 접두사를 공유하는 특성을 활용하여 중복된 데이터를 줄이고 효율적으로 압축하는 알고리즘에 사용됩니다. 대표적으로 Radix Trie라는 변형이 있습니다.

정리

Trie는 특히 문자열 처리에서 강력한 도구로, 빠른 검색과 접두사 기반 검색 기능을 제공합니다. 자동 완성, 사전, 패턴 검색 등에 적합하며, 상황에 맞게 메모리 사용량과 구현의 복잡성을 고려해 사용하면 좋습니다.

---

Trie 자료 구조를 코드로 한번 구현 해보았다.

class TrieNode:
    def __init__(self):
        # 각 노드는 자식 노드와 끝나는 단어 여부를 저장
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        # Trie는 루트 노드를 가지고 시작
        # root 노드는 아무 값도 넣지 않는다.
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        # 단어 삽입
        node = self.root
        for char in word:
            # 현재 노드의 자식 노드 중에 문자가 없으면 새로 생성
            # node children 딕셔너리에 char가 없으면 TrieNode를 새로 만든다. 있다면 node를 움직인다.
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        # 단어의 마지막에 도달하면 단어가 끝남을 표시
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        # 단어 검색
        node = self.root
        for char in word:
            # node children 딕셔너리에 char가 없으면 return False 있다면 node를 움직인다.
            if char not in node.children:
                return False
            node = node.children[char]
        # 마지막 문자가 단어의 끝이면 True 반환
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        # 특정 접두사로 시작하는지 확인
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

사용 예시

trie = Trie()

# 단어 삽입
trie.insert("apple")
trie.insert("app")

# 단어 검색
print(trie.search("apple"))  # True
print(trie.search("app"))    # True
print(trie.search("appl"))   # False

# 접두사 검색
print(trie.starts_with("app"))  # True
print(trie.starts_with("apl"))  # False

 

insert("apple"): "apple" 단어를 삽입하면서 각 문자마다 노드를 생성하거나 이동하고, 마지막 노드에서 is_end_of_word를 True로 설정합니다.
search("apple"): "apple"이 Trie에 있는지 확인하고, 마지막 노드가 is_end_of_word라면 True를 반환합니다.
starts_with("app"): "app"으로 시작하는 단어가 있는지 확인하고, 그 접두사를 Trie에서 찾을 수 있으면 True를 반환합니다.