某储备粮的“学习笔记”

by 咳嗽di小鱼

Trapecho

Quickweb OpenVZ安装PPTP VPN实践笔记(不用MPPE)

Author: 咳嗽di小鱼 Date: April 22, 2011 Category: Network 7 Comments

从回国之前, 一直倒腾到家`可算是把VPN搭好了...
OpenVZ的VPS在内核这块实在是缺少自由, 如果是Xen这次就不会这么复杂了.
废话少说.

基本过程和网上其他的教程都差不多, 主要在于加密和ipforward的配置.

  1. 安装ppp和iptables



    yum install -y ppp iptables

  2. 安装pptpd



    wget http://poptop.sourceforge.net/yum/stable/packages/pptpd-1.3.4-2.rhel5.i386.rpm 
rpm -ivh pptpd-1.3.4-2.rhel5.i386.rpm

Read more...

Compiler各个步骤的含义

Author: 咳嗽di小鱼 Date: April 18, 2011 Category: Sum Up No Comments

Step1: String -> Scanning (DFA) -> Tokens Scanner又叫Lexical analyzer或Lexer.

其目的在于, 将需要compile的源代码逐字读入compiler, 并将每一个符合"词汇命名规则(Lexical Syntax)"的字段转换成token存储.
换句话说, 就是一遍读, 一遍看每一个单词的拼写对不对. 对的就转成token, 拼错了就输出error.

作业中对应: A6 P4
(某些语言的compiler在Scanning之后还包含Preprocessing, 因为不在241讨论范围内, 不做解释)

Step2: Tokens -> Parsing(LL/LR) -> Intermediate Format (WLI)

Parsing又叫Syntactic Analysis.
其目的在于, 将token与token联系在一起, 并将他们的转换成符合一定规范的"中间格式", 一般是某种树状结构, 例如241中定义的WLI.

在Parsing过程中, 如果遇到不符合某种语言的"语法规则(Grammar)"时, 则输出error. 如果语法正确, 则输出对应格式.
简单说, 就是看的说的话是不是人话, 有没有缺个标点少个括号.
如果不是人话那就说明你该重新学语法去了.

作业中对应: A8 P4

Read more...

LR(1) Parser Example

Author: 咳嗽di小鱼 Date: April 18, 2011 Category: Sum Up No Comments

Terminal Symbols: 6个

BOF, EOF, id, -, (, )

Nonterminal Symbols: 3个
S, expr, term

Start Symbol:
S

Production Rules: 5个
0 S BOF expr EOF
1 expr term
2 expr expr - term
3 term id
4 term ( expr )

Read more...

CS 240复习总结之九: Compression

Author: 咳嗽di小鱼 Date: April 11, 2011 Category: Sum Up 30 Comments

概念就不说了, 啥压缩比啊, logical/Physical compression, Lossy/Lossless的.

Run-Length Encoding (RLE)

思路: 将连续的0或1用位数表示, 缩减重复段所占的位置
  • 第一位表示由0或者1开头
  • 之后用prefix-free integer encoding表示每一个Run的长度
    • 后x位表示这个run的binary长度
    • 前x-1位填零, 为unary表示后x位的长度减一


Huffman Coding


思路: 用特殊的binary编码表, 省略ASCII/UTF-8编码中无用字符所占用的位置
  • 用binary trie表示字典中的所有字符
  • 将文本依照trie转成binary

如何建立压缩比最好的trie
  • 将每个字符存入独立的trie中
  • 确定每个字符的出现次数(频率), 一个trie的比重(weight)即为trie中字符的频率和
  • 将weight最小的两个trie合并成一个新trie
  • 重复上一步直到只剩下一个trie

Read more...

CS 240复习总结之八: Tries & String Matching

Author: 咳嗽di小鱼 Date: April 8, 2011 Category: Sum Up 2 Comments

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/