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