9.2 Tries
KMP나 BM 알고리즘에서는 search 속도를 높이기 위해 pattern을 preprocess했지만(failure function, last function), Tries에서는 text를 preprocess한다. 따라서, fixed text에 연속된 query들이 있을 때 사용한다. 처음에 text를 preprocessing하는 데 비용은 많이 들지만, 이것은 나중에 계속되는 query 속도를 증가시킴으로 보상된다.
trie 는 'a tree-based data structure for storing strings in order to support fast pattern matching'이다. information을 retrieval 하는데 주로 사용된다고, "retrieval"에서 이름을 따왔다. trie에서 지원하는 주요 query operation들로는, pattern matching과 prefix matching이 있다.
1) Standard tries
⊙ S에 대한 standard trie 는 ordered tree T로, 다음과 같은 성질을 가진다.
1. T의 root를 제외한 모든 node에는 ∑의 한 문자가 labeled.
2. ordered tree 이므로, child는 정렬되어있다.
3. root->external path는 S의 string이 된다.
trie에서는, no string in S(∑으로 만들어진 string들의 집합) is a prefix of another string. 밑에 있는 trie 구조를 보면 알겠지만, 한 string이 다른 string의 prefix가 되면, 즉, bil, bill 이란 단어는 함께 S에 있으면 안된다. 이것때문에, S의 string은 unique하게 external node랑 짝을 이루게 되고, 이는 search를 간단하게 만든다. 또한, trie에서는, string들의 common prefix를 간결하게 저장한다.
→ 따라서, standard trie는
▪ 모든 internal node는 최대 d(∑ size)개의 child 가진다.
▪ s(string개수)개의 external을 가진다.
▪ 높이는 가장 긴 string의 길이와 같다.
▪ 전체 node 수는 O(n)이다. n은 total length.
⊙ Search : root에서 내려가면서 string을 찾는다. path가 존재하고, external node에서 끝나면, 해당 string이 존재하는 것이고, running time은 O(dm)이다. (d는 size of ∑이고, m은 size of string이다.) 최대 m+1개(root 1개 포함)의 node를 visit하고, 각 node에서 O(d) 걸린다. 여기에서, dictionary of characters를 hash table이나 lookup table로 구현하면 O(d)를 O(1) 이나 O(logd)가 될 수 있지만, d는 주로 constant이므로, 그냥 간단하게 O(d) approach를 사용한다.
따라서, standard tires는 word matching에 사용된다. word matching은 말 그대로, text에 있는 word를 찾는 것이다. 이는, text에서의 임의의 substring을 찾는 것(앞에서 배웠던 Brute-Force, BM, KMP와 같은)이 아니라, text에서의 한 단어와 정확히 일치하는 단어만 찾는것이다. tire를 사용하면, 길이 m인 단어를 찾는데 걸리는 시간은 역시, O(dm)이다. 이는 간단하게 prefix matching에 사용될 수도 있지만, pattern이 proper suffix이거나 두 단어로 span했을 때에는 효율적으로 수행되지 못한다.
⊙ Standard Trie 만들기
Standard trie를 만드는 것은, 아주 직관적이다. 그냥 S에 있는 string들을 trie T에 한 번에 하나씩 넣어주면 되는데, prefix-free이므로, 한 word를 넣을때, root부터 탐색을 하다보면, 한 internal node에서 멈추게 된다. 그러면 pattern의 그 다음 char부터는 child node를 만들어가면서 insert 해주면 된다. 역시, 한 단어를 insert하는데 걸리는 시간은 O(dm)이다. 따라서, S에 속한 string들의 총 길이가 n이라하면, trie하나를 만드는 데 걸리는 시간은 O(dn)이 된다.
⊙ Performance
전체 노드 수의 worst-case는, 모든 string이 다른 string과 common prefix를 가지지 않을 때이다. 이 때에는, 모든 internal node는 1개의 child node를 가지게 되기 때문이다.
2) Compressed tries
Standard trie에서의 공간 낭비 때문에 만들어진 것이 compressed trie이다. Standard trie에서, 많은 node들이 child가 1개이고, 이것은 단어 수보다 node 수가 더 많을 수가 있어서 낭비인 것이다. 따라서, compressed tire는 standard trie와 비슷하지만, 모든 internal node는 각각 최소 2개의 child node를 가진다.
Internal node v가 root도 아닌데 child node를 한 개 가지고 있으면 그 node는 redundant하다 하고, 이런 redundant node들의 chain을 하나의 node로 만든다.
⊙ Compressed Trie의 특징
▪ 모든 internal node는 2~d개의 child node를 가진다.
▪ s개의 external node를 가진다.
▪ 전체 노드 수는 O(s)이다.
⊙ Compact Representation
Compressed trie가 진짜 장점을 가지기 위해서는, 보조적인 index구조를 가져야 한다. 이 보조적인 index 구조는, 따로 저장할 필요는 없고, primary structure에 이미 저장된 string들의 collection에 구현된다.
예를 들어, S가 S[0], S[1], ..., S[s-1]의 배열이라 하자. 한 노드에 char들을 바로 적지 말고, (i, j, k) 로 적어넣는다. 이것은 S[i][j..k]를 의미하는 것으로, S[i]의 j~k 번째의 substring이라는 의미이다.
3) Suffix tries
한 String X에 대한 Suffix trie는 X의 모든 suffix들의 compressed tire이다. (suffix tree, position tree라고도 한다.) Trie이기 때문에, 한 suffix가 다른 suffix의 prefix가 되지 않게 하기 위해서, 기존의 ∑에 없던 문자 $를 suffix 뒤에 붙인다. 예를 들어, X가 "amizemize" 라면, 뒤의 mize는 mizemize의 prefix가 될 수 있기 때문이다. 그러나, mize$는 mizemize$의 suffix이기는 하지만 prefix는 아니다.
그리고 compact representation은 더 간단하다. (i,j)로 나타낼 수 있는데, 이것은 X[i..j]를 가리킨다.
⊙ Saving Space
string의 길이가 n일 때, 전체 suffix들의 길이의 합은,
1+2+3+...+n = n(n+1)/2
이므로, suffix들을 저장하는데 드는 공간은 O(n²)가 된다. 하지만, implicitly O(n) 의 공간이 사용된다.
⊙ Suffix trie 만들기
전체 suffix들의 길이는 string의 길이를 n이라 할때, O(n²)이다. 따라서, standard trie와 같은 방법으로 만들면 O(dn²)의 시간이 걸린다. 그러나 compact suffix trie는 O(n) 시간안에 만들어지지만, 복잡해서 여기에서는 다루지 않는다.
⊙ Using a Suffix Trie
arbitrary pattern matching을 지원하고, O(dm) 시간 걸린다.
KMP나 BM 알고리즘에서는 search 속도를 높이기 위해 pattern을 preprocess했지만(failure function, last function), Tries에서는 text를 preprocess한다. 따라서, fixed text에 연속된 query들이 있을 때 사용한다. 처음에 text를 preprocessing하는 데 비용은 많이 들지만, 이것은 나중에 계속되는 query 속도를 증가시킴으로 보상된다.
trie 는 'a tree-based data structure for storing strings in order to support fast pattern matching'이다. information을 retrieval 하는데 주로 사용된다고, "retrieval"에서 이름을 따왔다. trie에서 지원하는 주요 query operation들로는, pattern matching과 prefix matching이 있다.
1) Standard tries
⊙ S에 대한 standard trie 는 ordered tree T로, 다음과 같은 성질을 가진다.
1. T의 root를 제외한 모든 node에는 ∑의 한 문자가 labeled.
2. ordered tree 이므로, child는 정렬되어있다.
3. root->external path는 S의 string이 된다.
trie에서는, no string in S(∑으로 만들어진 string들의 집합) is a prefix of another string. 밑에 있는 trie 구조를 보면 알겠지만, 한 string이 다른 string의 prefix가 되면, 즉, bil, bill 이란 단어는 함께 S에 있으면 안된다. 이것때문에, S의 string은 unique하게 external node랑 짝을 이루게 되고, 이는 search를 간단하게 만든다. 또한, trie에서는, string들의 common prefix를 간결하게 저장한다.
→ 따라서, standard trie는
▪ 모든 internal node는 최대 d(∑ size)개의 child 가진다.
▪ s(string개수)개의 external을 가진다.
▪ 높이는 가장 긴 string의 길이와 같다.
▪ 전체 node 수는 O(n)이다. n은 total length.
⊙ Search : root에서 내려가면서 string을 찾는다. path가 존재하고, external node에서 끝나면, 해당 string이 존재하는 것이고, running time은 O(dm)이다. (d는 size of ∑이고, m은 size of string이다.) 최대 m+1개(root 1개 포함)의 node를 visit하고, 각 node에서 O(d) 걸린다. 여기에서, dictionary of characters를 hash table이나 lookup table로 구현하면 O(d)를 O(1) 이나 O(logd)가 될 수 있지만, d는 주로 constant이므로, 그냥 간단하게 O(d) approach를 사용한다.
따라서, standard tires는 word matching에 사용된다. word matching은 말 그대로, text에 있는 word를 찾는 것이다. 이는, text에서의 임의의 substring을 찾는 것(앞에서 배웠던 Brute-Force, BM, KMP와 같은)이 아니라, text에서의 한 단어와 정확히 일치하는 단어만 찾는것이다. tire를 사용하면, 길이 m인 단어를 찾는데 걸리는 시간은 역시, O(dm)이다. 이는 간단하게 prefix matching에 사용될 수도 있지만, pattern이 proper suffix이거나 두 단어로 span했을 때에는 효율적으로 수행되지 못한다.
Word matching and prefix matching with a standard trie
⊙ Standard Trie 만들기
Standard trie를 만드는 것은, 아주 직관적이다. 그냥 S에 있는 string들을 trie T에 한 번에 하나씩 넣어주면 되는데, prefix-free이므로, 한 word를 넣을때, root부터 탐색을 하다보면, 한 internal node에서 멈추게 된다. 그러면 pattern의 그 다음 char부터는 child node를 만들어가면서 insert 해주면 된다. 역시, 한 단어를 insert하는데 걸리는 시간은 O(dm)이다. 따라서, S에 속한 string들의 총 길이가 n이라하면, trie하나를 만드는 데 걸리는 시간은 O(dn)이 된다.
⊙ Performance
전체 노드 수의 worst-case는, 모든 string이 다른 string과 common prefix를 가지지 않을 때이다. 이 때에는, 모든 internal node는 1개의 child node를 가지게 되기 때문이다.
2) Compressed tries
Standard trie에서의 공간 낭비 때문에 만들어진 것이 compressed trie이다. Standard trie에서, 많은 node들이 child가 1개이고, 이것은 단어 수보다 node 수가 더 많을 수가 있어서 낭비인 것이다. 따라서, compressed tire는 standard trie와 비슷하지만, 모든 internal node는 각각 최소 2개의 child node를 가진다.
Internal node v가 root도 아닌데 child node를 한 개 가지고 있으면 그 node는 redundant하다 하고, 이런 redundant node들의 chain을 하나의 node로 만든다.
Compressed Trie
⊙ Compressed Trie의 특징
▪ 모든 internal node는 2~d개의 child node를 가진다.
▪ s개의 external node를 가진다.
▪ 전체 노드 수는 O(s)이다.
⊙ Compact Representation
Compressed trie가 진짜 장점을 가지기 위해서는, 보조적인 index구조를 가져야 한다. 이 보조적인 index 구조는, 따로 저장할 필요는 없고, primary structure에 이미 저장된 string들의 collection에 구현된다.
예를 들어, S가 S[0], S[1], ..., S[s-1]의 배열이라 하자. 한 노드에 char들을 바로 적지 말고, (i, j, k) 로 적어넣는다. 이것은 S[i][j..k]를 의미하는 것으로, S[i]의 j~k 번째의 substring이라는 의미이다.
Compact Representation
3) Suffix tries
한 String X에 대한 Suffix trie는 X의 모든 suffix들의 compressed tire이다. (suffix tree, position tree라고도 한다.) Trie이기 때문에, 한 suffix가 다른 suffix의 prefix가 되지 않게 하기 위해서, 기존의 ∑에 없던 문자 $를 suffix 뒤에 붙인다. 예를 들어, X가 "amizemize" 라면, 뒤의 mize는 mizemize의 prefix가 될 수 있기 때문이다. 그러나, mize$는 mizemize$의 suffix이기는 하지만 prefix는 아니다.
그리고 compact representation은 더 간단하다. (i,j)로 나타낼 수 있는데, 이것은 X[i..j]를 가리킨다.
Suffix Trie for "minmize" and its compact representation
⊙ Saving Space
string의 길이가 n일 때, 전체 suffix들의 길이의 합은,
1+2+3+...+n = n(n+1)/2
이므로, suffix들을 저장하는데 드는 공간은 O(n²)가 된다. 하지만, implicitly O(n) 의 공간이 사용된다.
⊙ Suffix trie 만들기
전체 suffix들의 길이는 string의 길이를 n이라 할때, O(n²)이다. 따라서, standard trie와 같은 방법으로 만들면 O(dn²)의 시간이 걸린다. 그러나 compact suffix trie는 O(n) 시간안에 만들어지지만, 복잡해서 여기에서는 다루지 않는다.
⊙ Using a Suffix Trie
arbitrary pattern matching을 지원하고, O(dm) 시간 걸린다.
