http://blog.gregwym.info/tag/tries/ http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-ba--tries-and-string-matching.html 2011-04-09T06:12:41+08:00 Tries单词查找树 Tries (Radix Tree): 左0右1 item只存在leaf上 Prefix-free: 任意一个key不能有其他key是他的前缀(比如: 1101和11011不能共存) Search: 逐位执行BS Insert: 逐位执行BS 如果找到某leaf与insert的item不等, insert fail. (现存item是新item的prefix) 如果在某个node搜索结束, insert fail. (新item是其他key的prefix) 如果无路可走了, 开路出来. Delete: Search到对应item以后, 删除这个leaf以及其他无用的node. Compressed Tries (Patricia Tries): 相比普通Tries, compressed tries去除了额外的node(只有一个child的node). 其他基本相同. 每个node中增加了下一层Search中, 需要检测的位数 Multiway Tries: 以特定alphabet集合为基础, 建立的Tries 通过$ sigh以允许prefix存在 不是Binary Tree 同样可以compress, 与Compressed Tries方法相同 String Matching 要match的string为T, pattern为PBrute-force Algorithm 从前往后依次比对P的首字母 如发现与首字母匹配, 则继续比对剩下的字符直到P结尾 如P未结尾时出现不匹配, 则回到与首字母匹配位置的下一个, 继续比对首字母 如T结尾, 则无匹配 Boyer-Moore Algorithm 将T和P右对齐 从P的结尾开始, 依次向前与T比对 如遇到不匹配, 检查T该位置的字符是否在P中出现过 如出现过, 则将该字符在P中最后出现的位置, 与T对齐 如没出现过, 则讲P向后shift一个P的长度 重复第二步 如T结尾, 则无匹配 KMP Algorithm 建立KMP Failure Array 位于j点的F(j)值等于P[1..j]的结尾与P的开头所重叠的字符位数 将T和P左对齐 从P的开头开始, 依次向后与T比对 如遇到P[i]不匹配, P向后shift[i - F(i-1)]位, 且 i 值assign为F(i-1) 如T结尾, 则无匹配 Suffix Tree (Trie) 与前几个Algorithm相反, 此Algorithm是为了在同一个T中寻找不同P而建立的.Post-condition: T长度为n, i值为从0到n-11. 将所有T[i..n]依次insert进Compressed trie 2. 因为Compressed trie的性质 (prefix-free), 如果某一个T[i..n]是已有node的prefix, 则不会被insert 3. 每个node和leaf中, 保存对应的i和n值 4. 在Compressed trie中搜索, 将P与每个node进行比对. (长度以P为准) 5. 如果遇到node长度小于P长度, 则无匹配.= =`最后一个Module后天再说...每天都看Algorithm会死人的`明天收拾251更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/