数据压缩—导论+通用无损压缩方法

Posted by MetaNetworks on September 28, 2021
本页面总访问量

  • 指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法进行组织。

结课形式:小论文

参考书:

  • 《数据压缩导论》(第四版,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编码