CS 240复习总结之九: Compression
Author: 咳嗽di小鱼 Date: April 11, 2011 Category: Sum Up
概念就不说了, 啥压缩比啊, 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
MTF
- 用字典中, 字符的index表示字符
- 使用动态字典, 将出现过的字符移到字典开头, 以减小下次出现时该字符的index值
- MTF本身不能达到压缩的目的, 需配合prefix-free integer encoding或者huffman
LZW
思路: 给出现过的字符组assign编码, 在重复出现时以一个编码代表整个字符组
- 字典编码使用固定长度k, 字典总共有2k个entry
- 字典由所有单字符开头, 剩余entry留空
- 从第二个encode的字符[组]开始, 将其首字符与上一个encode的字符[组], 组成一个新的字符组, 并存入字典中
- 当这个字符组合再次出现的时候, 即可用一个编码代表整个字符组
BWT
思路: 不知道!!!!!!! 他tm就是work了`!!!不知道为什么!!!!
Encode方法:
- 将整个string S写成各种cyclic shift, 用$表示string结尾
- 比如abcd$可以写成abcd$, bcd$a, cd$ab, d$abc, $abcd
- 将所有cyclic shift排序
- 将排序后的所有cyclic shift的最后一位按顺序组合成新的string, 既是Encoded的string C
Decode方法:
- 给Encoded的string C的每一个字符一个序号, 从0到n-1
- 将字符和序号一起排序. 排序后的序号提取为Array N
- for(i = N[N[0]], i != N[0], i = N[i]) print(C[i]);
BWT本身不进行压缩, 而是将string转化成更容易被MTF压缩的Encoded string.
BWT以后, 执行MTF即可达到极佳的英文字符压缩比.
更多CS 240总结请看: http://blog.gregwym.info/tag/cs240/
整个博客全是算法什么的?
太猛了.
这个是压缩的基本算法吧,转了.
额`...我正在期末考试, 这个是复习总结= =`
博客主要是随手记一些平时瞎折腾时候碰到的问题, 省的以后再用的时候找不到, 哈哈
欢迎转载
虽然自己不可能写个压缩算法出来,但是学了这个对程序设计绝对有用,呵
对啊, 所以虽然这门课学的有点头疼, 可还是好好复习整理一下, 以后用的时候就方便了.
课程名是?
CS 240: Data Structures and Data Management
http://www.student.cs.uwaterloo.ca/~cs240/w11/
滑铁卢大学 留学 Android IT专业 日本动漫
呵呵,留字后面,我和你一样..
哈哈`大家都是技术宅...
晚上9点啦,你几点睡?
其实是11点40了...`
还在复习, 准备睡了...这两天依然在考试
加拿大不是GMT-8么?夏令时再-1,
15个小时的时差,错在哪里了?
哦,加拿大是多时区的...
西岸是-8, 我是东岸 -5.
夏令时+1, 现在是-4`
还是错了...
Whatever,不早了,不打扰你休息了.Have a nice dream!
thx`night
强悍的你们。
啊哈`晚上好...
- -
不用显摆时差吧
= =...`回家了
技术盲的路过！
这学期学的240好痛苦。。 感谢分享！
另外想请教一下三年级除了cs341还建议选什么其他的课吗？
谢谢！
341 350是必修吧? 348肯定要上. 349不推荐, 如果想上最好有和各种概念搏斗的心理准备. 343要上, 不过好像要求350. 370, 371这些我没上过.
348一定有用么？ 我看下学期的348的老师好差呃。。 担心学不到东西。。cs360学长推荐么？
348肯定要上. 老师不是一个口音很诡异的香港人的话, 应该问题不大= =...CS360没听周围人上过.
额偏偏这学期好像就是内个香港人。。评分好低额。。叫Edward Chan 。。 这个老师的可以上么？
你可以先选上，听两节课，他的口音保证你听的如痴如醉，云里雾里的。(悄悄话: 想真的学明白database的话，就别上他的课了...)
懂了。。 下学期好像有两个老师教。。另外一个老师好像挺好的。但是是第一次教这个课。 如果我去另外一个老师的section行不行呀？ 会不会是内个很差的香港老师来出题呢？
这就说不准了...哈哈
下学期除了348没其他课可以上了诶。。
先报上试一下吧`