无损压缩
1. 行程编码(Run Length Encoding,RLE)
压缩原始数据中相同、重复的部分
2. 霍夫曼编码(Huffman Coding)
出现概率大的
分配短码
, 出现概率小的
分配长码
步骤:
- 按概率递减排列
- 把两个最小的
概率值
合并,作为新符号概率 - 重复 step1 和 step2 ,直到概率和 = 1
- ...
注意:
- 允许交叉
概率大的分支
写1
,概率小的分支
写0
,如果概率相等就 左1
右0
- 写
对应编码
时,从根出发,走最短路径
3. 算术编码
每次编码会得到一个[0,1)
的小数。(无限细分概率区间)
实际是: 多重概率合并计算 (那个小数 = 连续输这一串数据的概率)
例如:
小数变二进制: 乘2取整
4. 字典编码(Dictionary Coding)
- 方式一,用
内存指针
指向重复字符(方式二 dict 方法的本质) - 方式二,自动创建 dict,输出 index,而不是原数据
Questions
我这里第一题的答案是错的,你可以按照你自己的想法自己再做一遍
注意 1 - 0
,0.5 - 0
, 0.375 - 0.25
只是一个区间,它们的值还是取决于符号的概率
比如: