某储备粮的“学习笔记”

by 咳嗽di小鱼

概念就不说了, 啥压缩比啊, 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/


30 comments »

  1. 整个博客全是算法什么的?
    太猛了.
    这个是压缩的基本算法吧,转了.

    1. 额`...我正在期末考试, 这个是复习总结= =`
      博客主要是随手记一些平时瞎折腾时候碰到的问题, 省的以后再用的时候找不到, 哈哈
      欢迎转载

    2. 虽然自己不可能写个压缩算法出来,但是学了这个对程序设计绝对有用,呵

    3. 对啊, 所以虽然这门课学的有点头疼, 可还是好好复习整理一下, 以后用的时候就方便了.

    4. 课程名是?

    5. CS 240: Data Structures and Data Management
      http://www.student.cs.uwaterloo.ca/~cs240/w11/

    6. 滑铁卢大学 留学 Android IT专业 日本动漫
      呵呵,留字后面,我和你一样..

    7. 哈哈`大家都是技术宅...

    8. 晚上9点啦,你几点睡?

    9. 其实是11点40了...`
      还在复习, 准备睡了...这两天依然在考试

    10. 加拿大不是GMT-8么?夏令时再-1,
      15个小时的时差,错在哪里了?

    11. 哦,加拿大是多时区的...

    12. 西岸是-8, 我是东岸 -5.
      夏令时+1, 现在是-4`

    13. 还是错了...
      Whatever,不早了,不打扰你休息了.Have a nice dream!

    14. thx`night

  2. 强悍的你们。

  3. 技术盲的路过!

  4. Cherry Cherry

    这学期学的240好痛苦。。 感谢分享!
    另外想请教一下三年级除了cs341还建议选什么其他的课吗?
    谢谢!

    1. 341 350是必修吧? 348肯定要上. 349不推荐, 如果想上最好有和各种概念搏斗的心理准备. 343要上, 不过好像要求350. 370, 371这些我没上过.

    2. Cherry Cherry

      348一定有用么? 我看下学期的348的老师好差呃。。 担心学不到东西。。cs360学长推荐么?

    3. 348肯定要上. 老师不是一个口音很诡异的香港人的话, 应该问题不大= =...CS360没听周围人上过.

    4. Cherry Cherry

      额偏偏这学期好像就是内个香港人。。评分好低额。。叫Edward Chan 。。 这个老师的可以上么?

    5. 你可以先选上,听两节课,他的口音保证你听的如痴如醉,云里雾里的。(悄悄话: 想真的学明白database的话,就别上他的课了...)

    6. Cherry Cherry

      懂了。。 下学期好像有两个老师教。。另外一个老师好像挺好的。但是是第一次教这个课。 如果我去另外一个老师的section行不行呀? 会不会是内个很差的香港老师来出题呢?

    7. 这就说不准了...哈哈

  5. Cherry Cherry

    下学期除了348没其他课可以上了诶。。

Add new comment »

Enter your comment here...

captcha
请输入验证码