|
|
Last at : 2005-9-23 [ Deen  ] ( QQ : 66439797 ) ( MSN : Deen000@hotmail.com )
PS : 本人一直都对数据压缩有兴趣，最近整理了一下以前学习到的东西，继续有更新哦 ～～～ 大家多多交流分享。
高手们多多指点 ！！大家共同进步 ！！！
------------------------------
[一] 直观压缩 :
1. 日常生活中的缩写或者是简写都是减少重复信息量的工作。
2. 不可逆文本压缩 :
- 比如去除了一些重复的空格和一些不常使用的字符，但是却可能对整个数据源带来不可恢复的灾难。
3. 特定的文本压缩
- Baudot 码 :
使用一个键 （ 状态转换键，类似 Shift 键 ) 来切换数字和英文输入，从而得到更加多的编码范围。
4. 游程编码 :
- RLE 文本压缩
- 其 Len 可以比较灵活的变动，0 可以从起始值 3 开始，应此得到 255 = 258 更长的行程编码
- MNP5 [ Microcom Network Protocol ]
- 采用 3 个重复字符则进行编码处理，其缺点是单 3 个字符重复的时候扩展了，4 个重复则没有压缩。
- 字符对编码 ( digram encoding )
- 使用一些特定的符号来表示经常出现的数据，如 @a 来代替 "printf"
- 相关编码 :
- 使用差分来存放数据关系，如 : 温度 70, 71, 72, 73, 70 -> 71, 1, 2, 3, - 3
有时候差分过大，则会用原数据 ( 不用差分 ) 来表示，必须有标识来区别两者。
- RLE 图像压缩
- 通常会对颜色通道 ( R, G, B, A ) 进行分离，来获取更好的压缩率。
- 图形可以单个游程进行解码 ( 比如加入 eof 标识 )，让用户尽快的得到图像数据。
在合并图像的时候也不用进行解码就可以直接合并了。
- 最好能采用不同的行程遍历方法，线性的，非线性的，Z 字型的，这样来挑选最优的压缩方案。
- 可以对一些游程进行合并处理，比如 1,2,3,7,1,11,2 的游程，用户指定合并 <= 3 的编码
则最终如下 : 6, 7, 14 。而效果则只能由人眼来分辨了。
- ASCII 高位可以作为 CRC 码
- 前移编码 :
- 维护一个 A 表，将被使用都放入 A 表中，计数器自行维护，这样可以将常用的都编码到最小字节。
有时候不前移的效果更好，这个要自行判断，平均数( C ) 越小越好。
- 移动的长度是可以改变的，不一定都要移动到头部。
- 标量量化 :
- 可以使用截尾或者近似值来取代 ( 个人感觉像调色板来逼取近似值 )
( 如 : [ 0, 3, 6, 9 ] 7 就编码成 6，因为 6 比 9 更接近于 7 )
[一] 统计方法 :
1. 信息论思想 :
完全压缩 = log2(N) [ PS: 要得到可不容易也，最近用 RAR 作了比较，RAR 有的时候能 90% 的接近，真是强 ！]
2. 变长码 :
- 前缀性 : 别的编码的前部不能等于某个编码。
如 : 1, 01, 001, 010 就没有前缀性 ( 01 和 010 ) [ 解码中碰到 01 字段就不知道是谁的了 ]
而 : 1, 01, 001, 000 就有前缀性
原因是线性解码的时候无法识别是谁的编码，因此无法正确解压。
3. 前缀码 :
- 一元码 :
0 或者 1
10 01
110 001
1110 0001 ( 就是重复的 0 或者 1 最后再加入一个非 :P )
- 数字基 :
- Fibonacci 基 : 1, 2, 3, 5, 8, 13, 21 ...
比如 : 3 ( 01 )
8 ( 0011 )
12 ( 10101 )
10 ( 0111 )
- Golomb 码 :
- b = 2^m; q = int( ( n - 1 ) / b ); r = n - q * b; [ 注意 : 0 元素就一个编码 1 完事了 ]
- 第一部分 : q + 1 个一元编码 ，第二部分 : m 位二进制 ( r 值 )
( m 的值经验来说最好取 3 或者 4 ) [ From Benben 教程 :P ]
- 如 :
m = 3; n = 9; ( 01 | 000 )
m = 3; n = 10; ( 01 | 001 )
m = 3; n = 99; ( 0000000000001 | 011 ) ( 好长 :P )
- Kraft-MacMilan 不等式 :
- [ Deen : 此不等式比较复杂，请其他高手填充此栏目，本人能力有限，谢谢 ！]
- [ Deen : 对此有研究的人在回复中解释此不等式作用，谢谢 ！]
// to be continue ...
[ 参考书目 ]
1. Data Compression ( The Complete Reference, Second Edition ) [ 美 ] David Salomon [ 译 ] 吴乐南
2. 《笨笨数据压缩教程》 [ China ] 王咏刚 |
|
发表于 2005-9-23 23:17:00
楼主