Compression

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即可达到极佳的英文字符压缩比.


转载自:http://blog.gregwym.info/cs-240-fu-xi-zong-jie-zhi-jiu--compression.html

标签:压缩

已有 2 条评论

  1. 虽然我看不懂是什么。不懂这个技术!
    但还是坚决的支持博主!

  2. 匿名 匿名

    不错啊!真的很好!

添加新评论