Assignment10.5 Tries

Tries

0. 如何阅读

大家(包括TA)期末都比较忙, 这次的分享比较简单. 大家看一下,知道有这么个东西就好了.

代码示例是Java, 考虑到没有用到很特殊的的东西. 应该都看得懂. 助教就不帮大家翻译成C++了.

1. 定义

Tries 在课本P173

通常用来处理字符串.

2. 应用场景

1. 求匹配前缀, 举个应用场景,比如 在IP路由的时候, 目标地址 128.112.136.12, 路由器在进行转发的时候, 会在路由表记录中查找最长匹配的前缀. 将其发送到对应下一跳路由.
2. Symbol Table, 比如(上图)统计单词出现个数, 当出现单词to, put("to", get("to") + 1) 上图可表示tot 出现了7次. A 出现了15次 in 出现了 5次.

3. 空间&时间

1. R-way tries
   这也是课本中的方案, 其特点是每个节点开一个字符集大小的数组. 最终总的空间开销为 O(|Σ|*N) , 查询时间开销为O(|STRING|). N为树的节点数

2. Ternary search tries 一个节省空间的方案, 最终空间开销 O(N), 查询开销最差为 |Σ|*|STRING|

   private class Node {
       private char c;                 // character
       private Node left, mid, right;  // left, middle, and right subtries
       private Value val;              // value associated with string
   }
   
   
   private Node put(Node x, String s, Value val, int d) {
       char c = s.charAt(d);
       if (x == null) {
           x = new Node();
           x.c = c;
       }
       if      (c < x.c)             x.left  = put(x.left,  s, val, d);
       else if (c > x.c)             x.right = put(x.right, s, val, d);
       else if (d < s.length() - 1)  x.mid   = put(x.mid,   s, val, d+1);
       else                          x.val   = val;
       return x;
   }
   
   
   

4. 总结&代码

Ternary search tries的查询效率问题, 在Fast Algorithms for Sorting and Searching by Bentley and Sedgewick. 通过比较实现Symbol Table 和Hash的效率进行比较. 得出TST更加优秀的结论.

这张表格看看~ 应该已经有感性认识, 具体内容到[论文](Fast Algorithms for Sorting and Searching by Bentley and Sedgewick里去看吧

Algorithm	Data Structure
QuickSort	Binary Search Trees
Multikey QuickSort	Ternary Search Trees
MSD Radix Sort	Tries

1. R-way-tries
2. Ternary search tree