트라이 알고리즘 - 문자열 검색

트라이 자료구조

• 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

• DFS 형태로 검색을 해보면 문자열을 탐색.

• 목적

  • 문자열의 탐색을 하고자 할때, 시간적으로 훨씬 효율적이지만 저장 공간 크기가 크다는 단점이 있음.
  • 검색어 자동완성, 사전에서 찾기, 문자열 검사 등에 대표적으로 사용할 수 있음

• 트라이 구현

  • node 클래스 생성

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

    key는 해당 노드의 문자가 들어가고 children 에는 자식 노드가 포함된다.
    data 는 문자열이 끝나는 위치를 알려주는 역할을 하게 된다. 예를 들어서 “car”이 “r”에서 끝날 때, “r”을 key로 가지는 노드의 data에 “car”를 입력한다.해당 노드에서 끝나는 문자열이 없을 경우에는 None으로 그대로 놔둔다.

  • trie 삽입과 검색 기능 구현

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 
    # 삽입할 string 각가의 문자에 대해 자식 node 만들며 내려감

    for char in string:
      # 자식 node 등 중 같은 문자가 없으면 node 새로 생성
      if char not in curr_node.children :
        curr_node.children[char] = Node(char)
      # 이제 존재하게 된다면 해당 노드로 이동
      curr_node = curr_node.children[char]
    
    #문자열 끝난 지점의 노드 data값에 해당 문자열을 입력
    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]
      # 없다면 False를 반환
      else:
        return False
    #탐색이 끝난 후 해당 노드에 data 가 존재하면 문자가 포함 되어있단 뜻임.
    if curr_node.data != None:
      return True