8. Tries

1. R-way tries

 

Symbol table의 검색은 크게 red-black BST, hash table을 통하여 이루어 질 수 있었다.

Hash table은 constant time의 검색/삽입/삭제를 지원하지만, ordered operation이 불가능하였고, red-black BST는 ordered operation이 가능하지만, logarithmic time의 검색/삽입/삭제가 이루어 졌다.

특별히 Symbol table의 Key가 String인 경우 우리는 character의 갯수가 R로 제한되어있다는 것을 이용하여 red-black BST보다 성능을 더 향상시키면서 ordered operation을 가능하게 할 수 있다.

 

tries라는 이름은 retireval 로부터 나왔고, 우리는 try라고 부른다.

R-way tries는 tree 구조를 가지며, 각 node가 가지는 link의 갯수는 R이다(R은 radix)

하나의 link는 하나의 character를 의미하고 다음 node를 가리킨다. node는 하나의 value만을 저장할 수 있다.

 

다음은 R-way tries의  node구현이다.

 

private static class Node {
    private Object value;
    private Node[] next = new Node[R];
}

 

출처 : Wikipedia

 

검색의 경우, root node부터 시작해 String의 첫번째 character가 존재하는지를 찾는다. character은 그 자체로 R개의 link중 하나를 가리키는 index이고, 해당 link가 null link가 아닌 경우 recursive하게 탐색을 계속 한다.

검색 중간에 null link를 만나거나 마지막 character의 검색에서 node의 값이 null value일 경우, search miss로 본다.

 

예를들어, She를 검색하는 경우, root의 children node들 중 s는 null link가 아니므로, s가 가리키는 children node로 넘어가고 h를 검색한다. h 또한 null link가 아니므로, h가 가리키는 children node로 넘어간다. e는 마지막 character이고 값이 null value가 아닌 0이므로, She의 값은 0이 된다. 이 경우, String의 legnth인 L번 탐색이 이루어졌다.

search hit인 경우 이렇듯 character access횟수는 L이다.

이는 red-black BST의 L + c(logN)^2보다 우수하며, hashing에서 L과 동일하다.

 

만약, Skill을 검색하는 경우, root의 children node들 중 s는 null link가 아니므로, s가 가리키는 children node로 넘어가고 k를 검색한다. 그런데 k는 null link이므로, search miss이고 탐색을 조기에 종료한다.

search miss인 경우 이렇듯 character access횟수는 L보다 적을 수 있다. 평균적으로 log(R)N의 시간이 걸린다(R은 base, N은 String갯수).

이는 red-black BST의 c(logN)^2보다 우수하며, hashing에서 L보다는 약간 부족하다.

 

R-way tries은 ordered-operation을 제공하면서  red-black BST보다 search hit/miss, insert의 경우 모두 더 나은 성능을 보여준다.

한가지 문제점은, node가 R개의 link를 가진다는 점이다. 사용되지 않는 null link가 많을 수록 공간의 낭비는 심해지는데, leaf node가 총 N개 경우, leaf node 총 RN개의 null link를 가지게 된다. 이것은 특히, R의 크기가 클 수록 심각한 공간의 낭비를 가져오게 되어 Unicode의 경우 out of memory현상이 일어날 수 있다. 이론적으로 (R + 1)N만큼의 공간을 사용하게 된다. 이것은 4N정도의 공간을 사용하는 red-black BST에 비교해도 매우 큰 수준이다.

 

2. Ternary search tries

 

Ternary search tries는 각 node가 3개의 link를 갖는 search tree이다.

node는 하나의 character와 그에 대응하는 하나의 value를 저장하며, 3개의 link를 갖는다.

R-way tries에서 탐색시 character자체가 key가 되어 탐색 link를 선택했다면, Ternary search tries에서는 key의 값이 node의 character값 보다 작을 경우 left link로 탐색하고, 같을 경우 middle link, 클 경우 right link로 선택하여 탐색한다.

탐색의 종료는 R-way tries와 동일하게 검색 중간에 null link를 만나거나 마지막 character의 검색에서 node의 값이 null value일 경우, search miss로 본다.

 

다음은 tenary search tries의 node 구현이다.

 

private class Node {
    private Value val;
    private char c;
    private Node left, mid, right;
}

 

출처 : coursera, Princeton University Algorithm part2 lecture

 

예를 들어, shore를 검색한다고 해보자. 참고로 root를 제외한 모든 node는 3개의 children을 갖는다.

첫번째 문자 s와 정확히 일치하는게 있으므로, s에서 middle link를 통해 h로 이동한다. 

두번째 문자 h와 정확히 일치하므로, middle link를 통해 e로 이동한다.

세번째 문자 o가 e보다 크므로, right link를 통해 o로 이동한다.

세번째 문자 o와 정확히 일치하므로, middle link를 통해 r로 이동한다.

네번째 문자 r과 정확히 일치하므로, middle link를 통해 e로 이동한다.

마지막 문자 e과 정확히 일치하므로, 값은 해당 node의 값인 7이다.

 

apple을 검색한다고 해보자.

첫번째 문자 a보다 s가 더 크므로, s에서 left link를 통해 b로 이동한다.

첫번째 문자 a보다 b가 더 크므로, left link를 통해 a로 이동한다.

첫번째 문자 a와 정확히 일치하므로, middle link를 통해 r로 이동한다.

두번째 문자 p보다 r이 더 크므로, left link로 이동한다. 그런데 left link는 null link이므로 탐색을 종료하고 search miss로 판정한다.

 

Ternary search tries는 node의 link의 갯수가 3으로 고정되어 있으므로, radix에 관계없이 상대적으로 공간낭비가 적다. Red-black BST와 같은 4N정도의 공간만을 가져가면서, 성능의 경우 R개의 link를 가져가는 R-way tries보다는 상대적으로 떨어질 수 밖에 없지만, red-black BST보다는 우수하며 . 만약, rotation을 통해 Tree의 balance를 유지시킨다면, worst case에서 L + logN의 성능을 보장한다. 

 

R-way와 Tenary방식을 혼합한 hybrid방식도 활용할 수 있는데, 예를 들어 root를 첫번째와 두번째 문자열인 aa, ab, ..., zz를 가리키는 R^2의 link를 갖도록하고 하위의 node는 다시 Tenary search tries의 node를 갖도록 할 수 있다. 이런식으로  약간의 공간비용만으로 성능을 꽤 향상시킬 수 있다.

 

3. Character-based operations

 

String symbol table의 경우 몇가지 operation을 제공하는데, prefix match, wildcard math, logest prefix 과 같은 것들이다.

 

String symbol table의 API는 다음과 같은 것들이 있다.

 

StringST()

void put(String key, Value, val)

Value get(String key)

void delete(String key)

Iterable<String> keys()

Iterable<String> keysWithPrefix(String s)   //s를 prefix로 가지는 String찾기

Iterable<String> keysThatMatch(String s)

String logestPrefixOf(String s) //s와 공통의 prefix를 가지는 것들 중 가장 긴 prefix를 가지는 String찾기

 

정렬된 순서로 Key를 꺼내는 방법(ordered iteration) 은 tries에서 inorder방식으로 traversal하면서 node에 value가 존재할 때마다 queue에 key값을 넣음으로서 구현할 수 있다.

 

Prefix match는 검색창에서 검색할 때 자동완성기능에서 앞에 몇글자만 입력해도 추천검색단어가 뜨도록 할 때 사용된다.

이것은 tree에서 prefix까지 탐색하고 바로 이후의 character node를 root로 설정하여 ordered iteration을 수행함으로서 구현할 수 있다. 

 

Longest prefix는 network routing에서 사용되는데,  routing table에서 longest prefix로 매칭되는 주소로 패킷을 라우팅시켜 보낸다. 이것은 prefix를 탐색하면서, 가장 긴 prefix를 지속적으로 추적함으로서 구현가능한다.

 

또 한가지 응용으로 Patricia trie가 있다.

여기서 각각의 node는 sequenceof characters를 가진다.

따라서 이를 이용하면, suffix tree를 만들 수 있는데 각각의 link는 suffix를 가리킨다.

앞서 공부했을 때 radix sort를 이용하지 않고, suffix tree를 만들면 substring문제를 linear time으로 구할 수 있다고 하였다. 이는 Biology database등에 응용된다...