压缩、去重等技术调研
主要用于我自己学习过程中记笔记，便于以后回忆，因此阅读性很差
于2020年新肺炎疫情长假期间，成都双流
阅读内容：
1、书籍：吴家安《数据压缩技术及应用》
2、论文：夏文《数据备份系统中冗余数据的高性能消除技术研究》一、导论数据压缩的分类其中一种：冗余度压缩、熵压缩（无损、有损） 压缩的性能指标压缩能力：
压缩比：输出：输入
压缩因子：输入：输出
压缩效率
压缩增益
速度
信号质量：
客观量度：信噪比（SNR，db）、均方差（MSE）等
主观量度 二、数据压缩的信息论基础主要讨论 离散无记忆信源
不确定性越高（概率低），其信息量越大 信息的定义打公式太麻烦了，下文均省略，而且缩进也特别麻烦
信息定义的公式：-log（概率倒数） 互信息和自信息互信息公式略
A和B相互独立时，互信息显然0
自信息就是本身的信息，A决定B时，二者互信息为自信息 熵公式：平均自信息
熵非负
确定性事件熵为零
当信源所有输出符号等概率时，熵取最大值，log^n 信源编码定理 一个输出n个符号的离散无记忆信源，其信源符号不可能用平均码长小于该信源熵的单义可译码来表示：
H(X) <= L，L为平均码长 信道容量通过一个信道所能传输的最高信息速率
时间T内输出与其相应输入的互信息之和之商，bit/s 信道编码定理（香农第二定理）若信源以速率R发送信息，信道容量为C，若R<C，采用完善的信道编码器、解码器就能以任意小的差错概率，用最高C的速率传输数字信息。相反，若R>C，则使用任何编码器、译码器都达不到任意小差错概率，而必定会大于某个正值 率失真理论数据压缩的极限值，找出一个条件概率使平均互信息最小 三、统计编码3.1 概述变长码唯一可译性
即时可译性
变长码码字即时唯一可译条件：异前缀码 最佳变长编码定理码字长度与概率顺序相反 3.2 香农-范诺编码将符号按概率降序排列 将符号集合分为概率基本相等（差最小）的两个集合，把0分给第一个，1给第二个 重复步骤2直至每个符号都分裂成叶子
3.3 霍夫曼编码众所周知：自下而上构建二叉树
霍夫曼编码的平均码长：除叶子节点外的所有节点的概率相加即为平均码长
与香农-范诺编码的比较： 当概率不均为2的负次幂时，霍夫曼编码的效率高于香农-范诺编码（此时log^p不为整数，由信源编码定理可知平均码长大于熵且为整数，效率低于100%；香农-范诺编码有可能产生非最优编码） 当概率均为2的负次幂时，二者编码效率都是100%（此时log^p为整数，平均码长等于熵）
自适应霍夫曼编码字符的频率是动态变化的，因此编码器和译码器要同步、一致，二者都动态地调整霍夫曼树，每编码（解码）一个字符就要调整树。编码器先编码再改变频率（当前字符频数 1），解码器先解码再改变频率，以此来保证编码和解码所用的霍夫曼树是一致的。 3.4 行程编码也称为“游程编码”。
定长的行程编码结构为：X,S,RL
其中X为字符；S是一个在数据集合中不用的字符，起一个异字头的作用；RL表示行程长度，也就是X出现的次数。
可见RL>3才有压缩效果。
变长的行程编码需要增加标志位信息来表示编码的起止位置。 变长编码的可靠性以上讨论的三种变长编码对传输误差都存在脆弱性，一步错步步错，且解码器不自知。尤其是行程编码，一旦错一个位都会导致整个行程移位。可参考的解决办法是每几位加一个奇偶校验码等等，用压缩比来换取可靠性。 3.5 算术编码真是巧妙的算法，我何时能提出一个这样的算法 ：） 编码原理初始分配一个[0,1)区间，按信源输出字符的概率对其进行划分，使每一个字符都对应一个唯一的区间。编码时，每次把当前字符的区间分配为码字，重复下去，最终得到一个区间就是该字符串的编码。解码时，查看码字区间属于哪个字符，依次迭代直到迭代出与码字相同的区间即为结束。即为：
high(n 1) = low(n 1) range x high_range(x)
low(n 1) = low(n 1) range x low_range(x)
其中，range = high(n) - low(n)，high、low_range(x)为当前字符x的概率区间上下界。
实际应用时，只保存下界作为码字即可。
 算术编码与移位运算**一知半解，此处存疑。**目的是为了简化算术编码过程中的乘法运算，从而提高速度。疑惑的点在于：移位的位数为何是动态的，是怎么决定的？ 自适应算术编码与自适应霍夫曼编码相似，动态调整每个字符的概率。用一棵平衡二叉树来保存字符的频数来提高效率。 四、字典编码4.1 基本原理静态字典：需要预设字典项，对一些专用的场景比较适合，比如源程序代码等等。但当字典查找成功率低到某一个阈值时，就会出现反扩张的现象。 自适应字典：从一个空或小字典开始，从输入流读到新字就输出新字并加入字典，并且删除旧字。删除旧字是因为大字典搜索速度太慢。如此便形成了一个循环：读入并解析成短语，在字典中查找，找到就输出码字，否则加入字典并输出原字，最后检查看是否需要删除一个旧字。这样做的好处是：只有字符串操作无数值运算；译码简单。译码过程，与编码一样从动态调整字典，只要规则一样，最后的解压结果便也是一样的，并且不需要解析输入数据，不需要匹配字符串，只需要查找索引，简单高效，是不对称的。
4.2 LZ77分两个区域，左边的缓冲区为当前的字典，右边的滑动窗口为即将要压缩的字符。原理见下图：
声明：上面这张图是来自另一篇博客：https://blog.csdn.net/qq_23084801/article/details/77496955，我看的这本书没图，纯文字，无力吐槽。
若从右往左搜索缓冲区没有匹配到字符串，则输出（0，0，当前字符），这就是必须要有第三部分的原因。一般在压缩器刚开始工作时，（0，0，）很容易出现。
LZ77也是非对称压缩技术，解压简单，因此多应用于一次压缩多次解压的场合。 4.3 LZ78压缩原理如下图：
解压时可以动态地恢复字典，如下图例：
 声明：以上三图均来自博客：https://www.cnblogs.com/en-heng/p/6283282.html
与LZ77不同，LZ78的字典不删除字典项。LZ78的字典采用树形结构保存，且是多叉树，如8位字符则每个节点最多可以有2^8个子节点。由于不会删除字典项，因此不涉及空间的回收，简化了存储空间的管理及字符串的搜索。但树的大小可能会急剧膨胀，导致空间耗尽。 4.4 LZW算是LZ78的改进版。最主要的区别在于它去掉了LZ78的第二个字段，这是因为它将所有的单字符提前预装到字典中了，所以下一个输入字符总是能被找到。剩下的过程显然容易推得，其解码过程与编码一样。
LZW的字典结构显然也是一棵多叉树，此书中介绍说为了减少不必要的子节点指针的空间预分配，LZW的多叉树采用的是数组结构，保存的是母节点指针。母节点采用哈希映射的方法来寻找子节点。我猜Zstd在这里肯定是有优化的。 存疑点率失真定理 算术编码与移位运算 基于LZ77的LZSS，Google的Snappy；基于LZ78的LZW，Facebook的Zstd（基于FSE）
未完待续…
|
