Symbol table

各种树的变种 为了适应不同的应用场景, 人们使用不同的树结构来实现符号表. 九宫格输入法 对于手机的九宫格输入法, 简单的实现方式是多次敲击: 通过反复按键输入一个字母，直到出现所需的字母。 但 http://www.t9.com/ 的 T9 texting 支持更高效的输入方法: ・Find all words that correspond to given sequence of numbers. ・Press 0 to see all completion options. Ex. hello ・多次敲击: 4 4 3 3 5 5 5 5 5 5 6 6 6 ・T9: 4 3 5 5 6 可以使用 8-way trie 来实现. 三元搜索Trie R较大的R-way trie的空间效率不高，读取比较大的文件往往导致内存不足。但弊端是开辟出的数组内存利用率其实不高。现在很多系统都使用Unicode，分支可高达65,536. 所以需要更高效的方法。 Ternary search tries: ・Store characters and values in nodes (not keys)....

符号表 在计算机科学中，符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。 常用哈希表来实现. 符号表的应用非常广泛, 可用于实现Set, Dictionary, 文件索引, 稀疏向量/矩阵等数据结构和相关的运算操作, 还有其他如过滤查询(Exception filter), 一致性查询(concordance queries)等操作. 字符符号表就是专门针对字符操作的符号表, API: Prefix match - Keys with prefix sh: she, shells, and shore. Wildcard match - Keys that match .he: she and the. Longest prefix - Key that is the longest prefix of shellsort: shells. public interface StringST<Value> { StringST(); create a symbol table with string keys void put(String key, Value val); put key-value pair into the symbol table Value get(String key); value paired with key void delete(String key); delete key and corresponding value Iterable<String> keys(); all keys Iterable<String> keysWithPrefix(String s); keys having s as a prefix Iterable<String> keysThatMatch(String s); keys that match s (where ....