[파이썬] 트라이 (Tries)의 구조와 문자열 검색

01 Sep 2023

python

트라이 (Tries)는 문자열을 저장하고 검색하기 위한 효율적인 자료구조입니다. 이 자료구조는 문자열의 길이에 따라 빠르게 검색이 가능하며, 문자열을 효율적으로 저장하기 위해 메모리를 사용합니다.

트라이의 구조

트라이는 트리형태의 구조를 가지며, 각 노드는 하나의 문자를 나타냅니다. 루트노드부터 시작하여 자식 노드를 따라 내려감으로써 문자열을 표현합니다. 각 노드는 여러 개의 자식을 가질 수 있으며, 문자열의 종료를 표시하기 위한 특별한 종료 노드도 존재합니다.

예를 들어, 다음과 같은 단어들을 트라이에 저장한다고 가정해봅시다:

“apple”
“banana”
“orange”

이 경우 트라이는 다음과 같이 구성됩니다:

root
  ├ a
  │   └ p
  │       └ p
  │           └ l
  │               └ e (단어 종료)
  ├ b
  │   └ a
  │       └ n
  │           └ a
  │               └ n
  │                   └ a (단어 종료)
  └ o
      └ r
          └ a
              └ n
                  └ g
                      └ e (단어 종료)

문자열 검색

트라이는 문자열을 효율적으로 검색하기 위한 자료구조입니다. 문자열 검색은 루트 노드부터 시작하여 문자열의 각 문자를 따라 내려가며 검색을 수행합니다.

예를 들어, “banana”라는 문자열을 트라이에서 검색한다고 가정해봅시다. 검색 과정은 다음과 같습니다:

루트 노드에서 ‘b’를 찾아 자식 노드로 이동합니다.
‘b’의 자식 노드에서 ‘a’를 찾아 자식 노드로 이동합니다.
‘a’의 자식 노드에서 ‘n’을 찾아 자식 노드로 이동합니다.
‘n’의 자식 노드에서 ‘a’를 찾아 자식 노드로 이동합니다.
‘a’의 자식 노드에서 ‘n’을 찾아 자식 노드로 이동합니다.
‘n’의 자식 노드에서 ‘a’를 찾습니다. 이 노드는 단어 종료 노드이므로 “banana”를 찾았다고 판단합니다.

문자열 검색은 트라이 구조를 이용하여 빠르게 수행될 수 있습니다. 시간 복잡도는 문자열의 길이에 비례합니다.

파이썬에서의 트라이 구현

파이썬에서는 트라이를 구현하기 위해 일반적으로 클래스를 사용합니다. 각 노드는 딕셔너리를 이용하여 자식 노드를 저장하며, 문자열의 종료를 나타내기 위한 특별한 키를 사용합니다.

다음은 간단한 트라이 클래스의 예시입니다:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

위의 예시에서 insert 메서드는 트라이에 단어를 삽입하고, search 메서드는 단어의 존재 여부를 확인합니다. 이를 통해 트라이를 사용하여 문자열 검색을 수행할 수 있습니다.

정리

트라이는 문자열의 저장과 검색에 효율적인 자료구조입니다. 문자열의 길이에 따라 검색 속도가 빠르며, 트라이를 구현하여 파이썬에서 문자열 검색을 수행할 수 있습니다. 이를 통해 복잡한 문자열 처리 작업을 간편하게 처리할 수 있습니다.