信息无损性 模糊性 prefix-free codes Huffman codes shannon-fano codes using tries to convert compressed data into a original data longest prefix matching self-extracting bits

Overview Tries——前缀树/字典树 usages: prefix matching approximate matching 1 2 keysWithPrefix(String prefix) // returns all keys in the trie that start with the given prefix longestPrefixOf(String query) // returns the longest key in the trie that is a prefix of the query implementation 1 2 3 4 5 6 7 8 private class Node{ boolean exists; Map<Character, Node> links; public Node(){ links = new TreeMap<>(); exists = false; } } T9 keyboard Ternary search Tries 1 2 3 4 5 6 7 public class TSTSet<Value>{ private Node<Value> root; private static class Node<Value>{ private char c; private Node<Value> lo, mid, hi; } } 但是这种实现方式表现不佳

radix sort 不用comparisons的排序算法，时间复杂度O(dn)，d为最大数的位数，n为待排序数的个数。 空间换时间 bucket sort counting sort: 找出待排序数的最大值max，确定计数数组的长度为max+1。 遍历待排序数，将每个数的个位数值作为索引，将该索引对应的计数数组元素加1。 遍历计数数组，将每个元素的值作为索引，将该索引对应的元素值输出到结果数组中。 runtime: O(n+k) LSD radix sort: least significant digit radix sort 找出待排序数的最大值max，确定计数数组的长度为10。 遍历待排序数，将每个数的个位数值作为索引，将该索引对应的计数数组元素加1。 LSD sort vs merge sort: similar strings:LSD sort is better dissimilar strings:merge sort is better MSD radix sort: most significant digit radix sort 找出待排序数的最大值max，确定计数数组的长度为10。 遍历待排序数，将每个数的个位数值作为索引，将该索引对应的计数数组元素加1。 遍历计数数组，将每个元素的值作为索引，将该索引对应的元素值输出到结果数组中。 runtime: O(n+k)