Trie 트라이 알고리즘

트라이(Trie) 알고리즘

# 개념
트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의
자료구조이다.
래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 한다.
retrival(탐색)에서 trie를 따왔다고도 한다.
이 자료구조를 활용해 검색어 자동완성, 사전에서 찾기, 문자열 검사 등을
한다고 한다.

# 사용 목적
문자열의 탐색을 할 때, 단순하게 하나씩 비교하면서 탐색을 하는 것보다
시간복잡도 측면에서 훨씬 효율적이다.
단 빠르게 탐색이 가능하다는 장점이 있지만, 각 노드에서 자식들에 대한
포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기가
크다는 단점도 있다.
문자열을 검색하는 문제에서 입력되는 문자열이 많은 경우 자주 사용됨.

# 시간 복잡도
제일 긴 문자열의 길이를 L, 총 문자열들의 수를 M이라 할 때 시간복잡도.

생성 시간 복잡도 : O(M*L), 모든 문자열들을 넣어야하니 M개에 대해
트라이 자료구조에 넣는 건 가장 긴 문자열 길이만큼 걸리니 L만큼 걸려서
O(M*L)

탐색 시간 복잡도 : O(L), 트리를 타고 들어가봤자 가장 긴 문자열의
길이만큼만 탐색해서 O(L)만큼 걸린다.

# 알아야 할 점
1. 트라이 알고리즘은 노드를 이용한 tree 형태로 이루어져 있다.
2. 문자열의 끝을 알리는 flag가 존재한다.

# 구현
노드 구현

class Node(object):
def __init__(self, key, data=None):
self.key = key # 값으로 입력될 문자
self.data = data # 문자열의 종료를 알리는 flag
# True/False로도 구현할 수 있지만, 되돌아가는 일이 없게 하기
# 위해 전체 문자열을 저장
self.children = {}


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

  def insert(self, string):
    current_node = self.head
    for char in string:
      if char not in current_node.children:
        current_node.children[char] = Node(char)
      current_node = current_node.children[char]
    current_node.data = string

  def search(self, string):
    current_node = self.head
    for char in string:
      if char in current_node.children:
        current_node = current_node.children[char]
      else:
        return False
    if current_node.data:
      return True
    else:
      return False

  def starts_with(self, prefix):
    current_node = self.head
    words = []
    
    for p in prefix:
      if p in current_node.children:
        current_node = current_node.children[p]
      else:
        return None
    
    current_node = [current_node]
    next_node = []
    while True:
      for node in current_node:
        if node.data:
          words.append(node.data)
        next_node.extend(list(node.children.values())) 
      if len(next_node) != 0:
        current_node = next_node
        next_node = []
      else:
        break
    return words


Trie에는 여러가지 함수가 필요하다.
1. head를 빈노드로 설정
2. insert 함수 - 트리를 생성하기 위한 함수이다.
입력된 문자열의 문자를 하나씩 children에 확인 후 저장하고
문자열을 다 돌면 마지막 노드의 data에 문자열을 저장한다
3. search 함수 - 문자열이 존재하는지에 대한 여부를 리턴하는 함수.
문자열을 하나씩 돌면서 확인 후 마지막 노드가 data가 존재한다면 
True를, 그렇지 않거나 애초에 children에 존재하지 않는다면 False를
리턴한다
4. starts_with 함수 - prefix 단어로 시작하는 단어를 찾고, 
배열로 리턴하는 함수이다. prefix 단어까지 tree를 순회 한 이후
그 다음부터 data가 존재하는 것들만 배열에 저장하여 리턴한다.


출처 : https://m.blog.naver.com/cjsencks/221740232900

[Python / 파이썬] Trie 알고리즘

메모장에 옮기면서 곱씹어보며 공부한 걸 여기에 옮겼다.

나는 메모장에 다시 타이핑하면서 공부하는게 이해가 더 잘되는듯.