♧ Self-study/<누구나 자료구조와 알고리즘>

Chapter 17. 트라이(trie)해 보는 것도 나쁘지 않다

Grit_0913 2024. 9. 20. 19:55

Chapter 17. 트라이(trie)해 보는 것도 나쁘지 않다

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 트라이 노드
2. 단어 저장
3. 트라이 검색
       3-1. 트라이 검색의 효율성
4. 트라이 삽입
5. 자동 완성 개발
       5-1. 단어 수집
       5-2. 자동 완성 마무리
6. 연습 문제 정리
  • 트라이(tire)는 자동 완성과 자동 수정 등의 기능을 구현할 때 사용하기 좋다.
  • 트라이의 어원은 retrieval 이다. 따라서 '트리'라고 발음하는 것이 맞다. 그러나 기존의 트리 자료 구조와 차이를 두기 위해 트라이라 칭한다.
  • 트라이는 교재마다 설명이 조금씩 상이할 수 있다. 그러나 기본적인 개념은 동일하다.

1. 트라이 노드

  • 트라이 또한 노드를 기반으로한 자료 구조 이다.
  • 트라이는 자식 노드의 개수에 제한이 없다. (반면 이진 트리는 최대 두 개의 자식 노드를 갖는다).
  • 교재에서 트라이가 갖는 노드의 특징은 다음과 같다.
    • 각 노드는 해시 테이블이다.
    • 해시 테이블의 키는 알파벳(문자열의 각 문자)이다.
    • 해시 테이블의 값은 트라이의 자식 노드이다.
      • { "알파벳" : 자식 노드 }
  • 코드 구현
# 트라이 노드 구현-----------------------------------------------------------
class TrieNode:
    
    def __init__(self):
        # 자식 노드는 해시 테이블만 포함한다.
        self.children = {}
        
# 루트 노드를 추적하는 Trie 클래스--------------------------------------------
class Trie:
    def __init__(self):
        self.root = TrieNode()
# 코드 테스트
# TrieNode 객체 생성
tri = TrieNode()

# "a", "b", "c" 값을 하드코딩으로 추가
# 각 객체에 클래스를 할당하여 인스턴스 생성
tri.children["a"] = TrieNode()  # "a"라는 자식 노드를 추가
tri.children["b"] = TrieNode()  # "b"라는 자식 노드를 추가
tri.children["c"] = TrieNode()  # "c"라는 자식 노드를 추가

# 출력
tri.children

2. 단어 저장

  • 트라이를 통해 단어를 저장한다.
    • step 1 : 개별 단어의 알파벳이 각 노드(해시 테이블)의 키가 된다.
    • step 2 : 주어진 알파벳을 따라 트라이의 노드를 찾아 들어간다.
    • step 3 : 키가 * 인 노드를 찾으면 해당 노드가 끝 지점이 된다. 즉, 단어를 찾은 것이다.
      • * 를 마침표로 여기면 이해하기 쉽다.
      • 단, 단어가 존재하지 않는 경우, 즉 찾는 알파벳이 없다면 해당 노드에 알파벳을 키로 추가한다.
        • 이 경우 하나의 노드(해시 테이블) 내에 두 개(이상)의 키가 존재한다.
  • 별표(asterisk)는 특정 단어가 완성되었음을 알려준다. 앞서 언급한 것과 같이 마침표와 동일한 역할이다.
    • 단, 해당 노드에 별표와 다른 알파벳이 있다면 다음을 의미한다.
      • 우선 하나의 단어는 완성되었다.
      • 계속해서 노드를 따라가면 다른 단어를 완성할 수 있다. (즉 접두사로 쓸 수 있다).
        • e.g. bat에서 단어가 완성되지만 계속 노드를 따라가 batter를 완성할 수 있다.

3. 트라이 검색

  • 트라이 검색의 목적은 크게 두 가지이다. (교재에서는 접두사인 경우의 코드만 다룬다. 접두사인 코드는 단어도 찾을 수 있기 때문이다).
    • 완전한 단어진이 확인한다.
    • 문자열이 어떤 단어의 접두사인지 확인한다.
  • 검색 수행 (접두사)
    • step 1 : currentNode라는 변수를 생성한다.
      • 알고리즘 시작 시 currentNode는 루트 노드가 된다.
    • step 2 : 검색 문자열의 각 문자를 순회한다.
    • step 3 : step 2에서 순회를 하며 currentNode의 자식 노드 중 일치하는 알파벳이 있는지 확인한다.
      • 자식이 없는 경우
        • 문자열이 트라이에 없는 것이다.
        • None을 반환한다.
      • 자식이 있는 경우
        • currentNode를 자식 노드로 업데이트 한다.
        • 'step 1 ~ step 3'의 과정을 반복하여 트라이의 깊은 레벨까지 트리클링한다.
    • step 4 : 검색 문자열을 끝까지 순회했다면 검색 문자열을 찾은 것이다.
  • 코드 구현
# 트라이 노드 구현-----------------------------------------------------------
class TrieNode:
    
    def __init__(self):
        # 자식 노드는 해시 테이블만 포함한다.
        self.children = {}
        
# 루트 노드를 추적하는 Trie 클래스--------------------------------------------
class Trie:
    def __init__(self):
        self.root = TrieNode()    
        
# 트라이 검색----------------------------------------------------------------
    def search(self, word):
    cyrrentNode = self.root
    
    for char in word:
        # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
        if currentNode.children.get(char):
            # 자식 노드를 따라간다.
            # 'self.children = {}' 구조로 자식 노드의
            # 해시 테이블을 초기화한다. (self 자리에 currentNode 사용).
            currentNode = currentNode.children[char]
        else:
            # 현재 노드의 자식 중에 현재 문자가 없으면
            # 검색하려는 단어가 트라이에 없는 것이다.
            return None
        
        # 자동 완성 기능을 지원하기 위해
        # currentNode를 반환한다.
        return currentNode

 

 

3-1. 트라이 검색의 효율성

  • 검색 알고리즘은 두 가지 영역으로 분류된다.
    • 주어진 문자열을 하나씩 순회한다.
    • 하나의 문자열은 자식 노드(해시 테이블)에 키로 접근한다. 
  • 트라이 검색의 시간 복잡도는 $O(K)$로 표기한다. ($K$ = 검색 문자열 내 문자들의 수).
    • 문자열 수만큼 순회를 하기에 $O(N)$으로 생각할 수 있다. 그러나 일반적으로 $N$은 자료 구조 내의 데이터 양을 의미한다. 따라서 트라이에서 $N$은 문자들의 수가 아니라 트라이 내의 '노드의 수'가 된다.
  • 트라이 자체의 시간 복잡도는 수많은 노드들로 인하여 비효율적이다. 
    • 그러나 트라이에서 문자열을 검색하는 것은 노드(해시 테이블)을 이용하기에 효율적이다.
  • 선형 검색도 모든 문자열을 순회한다는 점에서 시간 복잡도는 동일하다.
    • 그러나 트라이는 공통 접두사 처리, 자동 완성, 그리고 메모리 효율성 등 자료 구조와 알고리즘 적으로 더 많은 이점을 갖는다.

4. 트라이 삽입

  • 삽입 수행
    • step 1 : currentNode라는 변수를 생성한다.
      • 알고리즘 시작 시 currentNode는 루트 노드가 된다.
    • step 2 : 검색 문자열의 각 문자를 순회한다.
    • step 3 : step 2에서 순회를 하며 해당 문자를 키로 하는 자식 노드가 있는지 확인한다.
      • 자식 노드가 없는 경우
        • inner step 1 : 자식 노드를 생성한다.
        • inner step 2 : currentNode를 생성된 자식 노드로 업데이트 한다.
        • inner step 3 : step 2로 돌아가 남은 문자들의 순회를 계속한다.
      • 자식 노드가 있는 경우
        • currentNode를 자식 노드로 업데이트하고, 다시 step 2로 돌아가 남은 문자들의 순회를 계속한다.
  • 코드 구현
# 트라이 노드 구현-----------------------------------------------------------
class TrieNode:
    
    def __init__(self):
        # 자식 노드는 해시 테이블만 포함한다.
        self.children = {}
        
# 루트 노드를 추적하는 Trie 클래스--------------------------------------------
class Trie:
    def __init__(self):
        self.root = TrieNode()    
        
# 트라이 검색----------------------------------------------------------------
    def search(self, word):
    cyrrentNode = self.root
    
    for char in word:
        # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
        if currentNode.children.get(char):
            # 자식 노드를 따라간다.
            # 'self.children = {}' 구조로 자식 노드의
            # 해시 테이블을 초기화한다. (self 자리에 currentNode 사용).
            currentNode = currentNode.children[char]
        else:
            # 현재 노드의 자식 중에 현재 문자가 없으면
            # 검색하려는 단어가 트라이에 없는 것이다.
            return None
        
        # 자동 완성 기능을 지원하기 위해
        # currentNode를 반환한다.
        return currentNode

# 트라이 삽입----------------------------------------------------------------
    def insert(self, word):
        currentNode = self.root
    
        for char in word:
            # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
            if currentNode.children.get(char):
                # 자식 노드를 따라간다.
                currentNode = currentNode.children[char]
            else:
                # 현재 노드의 자식 중에 현재 문자가 없으면
                # 그 문자를 새 자식 노드로 추가한다.
                newNode = TrieNode()
                currentNode.children[char] = newNode
            
                # 새로 추가한 노드를 따라간다.
                currentNode = newNode
    
        # 단어 전체를 트라이에 삽입했으면 
        # 마지막으로 *를 추가한다.
        # "*" key에 None을 value로 저장.
        currentNode.children["*"] = None

5. 자동 완성 개발

5-1. 단어 수집

  • 트라이 내의 모든 단어를 배열로 변환하는 메서드를 작성한다.
    • 트라이의 모든 노드를 인수로 받아 해당 노드로부터 시작되는 모든 단어를 나열할 수 있도록하기 위함이다. (즉, 자동 완성구현을 위함).
  • 코드 구현
    • 재귀 수행에 관해서는 p394에서 자세히 확인할 수 있다.
      • 특히 words를 입력할 때 배열은 값을 새로 추가해도 개별적으로 객체가 존재한다.
      • e.g. "ca"에 "n"이 추가되면 "can"과 "ca"가 모두 존재한다. ("ca"가 사라지지 않는다).
# 트라이 노드 구현-----------------------------------------------------------
class TrieNode:
    
    def __init__(self):
        # 자식 노드는 해시 테이블만 포함한다.
        self.children = {}
        
# 루트 노드를 추적하는 Trie 클래스--------------------------------------------
class Trie:
    def __init__(self):
        self.root = TrieNode()    
        
# 트라이 검색----------------------------------------------------------------
    def search(self, word):
    cyrrentNode = self.root
    
    for char in word:
        # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
        if currentNode.children.get(char):
            # 자식 노드를 따라간다.
            # 'self.children = {}' 구조로 자식 노드의
            # 해시 테이블을 초기화한다. (self 자리에 currentNode 사용).
            currentNode = currentNode.children[char]
        else:
            # 현재 노드의 자식 중에 현재 문자가 없으면
            # 검색하려는 단어가 트라이에 없는 것이다.
            return None
        
        # 자동 완성 기능을 지원하기 위해
        # currentNode를 반환한다.
        return currentNode

# 트라이 삽입----------------------------------------------------------------
    def insert(self, word):
        currentNode = self.root
    
        for char in word:
            # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
            if currentNode.children.get(char):
                # 자식 노드를 따라간다.
                currentNode = currentNode.children[char]
            else:
                # 현재 노드의 자식 중에 현재 문자가 없으면
                # 그 문자를 새 자식 노드로 추가한다.
                newNode = TrieNode()
                currentNode.children[char] = newNode
            
                # 새로 추가한 노드를 따라간다.
                currentNode = newNode
    
        # 단어 전체를 트라이에 삽입했으면 
        # 마지막으로 *를 추가한다.
        # "*" key에 None을 value로 저장.
        currentNode.children["*"] = None

# 모든 단어를 배열로 만드는 메서드--------------------------------------------
    def collectAllWords(self, node=None, word="", words=[]):
    # 메서드는 인수 세 개를 받는다.
    # 첫 번째 인수인 node는 그 자손들에게서 단어를 수집할 노드이다.
    # 두 번째 인수인 word는 빈 문자열로 시작하고
    # 트라이를 이동하면서 문자가 추가된다.
    # 세 번째 인수인 word는 빈 배열로 시작하고
    # 함수가 끝날 때는 트라이 내 모든 단어를 포함한다.
    
    # 현재 노드는 첫 번째 인자로 전달받은 node다.
    # 아무것도 받지 않았으면 루트 노드다.
    currentNode = node or self.root
    
    # 현재 노드의 모든 자식을 순회한다.
    for key, childNode in currentNode.children.items():
        # 현재 키가 *이면 완전한 단어 끝에 도달했다는 뜻이므로
        # 이 단어를 words 배열에 추가한다.
        if key == "*":
            words.append(word)
        else: # 아직 단어 중간이면
            # 그 자식 노드에 대해 이 함수를 재귀적으로 호출한다.
            # word + key는 재귀적으로 호출되며 단어가 완성된다.
            # word + key로 완성된 단어를 바로 위의 words에 넣는 것이다.
            self.collectAllWords(childNode, word + key, words)
            
    return words

 

 

5-2. 자동 완성 마무리

  • 자동 완성 수행
    • step 1 : 사용자가 입력하기 시작하는 문자열인 prefix를 인자로 받는다.
    • step 2 : prefix가 트라이에 존재하는지 search 메서드를 통해 검색한다.
      • prefix가 트라이에 없는 경우 
        • None을 반환한다.
      • prefix가 트라이에 있는 경우
        • prefix의 마지막 문자가 들어있는 트라이 노드를 반환한다.
    • step 3 : collectAllWords를 호출하여 입력받은 prefix가 붙어 하나의 단어가 되는 완전한 단어를 모두 찾아 수집한다.
  • 자동 완성 코드의 각 노드의 해시 테이블에 *의 key 값에 대하여 우선 순위를 value로 주어 활용할 수 있다. (p399).
    • 우선 순위가 높은 단어가 자동 완성으로 먼저 출력되도록 하기 위함이다.
# 트라이 노드 구현-----------------------------------------------------------
class TrieNode:
    
    def __init__(self):
        # 자식 노드는 해시 테이블만 포함한다.
        self.children = {}
        
# 루트 노드를 추적하는 Trie 클래스--------------------------------------------
class Trie:
    def __init__(self):
        self.root = TrieNode()    
        
# 트라이 검색----------------------------------------------------------------
    def search(self, word):
    cyrrentNode = self.root
    
    for char in word:
        # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
        if currentNode.children.get(char):
            # 자식 노드를 따라간다.
            # 'self.children = {}' 구조로 자식 노드의
            # 해시 테이블을 초기화한다. (self 자리에 currentNode 사용).
            currentNode = currentNode.children[char]
        else:
            # 현재 노드의 자식 중에 현재 문자가 없으면
            # 검색하려는 단어가 트라이에 없는 것이다.
            return None
        
        # 자동 완성 기능을 지원하기 위해
        # currentNode를 반환한다.
        return currentNode

# 트라이 삽입----------------------------------------------------------------
    def insert(self, word):
        currentNode = self.root
    
        for char in word:
            # 현재 노드에 현재 문자를 키로 하는 자식이 있으면
            if currentNode.children.get(char):
                # 자식 노드를 따라간다.
                currentNode = currentNode.children[char]
            else:
                # 현재 노드의 자식 중에 현재 문자가 없으면
                # 그 문자를 새 자식 노드로 추가한다.
                newNode = TrieNode()
                currentNode.children[char] = newNode
            
                # 새로 추가한 노드를 따라간다.
                currentNode = newNode
    
        # 단어 전체를 트라이에 삽입했으면 
        # 마지막으로 *를 추가한다.
        # "*" key에 None을 value로 저장.
        currentNode.children["*"] = None

# 모든 단어를 배열로 만드는 메서드--------------------------------------------
    def collectAllWords(self, node=None, word="", words=[]):
    # 메서드는 인수 세 개를 받는다.
    # 첫 번째 인수인 node는 그 자손들에게서 단어를 수집할 노드이다.
    # 두 번째 인수인 word는 빈 문자열로 시작하고
    # 트라이를 이동하면서 문자가 추가된다.
    # 세 번째 인수인 word는 빈 배열로 시작하고
    # 함수가 끝날 때는 트라이 내 모든 단어를 포함한다.
    
    # 현재 노드는 첫 번째 인자로 전달받은 node다.
    # 아무것도 받지 않았으면 루트 노드다.
    currentNode = node or self.root
    
    # 현재 노드의 모든 자식을 순회한다.
    for key, childNode in currentNode.children.items():
        # 현재 키가 *이면 완전한 단어 끝에 도달했다는 뜻이므로
        # 이 단어를 words 배열에 추가한다.
        if key == "*":
            words.append(word)
        else: # 아직 단어 중간이면
            # 그 자식 노드에 대해 이 함수를 재귀적으로 호출한다.
            # word + key는 재귀적으로 호출되며 단어가 완성된다.
            # word + key로 완성된 단어를 바로 위의 words에 넣는 것이다.
            self.collectAllWords(childNode, word + key, words)
            
    return words

# 자동 완성 마무리-----------------------------------------------------------
    def autocomplete(self, prefix):
    currentNode = self.search(prefix)
    if not currentNode:
        return None
    return self.collectAllWords(currentNode, prefix)

6. 연습 문제 정리

3 번

def traverse(self, node=None):
    currentNode = node or self.root
    
    # node를 주지 않을 경우 root 노드부터 시작하여
    # 모든 자식 노드의 해시 테이블을 순회한다.
    # for loop은 상위 노드의 자식 노드에 대한 반복문이고,
    # 재귀를 통해 더 깊은 트라이의 노드까지 트리클링한다.
    for key, childNode in currentNode.children.items():
        print(key)
        if key != "*":
            self.traverse(childNode)

 

4 번

def autocorrect(self, word):
    currentNode = self.root
    # 지금까지 트라이에서 찾은 사용자 단어와 일치하는 부분을
    # 기록한다. 이 문자열을 트라이에서 찾을 수 있는
    # 최선의 접미사와 이어 붙여야 한다.
    wordFoundSoFar = ""
    
    for char in word:
        # 현재 노드의 자식 키 중에 현재 문자가 있으면
        if currentNode.children.get(char):
            wordFoundSoFar += char
            # 자식 노드를 따라간다.
            currentNode = currentNode.children.get(char)
        else:
            # 현재 노드의 자식 중에 현재 문자가 없으면
            # 현재 노드부터 내려가면서 만들 수 있는 모든 접미사를 모아
            # 첫 번째 접미사를 가져온다.
            # 그 접미사를 지금까지 찾은 접두사에 이어 붙여
            # 사용자가 입력하려던 문자를 제안한다.
            return wordFoundSoFar + self.collectAllWords(currentNode)[0]
    
    # 사용자가 단어를 트라이에서 찾았으면
    return word

'♧ Self-study > <누구나 자료구조와 알고리즘>' 카테고리의 다른 글

Chapter 19. 공간 제약 다루기  (4) 2024.09.22
Chapter 18. 그래프로 뭐든지 연결하기  (0) 2024.09.22
Chapter 16. 힙으로 우선순위 유지하기  (0) 2024.09.19
Chapter 15. 이진 탐색 트리로 속도 향상  (2) 2024.09.17
Chapter 14. 노드 기반 자료 구조  (0) 2024.09.14

'♧ Self-study/<누구나 자료구조와 알고리즘>'의 다른글

  • 현재글Chapter 17. 트라이(trie)해 보는 것도 나쁘지 않다

관련글

티스토리툴바