AI 도구 매일 노트 — 해고된 개발자의 기록

 1편에 이어 2편이다. 지난 장에서는 trie의 간단한 개념과 생성과 입력 기능에 대해 알아보았다. 이번 편에서는 조회와 삭제에 대해 알아보도록 하겠다. 접두어로 검색  Trie의 가장 큰 장점이라고 생각하는 접두어 검색 기능이다. 단어의 일부분으로 전체단어를 검색할 수 있다. 예를들어 trie에 gold, good, gerald를 저장한 다음 검색어에 g를 입력하면 gold, good, gerald를 모두 검색할 수 있다. 이런 기능은 검색어 자동완성에 쓰인다고 한다. 우선 검색 부분의 코드를 보도록 하겠다. def search_with_prefix(self, prefix): words = list() if prefix is None: raise ValueError('Requires not-Null prefix') top_node = self.head for letter in prefix: if letter in top_node.children: top_node = top_node.children[letter] else: return words if top_node == self.head: queue = [node for key, node in top_node.children.items()] else: queue = [top_node] while queue: current_node = queue.pop() if current_node.data is not None: words.append(current_node.data) queue = [node f...

 Trie는 이 구조를 구현한 라이브러리도 여럿있어서 파이썬으로 구현하기는 쉬울 것이다. 하지만 trie에 대해 더 잘 이해하고 연습도 할 겸 여기저기에서 참조해가며 직접 만들어 보았다. 이번에는 trie에 대한 간단한 개념과 문자열의 삽입과 조회 부분의 구현까지 진행할 것이다. 특징   Trie는 prefix tree라고도 불리는 트리 구조의 알고리즘이다. Trie는 다음과 같은 특징이 있다. 검색이 빠르고,  문자열을 키로하는 동적 집합이나 연관 배열로 사용되고  노드는 키를 갖지 않는 대신 노드의 위치가 키 역할을 하고  root가 빈 스트링이라는 특징이 있다. 시간 복잡도  시간 복잡도는 알고리즘의 수행시간 분석결과를 나타내는 용어이다. 당연히 시간 복잡도가 낮을수록 좋으며 연산 횟수를 계산하고, 처리해야 할 데이터의 수 n에 대한 연산횟수 함수 T(n)을 구성하여 구한다.  Trie의 시간 복잡도는 대표적인 트리 구조 중 하나인 이진 검색 트리(Binary Search Tree)와 비교를 해보도록 하겠다. 데이타 구조 시간 복잡도 (정수/실수) 이진 검색 트리 O(logN) 문자열 이진 검색 트리 O(MlogN) 트라이 O(M)   문자열은 길이가 변하기 때문에 검색 시간이 많이 소요된다. 길이가 고정된 정수나 실수는 O(logN)의 시간이 걸리지만 문자열은 길이가 변하기 떄문에 문자열의 최대 길이 M을 곱한 O(MlogN)이 된는데 trie는 이러한 문제를 해결하기 위해 고안된 자료구조이다. 트라이의 구조  알파벳만을 사용하여 trie를 구성할 경우 각 노드는 26개의 알파벳과 1개의 공백으로 구성된 27개의 포인터를 갖고있는 배열을 갖고 있다.   문자열 집합 : S = {"BE", "BET", "BUS", "TEA", "TEN"}을 trie로 구성한 그...

Suffix tree는 문자열의 모든 접미사들을 표현하는 trie 모양의 자료 구조이다. prefix tree라 불리는 trie가 근간이 되는 자료구조인듯 한데 두 자료구조의 차이는 banana라는 단어가 있을 때 trie는 banana라는 단어만 저장을 하지만 suffix tree는 banana, anana, nana, ana, na, a 와 같이 banana라는 단어에서 나올 수 있는 모든 경우의 수를 다 저장한다는 것이다. 쓸데없이 모든 경우를 저장하는 이유는 문자열에 대한 검색을 할 때 필요하기 때문이다. Trie 자료구조 같은 경우에는 ban, ba와 같은 일부분의 단어로 banana라는 완전한 단어를 찾을 수 있지만 nan, ana와 같은 단어로는 banana를 찾을 수 없다. 이러한 문제를 해결하기위해 trie를 개선시킨 것이 suffix tree인듯 하다.  Suffix trie는 trie에 모든 suffix들을 저장한 구조를 의미한다. 아래 그림은 abaaba라는 문자열 T를 suffix tree에 저장하는 예시이다. suffix tree나 suffix trie에 문자열을 저장할 때는 문자열의 끝에 $를 붙이는데 그 이유는 정확히 모르겠다... 아마 문자열의 끝을 알리기 위한 용도인 것 같다. Suffix Trie의 형태  위 그림의 왼쪽과 같은 모양이 suffix trie이다. 여기서 자식 노드가 1개 뿐인 것들을 합치면 오른쪽과 같은 모양이 되는데 저러한 형태의 자료구조를 suffix tree라 한다. Suffix Tree  이 suffix tree는 문자열의 길이만큼의 leaf node를 갖는다  위 그림에서 오른쪽 그림은 tree의 edge label을 (offset, length)의 형태로 T를 나타낸 것이다. Suffix tree의 label  각 노드의 label은 root로부터 node로 연결된 edge의 label과 ...