- 指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法进行组织。
结课形式：小论文
参考书：
- 《数据压缩导论》（第四版，Khalid Sayood）
- 《数据压缩》（吴乐南）
信息熵：
$H(i) = -log_2 (P_i)$
其中$P_i$是发生$I$事件的概率
- 统计模型
- 静态/半静态模型
- 自适应模型
- 字典模型
- 静态字典模型
- 自适应字典模型
通用数据压缩方法（无损）
Shannon-Fano编码
- 与huffman编码相反，采用从上到下的方法
- 步骤
- 根据字符集中的字符按照出现频度和频率进行排序
- 用递归的方法分成两类，使得两部分的频率和接近于相等。直至不可再分，即每一个叶子对应一个字符。
- 开始编码
霍夫曼编码
- 步骤
- 概率统计
- 将n个信源信息符号的n个概率，按概率大小排序
- 将n个概率中，最后两个小概率相加，这时概率个数减少为n-1个
- 将n-1个概率按大小排序，继续按照最小两个概率相加
- 重复上述3-4步骤，直至生成树
- 局限性
- 符号的编码长度只能为整数
- 输入符号首先与可实现的码表尺寸
- 编码复杂
- 需要事先知道输入符号集的分布
- 变种：范式Huffman编码
- Huffman子集
- 加约束条件，遵守一些规则
- 使用很少的数据便可以重构出编码树，可以有效减少编码字典的存储空间
算术编码
游程编码
Golomb编码
