无损数据压缩编码

数据压缩

数据压缩可分成两种类型，一种是无损压缩（lossless compression），另一种是有损压缩（lossy compression）

无损压缩：重构后的数据与原来的数据完全相同

有损压缩：重构后的数据与原来的数据有所不同，但不会导致对原始数据的误解

熵编码

所谓熵编码算法，就是一种用于确定码元的比特组合的计算方法。

所谓熵编码，就是指在不丢失任何信息的前提下，基于码元的统计特性，对码元或直接对报文本身进行编码，使得最后存储该报文所需要的平均比特数接近信源的信息熵。

信源：指构成一类报文的基本符号的集合。

报文：就是信息的载体

码元（基本编码单元）：基本符号又称为码元

一个信源的所有码元的平均信息量就称为该信源的信息熵（entropy）

信息熵公式：

香农-范诺编码（自上而下）

香农-范诺算法

• 第一步：对码元的概率（次数或频度）进行排序。

• 第二步：进入一个循环处理，将排列好的码元分割成两个部分

• 第三步：编码，对二叉树每一分支赋值0或1

  • 不等长编码

分割的原则是，两个部分的次数之和（或频度之和）最接近，换句话说，就是使两部分的次数之和的差最小。

示例：

压缩比是指压缩前的原始报文所需要的存储空间与压缩后所需要的存储空间之比。

压缩比为120:91

霍夫曼编码（自下而上）

霍夫曼编码算法

• 第一步：对码元的概率（次数或频度）进行排序，升序和降序均可

• 第二步：把概率最小的两个码元的概率相加，得到一个新的根节点；重复第二步直到形成二叉树

• 第三步：编码，对二叉树每一分支赋值0或1（大概率分支赋1或赋0均可）

压缩比为120:90

霍夫曼算法比香农-范诺算法的压缩效率要高。

$\textcolor{red}{平时分：}$

设计无损压缩算法得到压缩文件发到老师QQ邮箱

算术编码（考试会考-编码或者解码）

算术编码并不对码元进行编码，而是直接对报文进行处理，即编码算法直接作用于输入报文，将其压缩成某种编码形式

算术编码算法是一个对编码区间进行分割的循环过程，当前分割的区间是前一轮循环得到的编码区间，每一次循环都会从原始报文输入一个码元，直到输入最后一个码元，即中止分割循环。

行程编码-RLE

行程编码（run length encoding，RLE），是指对报文逐行进行统计，通过记录连续排列在一起的相同数据单元的数量、以及该数据单元本身，以压缩存储空间的一种编码算法

在这些图块中，许多行上都具有相同的颜色，或者说在一行上有许多连续的象素都具有相同的颜色值，只需要存储一个象素的颜色值，再加上相同颜色的象素的数目就可以了

词典编码（考：算法流程，伪代码，计算）

词典编码（Dictionary Encoding）就是典型的通用无损压缩方法

词典编码的根据是数据本身存在大量的重复或者说冗余

第一类字词编码（隐式词典）

基本思想：用指向早期曾经出现过的字符串的指针来表示当前被编码字符串

第一类词典编码算法中并没有出现一个显式的（explicit）“词典”，但实际上存在一组“指针+模式”这样的数据集合，指针就是“索引”，模式就是“词条”，这个“索引+词条”构成的词典没有明显地表示出来，而是融合到编码中去了。

LZ77 算法( by Abraham Lempel and Jakob Ziv)

LZ77的关键是搜索，即在已经处理过的符号序列（数据流）中，寻找与待编码符号序列相同的模式，如果找到匹配的模式，就设法对这个模式进行索引，也就是生成一个指针，然后输出该索引即可

总体上LZ77算法就是一个搜索匹配模式、输出匹配长度和偏移量的循环过程。

LZ77示例：

LZ77解码：

LZSS算法

改进点：

在LZ77算法基础上改进而来的，主要区别在于它设置了一个最小匹配长度，并改进了输出数据格式。如果匹配模式的长度大于最小匹配长度，就输出(off,length），否则就直接输出原字符序列（其长度取决于最小匹配长度，例如，如果最小匹配长度为2，那么直接输出的原字符长度等于1）。

LZSS示例：

第二类字词编码（显式词典）

基本思想：从输入的数据流中创建一个短语词典，后续数据流中若出现词典中的短语，则可用该短语在词典中的索引表示该短语，而不需要输出短语本身。

LZ78算法

LZ78示例：

LZW算法

改进点：

1. 第一，它的词典最初不是空的，而是一开始就包含了一些基本的词条，这些词条是字符流中可能出现的单个字符，例如ASCII字符集。

2. 第二，LZW算法的输出与LZ78不同，它只输出索引，不像LZ78那样输出（index，next char）对。

LZW示例：

解码示例：