[자료구조] Trie in Python

파이썬으로 구현하는 Trie.

 

출처 - https://www.youtube.com/watch?v=o6563NNbdtg 

 

Trie의 필요성

어떠한 사전이 내가 찾는 문자열을 담고 있는 지 알아본다고 하자.

 

사전이 담고 있는 문자열들 - "leets", "leeds", "leet"

내가 찾고자 하는 문자열 - "leet"

 

사전을 구성하는 방법엔 여러 가지가 있을 것이다.

예를 들어, hash table을 사용해, 각 문자열을 해싱해 얻은 키 값에 True 값을 지정해주면

Key	Value
leets	True
leeds	True
leet	True

와 같이 될 것이고,

내가 찾는 문자열 leet이 사전에 있는가는

 

if "leet" in hashTable and hashTable["leet"]

의 Value가 True인 지 확인하여 알 수 있을 것이다.

 

이렇게 Hash Table로 구성하면 인덱스로 바로 탐색이 가능해, 탐색의 시간 복잡도는 O(1)인 반면,

각 문자열의 정보를 모두 담아야 하는 테이블을 새로 만들어야 하므로 공간 복잡도는 O(단어들의 문자수의 합)이 될 것이다.

 

이 때, 문자열 탐색은 비교적 빠르면서, Hash Table보다 공간복잡도 면에서도 더 효율적인 자료구조가

Trie겠다.

 

Trie란?

탐색 트리의 일종이며, 주로 문자열이 키인 경우가 많다.
문자열의 각 문자를 노드로 가지며,
리프 노드로는 각 문자열의 끝을 의미하는 접미사('prefix')를 넣어준다.
- 위키피디아

 

예시로

(출처 - https://velog.io/@dksgyals1/%ED%8A%B8%EB%9D%BC%EC%9D%B4Trie-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)

 

를 봐보도록 하자!

 

이렇게 루트 노드는 공백이나 의미 없는 문자로 채워주고 (문자열의 시작을 의미),

각 문자를 노드로 삼아 트리 처럼 만들어주되,

리프 노드는 임의의 접미사 (Prefix)로 채워주는 (문자열의 끝을 의미)것이 Trie이다.

 

위의 Trie는 ["DOBBY", "DRACO", "DUDLEY", "HAGRID", "HARRY",  "HEDWIG", "HERMIONE", "RON",  "RONALD"]를 표현한 것을 볼 수 있다.

 

이렇게 맨 위에서 봤던

"leeds", "leets", "leet"를 Trie로 구성하여 준다면

 

이 Trie에서 루트 노드는 공백, 접미사 (Prefix)는 *로 채워줬다! 예시

 

이렇게 표현할 수 있고, 여기서

"leet" 탐색: l -> e -> e -> t -> * 로 탐색이 가능해 True를 반환하지만,

"lee" 탐색: l -> e -> e 후에 자식 노드 중 *가 없기 때문에 False를 반환할 것이다.

 

 

이러한 Trie구조를 파이썬 언어로 구현하면

다음과 같다.

 

파이썬 구현

class Trie:
    head = {} # Trie를 딕셔너리로 구현. 
    # key값은 노드의 값, value값은 그 노드의 자식 노드들의 값
    
    def add(self, word):
        cur = self.head # 포인터cur
        
        for ch in word:
            # 지금 보고 있는 글자가, 지금 포인터가 가리키는 
            # key값(글자)의 value 값들(자식 노드들)에 있지 않으면
            if ch not in cur: 
            	cur[ch] = {} # head안에 노드를 생성
            cur = cur[ch] # 현재 포인터 위치 변경 - 현재 보고 있는 노드로
            cur['*'] = True # 자식 노드의 모음에 '*' 또한  추가
            
    def search(self, word):
    	cur = self.head # 루트 노드부터 탐색 시작
        
        for ch in word:
            if ch not in cur: # 현재 보고 있는 노드의 자식 노드들에 없으면
                return False
            cur = cur[ch]
        if '*' in cur:
            return True # '*'까지 자식 노드 중에 있으면, 단어 자체가 Trie안에 있다는 말
        return False
            

 

위의 연산들의 시간 및 공간 복잡도는 아래와 같다.

 

삽입

시간 복잡도 - O(문자열 길이)

공간 복잡도 - O(문자열 길이) - 이미 있는 문자열들과 아무 접미사도 공통되지 않을 때 

 

탐색

시간 복잡도 - O(문자열 길이)

공간 복잡도 - O(1) - 이미 구성된 트라이 이용

 

접미사 탐색

시간 복잡도 - O(문자열 길이)

공간 복잡도 -O(1)

 

 

 

이렇게 본 Trie는 Hash Table 등과 같은 다른 자료 구조에 비해

1) 공통된 접미사로 시작하는 문자열 모두 찾기

2) 사전 순서로 문자열들 나열하기

의 연산도 훨씬 쉽게 수행가능케함을 알 수도 있다.

 

Trie의 활용

리트코드에서는 Trie가 효율적인 자료구조인만큼, 여러 곳에 많이 쓰인다는 것을 보여주고 있다.

 

1. 자동 완성

출처 - leetcode

 

2. 맞춤법 검사

Trie와 일종의 확률적 계산 (한+ 글자를 추가, 삭제, 수정했을 때 문자열이 매치될 확률 등)을 통해 구현

 

 

3. IP 라우팅 - Longest Prefix Match

라우터에서 packet을 forwarding해 줄 때, 다음 라우터(또는 호스트)로의 경로를 결정하기 위해, 패킷의 목적지 주소와 라우팅 테이블의 각 엔트리에 있는 prefix와 비교를 수행게 됩니다. 즉, 라우팅엔트리의 prefix mask(255.255.255.0 또는 길이로 24)를 목적지 주소에 masking 한 후, prefix와 비교를 하게 됩니다. 이때, 가장 많이 매칭되는 엔트리를 선택한다

- 출처: https://www.netmanias.com/ko/post/qna/4306

 

출처 - leetcode