백인감자
[알고리즘] Trie 본문
Trie
tree 기반의 자료구조이다.
사용 용도 : 여러 개의 문자열 (ex. 문서파일) 에서 많은 양의 텍스트정보를 빠르고 효율적으로 검색하기 위해 사용.
Trie는 사전 혹은 인터넷 자동완성의 retrieval을 효과적으로 할 수 있는 자료구조이다.
retrieval 에 유용하다고 하여 Fredkin이 Trie 라고 명명함.
Standard Tries
external node 는 네모 모양으로 표시해둔 것을 확인 할 수 있고 string 의 개수 = external node 의 개수 인 것을 확인 할 수 있다.(8개)
어떤 standard trie 가 크기 d 의 알파벳 으로부터 전체 길이가 n 인 s개의 문자열을 가진 집합 S 를 저장한다고 하면 아래를 만족한다.
(A standard trie storing a collection S of s strings of total length n from an alphabet of size d has the following properties)
위 뜻을 영어로 봐도 한글로 봐도 직관적으로 이해가 잘 안되서 위의 Fig 9.10 을 기준으로 설명하면 아래와 같다.
알파벳은 26개의 문자로 구성되어 있기 때문에 d=26
s개의 문자열 : bear ,bell ,.....,stop 이므로 s=8
S= s개의 문자열을 담고 있는 집합(collection)
집합 S 의 각 원소의 문자 개수를 다 합친 것이 n=31이다.(4 + 4 + 3 + 4 + 3 + 3 + 5 + 4 = 31)
위의 트리 구조 T 라고 지칭
- T 의 모든 internal node 는 최대 d 개의 children 을 가질 수 있다. (알파벳이 26개이므로 최대 26개 children 가능)
- T has s external nodes ( 최종적으로 s개의 문자열을 나타내는 tree 이기 때문이다.)
- The height of T is equal to the length of the longest string in S (stock 이 가장 긴 문자열이므로 tree 의 height 라고 할 수 있다.)
- The number of nodes of T is O(n) ( node 개수가 최대 n 개 )
standard trie 를 이용한 Word matching의 예를 살펴보자.
(a) 는 어떠한 문장들(텍스트) 이 배열에 저장되어 있는 모습이고 (b) 는 이 문장들 중에서 단어를 찾아서 standard trie 로 나타낸 것이다.
external node 의 아래에 적힌 숫자는 해당 단어들이 시작되는 index 를 나타낸다.
성능
- 길이가 m인 문자열을 찾는데 걸리는 시간은 O(dm)이다. (문서의 길이와 상관이 없음)
최대 m+1 개의 node 를 방문한다. (root 노드는 비어있는 노드이므로 +1 해준다.)
각각의 node를 찾는데 걸리는 시간은 O(d) 이다. (d= 알파벳 개수 (26) )
상수 1 을 무시하면 O(dm) 이 된다.
- 기존 trie 에 문자열 X 를 삽입하는데 소요되는 시간은 O(dm) 이다.
- S 집합에 대해서 전체 trie 를 생성하는 데 소요되는 시간은 O(dn) 이다.
Compressed Tries
standard trie 에서 child 가 하나뿐인 internal node 들을 child 와 합쳐서 하나의 node 로 압축한 trie 이다.
아래의 예시를 통해 확인해보자.
node 의 개수가 22개에서 14개로 감소한 것을 확인 할 수 있다.
특징 : 모든 internal node 의 children 은 최소 2개 ~ 최대 d개를 가질 수 있다. (d : 알파벳 개수 )
아래의 예시를 보자.
s개의 문자열을 저장한 집합 S 가 있다고 하자. 집합 S 의 원소개수 : s개 (10 개) (index 0~s-1)
compressed trie 의 node 개수 : O(s)
compact representation : trie 의 node 에 알파벳 대신 숫자들(index)로 채워넣는 것
node 개수가 줄어들면서 trie 를 생성하는데 사용되는 공간이 O(n) -> O(s) 으로 감소된다.
Suffix Tries
suffix : 접미사 라는 뜻
접미사 (접미어) 기준으로 노드를 만들기 때문에 문자열의 마지막 알파벳을 기준으로 node를 생성한다고 보면 된다.
ex. 문자열이 abc 이면 생성되는 node(suffix) 는 c, bc ,abc 3개가 된다.
길이가 n인 문자열 X 가 있으면 n 개의 suffix 를 만들 수 있다. -->n 개의 external node 가 생성됨
예시를 통해 알아보자.
문자열 X : minimize 길이 n : 8
위의 그림 (a) 는 suffix trie, (b) 는 Compact representation 을 나타낸 것이다.
노드에 적힌 숫자는 (a) 의 문자열의 시작점과 끝점 index 번호를 나타낸 것이다.
길이가 n인 문자열 X에 대한 suffix 들의 전체 합은 1+2+...+n =n(n+1)/2 이므로 저장하기 위한 공간 복잡도는 O(n^2) 이 된다.
하지만 suffix trie 구조상으로 보면 O(n) 이면 된다. (external node 의 개수)
길이가 n인 문자열 X에 대한 suffix Trie T의 compact representation 에서는 O(n) 의 공간을 사용한다.
기존의 tie 생성 방식을 사용한다면 node 들의 합이 n^2 정도이기 때문에 시간복잡도가 O(dn^2) 이 될것이다.
pattern matching 을 위한 알고리즘을 적용한다면 compact suffix trie 의 생성의 시간복잡도는 O(dn) 이다.
suffixTrieMatch 알고리즘
pattern matching 에 대한 시간 복잡도는 O(dm)이다. -문서의 길이와 아무 상관 없다는 것을 알 수 있다. m : 패턴의 길이 d : 알파벳 수