各种树的变种 为了适应不同的应用场景, 人们使用不同的树结构来实现符号表. 九宫格输入法 对于手机的九宫格输入法, 简单的实现方式是多次敲击: 通过反复按键输入一个字母，直到出现所需的字母。 但 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). ・Each node has 3 children: smaller (left), equal (middle), larger (right). Search in a TST: Follow links corresponding to each character in the key. ・If less, take left link; if greater, take right link. ・If equal, take the middle link and move to the next key character. ...

符号表 在计算机科学中，符号表是一种用于语言翻译器（例如编译器和解释器）中的数据结构。在符号表中，程序源代码中的每个标识符都和它的声明或使用信息绑定在一起，比如其数据类型、作用域以及内存地址。 常用哈希表来实现. 符号表的应用非常广泛, 可用于实现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 . is a wildcard) String longestPrefixOf(String s); longest key that is a prefix of s } 以Trie为基础的字符符号表 algs4中提供了用 R-way trie 来实现符号表(symbol table)例子: ...

虽然KMP可以用于单模式匹配问题，但如果是多模式问题, KMP的性能就得不到保证。比如根据墙内法律要求, 墙内的搜索引擎需要过滤敏感词后才能合法运营。敏感词的数量不少, 如果要求包含敏感词的网页不能被搜索到, 那么搜索引擎在爬取网页信息时, 就要标记网页的文本中是否包含任意个敏感词. 这就是典型的多模匹配问题. 这种情况下如果使用Trie，那么需要遍历网页的每一个字符位置，对每一个位置进行Trie前缀匹配。如果词典的词语数量为N，每个词语长度为L，文章的长度为M，那么需要进行的计算次数是在N*M*L这个级别的. 即使把词语的长度L简化为常数级别的, 整个算法的复杂度也至少是$O(n^2)$. AC自动机 可以看到，KMP算法可以避免back up（在检查字符的过程中不需要回头），而Trie可以存储多个模式的信息。如果把二者结合在一起，也许能从性能上解决多模式（任意位置）匹配问题。这就是Aho–Corasick算法（AC自动机）。 Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组字典中的子串。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。 所以算法的关键就是通过Trie把多个模式构建为一个DFA（Deterministic finite state automaton），然后让模式串末尾对应的状态作为一个DFA的终止节点。这样，对于一个要检查的长字符串（如一段网页内容），让这个字符串在DFA上跑一趟，每一个字符表示一种跳转方式，如果这段字符能够跳到任何一个终结节点, 那么就表明这段字符串匹配了至少一个模式, 如果整段字符跑完都没到达终结节点, 那么这个网页就是"和谐的". 在单模式匹配中, 用KMP构建的DFA是比较简单的, 从左到右, 开头的状态就是开始状态, 结尾的状态就是结束状态: 而多模式匹配中, 在Trie的结构基础上构建出来的DFA更像一个DFA的样子: Trie中的节点, 就类似于DFA中的状态. 如果让字符串shis在上面跑, 假如仅仅是靠Trie(也即是没有虚线标识的转移), 那么第一次从字符串的第一个字符s开始转移, 经过转移路径0 - 85 - 90之后就转不动了, 因为Trie记录的模式中没有shi, 这个时候得back up, 从第二个位置h开始再匹配一遍. 这个过程中就产生重复匹配, 而参考KMP的思路, 在匹配shi的过程中, 其实已经挖掘出了hi这个子串了, 而这个子串是跟模式his对应的, 如果有办法不回头继续匹配下去就能提高性能了. 而DFA中虚线的失败转移就是用来解决这个问题的: 当走到状态90时, 前面有了小部分子串h刚好对应状态74, 这个时候用虚线作为失败转移, 转移到74, 在状态74中寻找下一个转移i, 这样就实现了不回头继续匹配了. ...

Trie 也称字典树，名称来源于Retrieval，支持$O(n)$插入和查询操作，以空间换取时间的数据结构. 用于词频统计和输入统计领域, 可以高效地存储大规模的字典数据, 也可以用于模糊匹配, 搜索最长前缀词等. A trie, also called digital tree, radix tree or prefix tree is a kind of search tree - an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys tend to be associated with leaves, though some inner nodes may correspond to keys of interest. Hence, keys are not necessarily associated with every node. ...

Rabin-Karp Fingerprint Rabin-Karp fingerprint(RK) 基于 modular hashing： Compute a hash of pattern characters 0 to M - 1. For each i, compute a hash of text characters i to M + i - 1. If pattern hash = text substring hash, check for a match. 如果在一一比较中对text的每个子串都重新计算hash，那么速度比暴力算法还慢。 所以算法的关键在于如何高效地计算哈希值：Horner’s method - M阶多项式hash的线性时间方法 $$a^b \pmod c = (a \pmod c)^b$$ 引理： $$(a \times b) \pmod c = [( a \pmod c ) \times (b \pmod c) ] \pmod c$$即积的取余等于取余的积的取余. ...

In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. 字符串搜索/匹配算法在大规模文本应用中有非常重要的作用，比如文章敏感词搜索，多关键词过滤搜索等。如果使用暴力搜索，则时间复杂度很高（若 m 为关键字的长度， n 为要待搜索的字符串长度， k为关键字数量，则复杂度为$O(n \times m \times k)$。而好的算法可以让这些问题的时间复杂度大大降低。 常用的算法有Knuth–Morris–Pratt(KMP), Boyer-Moore(BM), Rabin-Karp(RK), Trie, Trie图, AC自动机等. 一个实例 匹配时，想象我们拿着模式字符串pat=ABABAC, 像尺子一样从左到右对齐依次匹配如图的txt。 从txt[i=0]开始, 把pat的开头pat[j=0]对齐txt[0], 开始比较pat[0]和txt[0], 发现不匹配, 暴力的算法是从txt下一个字符重新开始i=1, 同时把尺子也右移一位对齐新的txt起始点. 从i=3开始, 发现一开始可以匹配上(pat[j=0] == txt[3]), 那么保持尺子不动, 开始比较pat[j+1]和txt[i+1], 结果不匹配. 从i=4开始, 情况也类似, 而且发现连续匹配上了pat[++j]和txt[++i], 假如运气好, 我们能匹配完整个尺子, 那么达到目的. 可惜在i=7时失败了. 问题的关键就是i=3和i=7这里, 特别是i=7, 假如还是用暴力解法1操作, 那么需要重新比对txt[i=5,6,7...]. 但前面已经匹配了一半的尺子了, 那么其实我们已经知道了txt的后缀txt[4,5,6]和尺子的前缀pat[0,1,2]重合, 我们能否利用这个信息来优化算法? 按照前面的分析, 每一个已匹配的前缀等于txt中已匹配的后缀, 那么txt后缀后面可能接的字符有R种, 我们可以提前计算每一个已匹配txt后缀后接每一种字符时, 应该怎么做. ...

Boyer-Moore算法 在从头到尾对齐txt的字符时, 每一次对齐, BM算法反方向从尾到头检查patternP=BAABBAA和txt字符是否匹配。匹配过程中如果发现txt[i] != P[j], 也就说二者子串不相等, 如...XAA != ...BAA, 且字符txt[i] = X在P中不存在时，可以把P开头对齐到txt[i+7], 一次就跳过了7个位置. 模式相较于文本一般较短, 所以模式中包含的字符种类相对也比较少, 那么这样的跳跃出现情况就很可观了, 可以大大加速匹配. 不过一般来说, 可能txt的某些子串会和P的其他子串重合，不失一般性我们需要像Knuth-Morris-Pratt算法一样的重启位置数组。 Bad Character Heuristic(BCH) 重启点位: 预先计算各个字符c在Pattern的最rightmost的位置(若无则-1), 这些位置告诉我们如果是txt中的字符c导致不匹配, pattern可以右移的距离. badCharacterPreprocess(String pat) { // Compute skip table. this.pat = pat; int M = pat.length(); int R = 256; right = new int[R]; for (int c = 0; c < R; c++) right[c] = -1; // -1 for chars not in pattern for (int j = 0; j < M; j++) // rightmost position for right[pat.charAt(j)] = j; // chars in pattern } 有了right数组后, 一个例子说明匹配过程: ...

如何实现快速的幂运算？ 要求$c = a^b$, 按照朴素算法把a连乘b次的时间复杂度是$O(n)$. 而快速幂能做到$O(\log n)$。把b转换为二进制, 二进制数第i位的权为$2^{i-1}$，就可以把二进制拆分为若干个以2为底的真数, 然后利用幂数的性质，例如用朴素算法求$a^{11}$要求乘11次. 考虑到11的二进制为1011, 如果把$a^{11}$拆分为: $$a^{11} = a^{a_0 2^0 + a_1 2^1 + a_2 2^2 + a_3 2^3} = a^1 a^2 a^8$$ 可以看到每一个因子都是上一个因子的平方，利用$a^2 a^2$求出$a^4$, 同样利用$a^4$的平方求出$a^8$, 每次计算只需要用到上一次计算出来的结果, 所以总的运算次数是4次. 任何一个数b最多能写成长度为$O(\log b)$的二进制, 因此这个算法就是$O(\log n)$. 在程序设计中是根据b的二进制中是否为1来控制是否乘以上一次翻倍的积 不断右移b, 直到b不再有1： 根据当前位的权重（当前b最后一位）是否为1来决定c是否乘以最新的a 把a平方，用于下一位计算 在Java中要考虑极端值INT_MIN // 递归 public double myPow(double x, int n) { if(n==0) return 1; double temp = myPow(x, n/2); if (n % 2 ==0) return temp * temp; else { if(n > 0) return x*temp*temp; else return (temp*temp) / x; } } // 循环 public double myPow(double x, int n) { double ans = 1; if(n < 0){ n = -(n+1); // 处理极端值 x = 1/x; ans *= x; } System.out.println(n); while (n > 0) { if ((n & 1) == 1) ans *= x; x *= x; n >>= 1; } return ans; } 快速幂取余 求a^b mod c. 如果b是偶数, a^b mod c = $(a^2)^{b/2} \% c$ 如果b是奇数, a^b mod c = $((a^2)^{b/2} \times a) \% c$ ...

“找出只出现一次的数”， “找出唯二的只出现M次的数”， “找出缺失的数”等等这类问题，都可以利用异或操作的特性， 即一个整数和自己进行异或运算会归0的性质。 找出缺失的数字 问题1：给定一个包含n个不同数字的数组，取自0,1,2,...,n，找到数组中缺少的数字。 最直觉的解法是利用等差数列的性质直接数学求解。但这个方法限制于等差数列. 问题2: 在一个长度为n的数组里的所有数字都在0 ~ n-1之间, 数组中有些数字是重复的, 找出任意一个重复的数字. 这也是«剑指offer»的一道题. 但是如果利用数组大小和元素范围的特性, 就可以发现, 这里的数组的大小和数字的范围是有限定关系的. 对于第二个问题, 假如没有重复, 那么重新排列的话数组每一个位置都可以放上自己对应的数字. 对于第一个问题, 假如没有缺失, 那么除了每一个index都可以重新放上自己对应的数字外, 还会多出一个最大的数字没地方放. 这样就可以把数组包含的数字解读为index, 然后在遍历检查数组时, 同时检查以各个数字为index的其他位置的数字. 使用这种思路可以同时解决两个问题, 这里以问题1解法为例: public int missingNumber(int[] nums) { int n = nums.length; int misP = n; // points to the position where misssing. for (int i = 0; i < n; i++) { while (i != nums[i] && nums[i] != misP) { int j = nums[i]; nums[i] = nums[j]; nums[j] = j; } if (nums[i] == misP) misP = i; } return misP; } 找出只出现一次的数 问题3：在一个非空整数数组，找出那个只出现了一次的元素，已知其余每个元素均出现两次。 ...

求两个整数的汉明距离 hamming distance Leetcode 461 两个整数之间的汉明距离是该两个数之间不同的位数。 给定两个整数x和y，计算汉明距离。问题也可以理解为对于两个整数m和n, 需要改变m的二进制多少位才能得到n: /** Use Brian Kernighan's way to count bits */ public int hammingDistance(int x, int y) { x = x ^ y; y = 0; while(x != 0){ y++; x &= x - 1; } return y; } public class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } } 同样用到Brian Kernighan算法： ...