[알고리즘] 문자열 - 트라이(Trie)

문자열을 빨리 찾을 순 없을까?

개념

문자열은 문자들을 이어붙여 만든 개념으로 이를 빠르게 탐색하고 싶을 때  문자열들을 문자 하나를 기준으로 앞에는 어떤 문자가 오는지, 뒤에는 어떤 문자가 오는지를 체크 해놓으면 여러 문자열을 저장할 때 더 적은 비용을 들여 탐색할 수 있다. 말은 쉽지..

 

트라이(Trie) 알고리즘

• 문자열 집합을 표현하는 트리 자료구조
• 문자열을 탐색하는데 있어 시간을 줄이기 위한 알고리즘(문자열 탐색 알고리즘)

장점

• 빠른 탐색 시간( O(M *L) → O(M) ※M: 문자열의 수, L: 가장 긴 문자열 길이)

단점

• 정렬이 되어 있어야 함
• 비효율적인 메모리
  • 기존 : 문자열 길이(개행포함) * 문자열의 총 개수
  • 트라이 형식 : 문자열 *  (다음 노드의 수 + 끝인 경우의 문자열) * 문자열의 총 개수

 

이해

기본적인 개념은 간단하다. "HELLO"와 "HELL"를 예시로 들어보자.

입력

1. "HELLO" 입력
   1. Root노드 children(다음노드)에, "H" 노드를 생성하고 추가
   2. "H" 노드 children(다음노드)에, "E" 노드를 생성하고 추가
   3. "E" 노드 children(다음노드)에, "L" 노드를 생성하고 추가
   4. "L" 노드 children(다음노드)에, "L" 노드를 생성하고 추가
   5. "L" 노드 children(다음노드)에, "O" 노드를 생성하고 추가, 문자열의 끝이므로 data에 표시

  2. "HELL" 입력

1. Root노드 children(다음노드)에, "H" 노드가 이미 있으므로 타고 감
2. "H" 노드 children(다음노드)에, "E" 노드가 이미 있으므로 타고 감
3. "E" 노드 children(다음노드)에, "L" 노드가 이미 있으므로 타고 감
4. "L" 노드 children(다음노드)에, "L" 노드가 이미 있으므로 타고 감
5. "L" 노드가 마지막 이므로 data 에 표시

탐색

• "HELL"을 탐색 해보자
  1. Root노드 children(다음노드)에, "H" 노드가 이미 있으므로 타고 감
  2. "H" 노드 children(다음노드)에, "E" 노드가 이미 있으므로 타고 감
  3. "E" 노드 children(다음노드)에, "L" 노드가 이미 있으므로 타고 감
  4. "L" 노드 children(다음노드)에, "L" 노드가 이미 있으므로 타고 감
  5. 마지막 "L" 노드의 data를 확인, 끝 표시가 있으면 단어가 있다고 판단(탐색 끝)

구현

트라이 트리에 사용할 Node 구현

• 현재 위치를 알려주는 key
• 마지막 문자임을 확인할 수 있는 data
• 다음 단어를 저장할 children

class Node:
    def __init__(self, key:str, data=False):	# 문자열의 마지막을 문자열로 만들 땐 data=None
        self.key = key
        self.data = data
        self.children = {}

Trie 알고리즘 구현(class)

1. 필요 Method(클래스 내장 함수)
   • 생성자(__init__)

     # 위에서 생성한 Node class를 이용하여 생성자 작성
         def __init__(self) -> None:
             # 시작 부분 : root
             self.root = Node(None)​

1. • 저장(insert)

         def insert(self, string:str) -> None:
     		# 시작은 root 
         	current_node = self.root
             # 한글자씩 저장
             for char in string:
             	# 현재 글자가 다음 노드에 없으면 추가해주기
             	if char not in current_node.children.keys():
                 	current_node.children[char] = Node(char)
                 # 현재 글자를 키로 갖는 Node로 이동
                 current_node = current_node.children[char]
             # 마지막에 
             current_node.data = True
             # data를 문자열 형태로 저장
             # current_node.data = string	# Node의 기본 data값을 None으로 설정해주기​​

2. • 탐색(search)

         def search(self, string:str) -> bool:
         	# 시작은 root
         	current_node = self.root
             # 한 글자씩 탐색하며 있는 지 확인
             for char in string:
             	# 현재 문자가 다음 노드에 있으면 탐색, 없으면 False 반환(없음)
             	if char in current_node.children.keys():
                 	current_node = current_node.children[char]
                 else:
                 	return False
             # 다 돌았는데 끝이 아니면 False(없음), 끝이면 True(찾음)
             if current_node.data:
                 return True
             else:
             	return False​

참조

• Trie에 저장되는 Node 내부 생김새
  예시) "Hello", "Hell", "Here"

Trie<class>[{
Node<class>[{key:None, data:False, children:{} }],
Node<class>[{key:"H", data:False, children:{"e" : Node<class>} }],
Node<class>[{key:"e", data:False, children:{"l": Node<class>, "r": Node<class>} }],
Node<class>[{key:"l", data:True, children:{"l": Node<class>, "o": Node<class>} }],
Node<class>[{key:"o", data:True, children:{} }],
Node<class>[{key:"r", data:False, children:{"e": Node<class>} }]
}]

코드

class Node:
	def __init__(self, key:str, data=False):	# 문자열의 마지막을 문자열로 만들 땐 data=None
    	self.key = key
        self.data = data
        self.children = {}

class Trie:
	# 위에서 생성한 Node class를 이용하여 생성자 작성
	def __init__(self) -> None:
    	# 시작 부분 : root
    	self.root = Node(None)
    
    def insert(self, string:str) -> None:
		# 시작은 root 
    	current_node = self.root
        # 한글자씩 저장
        for char in string:
        	# 현재 글자가 다음 노드에 없으면 추가해주기
        	if char not in current_node.children.keys():
            	current_node.children[char] = Node(char)
            # 현재 글자를 키로 갖는 Node로 이동
            current_node = current_node.children[char]
        # 마지막에 
        current_node.data = True
        # data를 문자열 형태로 저장
        # current_node.data = string	# Node의 기본 data값을 None으로 설정해주기

	def search(self, string:str) -> bool:
    	# 시작은 root
    	current_node = self.root
        # 한 글자씩 탐색하며 있는 지 확인
        for char in string:
        	# 현재 문자가 다음 노드에 있으면 탐색, 없으면 False 반환(없음)
        	if char in current_node.children.keys():
            	current_node = current_node.children[char]
            else:
            	return False
        # 다 돌았는데 끝이 아니면 False(없음), 끝이면 True(찾음)
        if current_node.data:
            return True
        else:
        	return False