某储备粮的“学习笔记”

by 咳嗽di小鱼

Tries

单词查找树 Tries (Radix Tree):

  • tries.png
  • 左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):

  • compressed_trie.png
  • 相比普通Tries, compressed tries去除了额外的node(只有一个child的node). 其他基本相同.
  • 每个node中增加了下一层Search中, 需要检测的位数

Multiway Tries:

  • multiway_tries.png
  • 以特定alphabet集合为基础, 建立的Tries
  • 通过$ sigh以允许prefix存在
  • 不是Binary Tree
  • 同样可以compress, 与Compressed Tries方法相同

String Matching 要match的string为T, pattern为P

Brute-force Algorithm

  1. 从前往后依次比对P的首字母
  2. 如发现与首字母匹配, 则继续比对剩下的字符直到P结尾
  3. 如P未结尾时出现不匹配, 则回到与首字母匹配位置的下一个, 继续比对首字母
  4. 如T结尾, 则无匹配

Boyer-Moore Algorithm

  1. 将T和P右对齐
  2. 从P的结尾开始, 依次向前与T比对
  3. 如遇到不匹配, 检查T该位置的字符是否在P中出现过

    • 如出现过, 则将该字符在P中最后出现的位置, 与T对齐
    • 如没出现过, 则讲P向后shift一个P的长度
    • 重复第二步
  4. 如T结尾, 则无匹配

KMP Algorithm

  1. 建立KMP Failure Array 位于j点的F(j)值等于P[1..j]的结尾与P的开头所重叠的字符位数 KMP.png
  2. 将T和P左对齐
  3. 从P的开头开始, 依次向后与T比对
  4. 如遇到P[i]不匹配, P向后shift[i - F(i-1)]位, 且 i 值assign为F(i-1)
  5. 如T结尾, 则无匹配

Suffix Tree (Trie) 与前几个Algorithm相反, 此Algorithm是为了在同一个T中寻找不同P而建立的.


Post-condition: T长度为n, i值为从0到n-1
1. 将所有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/


2 comments »

  1. 其实我看不懂你写的这些。
    :(

    1. 啊哈哈`最近期末考试...总结复习一下

Add new comment »

Enter your comment here...

captcha
请输入验证码