String

各种树的变种 为了适应不同的应用场景, 人们使用不同的树结构来实现符号表. 九宫格输入法 对于手机的九宫格输入法, 简单的实现方式是多次敲击: 通过反复按键输入一个字母，直到出现所需的字母。 但 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 ....

虽然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, 这样就实现了不回头继续匹配了. 因为AC自动机是在Trie的基础上添加边, 用于指示各个节点经过不同字符后跳转到哪个节点, 结果就变成了图, 所以也叫做Trie图. 要构建AC自动机: 首先要把所有模式都吃进一个Trie中(最近看多进击的巨人了), 构建出一个由不同实线串联起来的状态机, 其中代表刚好吻合一个模式的状态标记为终结节点(如上图绿色节点) 然后补全其他字符的转移(失败转移), 用虚线表示. 补全了所有字符的转移方式, 才能让字符串永不回头地匹配下去, 避免了back up, 保证性能....

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....

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], 结果不匹配....

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....