[자료구조] 트라이[Trie]

문자열 탐색 알고리즘에 대해 알아보자.

 

트라이는 입력된 문자열을 트리 형식으로 만든 자료구조이다.

트라이를 이용하면 효율적 탐색이 가능하다.

 

만약 최대 N개의 문자열이 주어지고, 각 문자열은 최대 M의 길이를 갖는다고 해보자.

이때 특정 문자열의 개수를 구한다면 얼마나 걸릴까?

 

먼저 모든 문자열을 삽입하고, 특정 문자열과 동일한 문자열을 찾아야 한다.

 

1. 단순한 방법

모든 문자열을 삽입하는 시간복잡도는 O(N * M)이다.

특정 문자열을 탐색하는 시간복잡도는 O(N * M)이다.

 

2. 트라이 이용

모든 문자열을 삽입하는 시간 복잡도는 O(N * M)이다.

특정 문자열을 탐색하는 시간복잡도는 O(M)이다.

 

 

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data is not None:
            return True
        
        else:
            return False

 

 

트라이의 삽입, 탐색의 알고리즘을 위와 같다.

 

먼저, Node 클래스를 보자.

트라이의 루트를 하나 잡아주고 초기화한 것이다. 최초 노드는 비어있는 딕셔너리이다.

 

 

 

다음으로 Trie 클래스의 insert 함수를 보자. 

'ant'라는 문자열이 들어왔다면 'a', 'n', 't'로 한 글자씩 따져본다.

 

현재 글자가 현재 노드의 children과 같다면, children이 현재 노드가 되어 다음 글자로 넘어간다.

 

만약 현재 글자가 현재 노드의 children과 같지 않다면, 현재 노드의 children으로 현재 글자를 지정한다. (현재 글자의 Node를 만들어서 children으로 넣는다.)

그리고 다음 글자로 넘어간다.

 

문자열이 끝났음도 알려줘야 한다. 마지막 글자 't'의 data에 'ant' (전체 문자열)를 넣어주면 된다. 

 

 

 

마지막으로 Trie 클래스의 search 함수를 보자.

True를 출력하려면 insert 함수에서 했던 것처럼, 입력받은 글자가 children으로 이어지는지 확인해야 한다.

주의할 점은 입력받은 글자의 마지막 data가 None이 아니어야 한다.

'ant'가 트라이에 있는 상황에서 입력받은 글자가 'an'이라면, 'an'은 겹치지만 'n'의 데이터가 None이기 때문에 트라이에는 없는 문자열이다. 따라서 Fasle를 return한다.

 

현재 글자가 현재 노드의 children과 같지 않을 때 Fasle를 return한다.

 

 

 

ant, anti, bag 이라는 문자열을 예로 들면, 아래 그림처럼 그려진다.

 

 

 

 

 

 

위 내용은 이 블로그에서 참고했습니다.