Lossless-Compression

Posted on 2025-05-01

Lossless-Compression

[TOC]

信息论基础

对于随机事件$A$，定义其自信息(self-information)为
$$
I(A)=-\log P(A)
$$
以2为底时单位为bit,自信息是非负值；

考虑两个随机变量$X,Y$，其取值为$x_i,y_j(1\le i\le n, 1\le j\le m)$,定义事件${X=x_i}, {Y=y_j}$的互信息为
$$
I(x_i,y_i)=\log \left( \frac{P(x_i|y_j)}{P(x_i)}\right)
$$
可以注意到这样的定义是对称的；

定义随机变量的熵(entropy)为其自信息期望：
$$
H(x)=-\sum_{i=1}^n P(x_i)\log P(x_i)
$$
二元信源熵函数如下图，可以看到在$p=0.5$时熵达到了最大值；

两个随机变量的联合熵(cross entropy)为其互信息期望：
$$
H(X,Y)=-\sum_{i=1}^n \sum_{i=1}^m P(x_i,y_j) \log P(x_i,y_j)
$$
条件熵(conditional entropy)为条件自信息期望
$$
H(X|Y)=-\sum_{i=1}^n \sum_{i=1}^m P(x_i,y_j) \log P(x_i|y_j)
$$
不难观察到
$$
I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)\
H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)
$$

随机变量$X$位于发送端，$Y$位于接收端，当其间信道可靠性下降时(增加$p\le 0.5$)时，其互信息减少；

信源编码定理

无记忆信源：独立分布的信息源，当前输出符号的值不取决于先前出现符号的值。

对于一个离散无记忆信源(DMS)，其输出符号共有$L$个取值，每个符号的熵为
$$
H(X)=-\sum_{i=1}^n P(x_i)\log P(x_i)\le \log L
$$
前缀条件(prefix condition)是指没有一个码字构成另一个码字的前缀；

即时编码(instantaneous code)是指检测符号序列满足码字中的一个立马进行译码；

Kraft不等式：

存在码字长度为$n_1\le \cdots \le n_L$的二元码的充分必要条件为满足前缀条件
$$
\sum_{k=1}^L 2^{-n_k}\le 1
$$
proof:构造深度为$n_L$的二叉树，码字和叶子结点映射满足不等式$\sum_{i=1}^L 2^{n_L-n_i}\le 2^{n_L}$

熵指定了在编码中每个符号平均位数的下限，即
$$
H(X)\le \overline l
$$
可以构造一种满足前缀条件的编码(著名的Hoffman编码)满足下上界
$$
\overline l < H(X)+1
$$
对于二元定长码(Fixed-Length Coding, FLC)来说，惟一编码需要的比特数为
$$
R=\lceil \log_2 L\rceil
$$
信源编码定理说明，对于任意用来表示信源中符号的前缀码，最小比特数平均至少等于信源的熵；

定义前缀码的效率为
$$
\eta = \frac{H(X)}{\overline R}
$$
若一个压缩过程和对应的解压过程没有造成信息的损失，称这样的压缩过程是无损的(lossless),否则称为有损的(lossy);

记压缩前后的比特数为$B_0,B_1$,定义其压缩率(compression ratio)为
$$
\eta = \frac{B_0}{B_1}, \eta>1.
$$
与定长编码相对的有变长编码(Variable-Length Coding, VLC);

游程编码

游程编码(Run-Length Encoding, RLE)，基于利用信源中的内存的编码方式，是一种用于缩减重复字符串（游程）大小的技术,属于FLC;

基本原理：将每个游程表示为计数+符号

例子：S=11111111111111100000000000000000001111可表示为S=(15,1)+(19,0)+(4,1)=01111 1 10011 0 00100 1

适用场景黑白传真和PCX格式图像；

Shannon-Fano编码

Shannon-Fano编码属于VLC，对于每个字符$x$，其编码比特数为
$$
l(x)=\lceil \log\frac 1{p(x)}\rceil
$$
对于字串HELLO的编码如下表，总共花费了10bits完成编码；

Symbol	Count	Log2	Code	bits used
L	2	1.32	0	1
H	1	2.32	10	2
E	1	2.32	110	3
O	1	2.32	111	3

算法步骤：

根据符号出现的频率计数对符号进行排序；
递归地将符号分成两部分，每部分的计数数大致相同，直到所有部分都只包含一个符号

这种编码机制得到的码字不是唯一的；

Huffman Coding

传统的Huffman编码是一种基于前缀码自底向上的编码方式，以下是算法流程：

将信源符号按照概率递减排序；
重复以下步骤直到只剩下一个符号：
- 从列表中选择两个频率计数最低的符号
- 形成一个将这两个符号作为子节点的 Huffman 子树，并创建一个父节点；
- 将子项的频率计数之和分配给父项，并将其插入到列表中，以便保持顺序；
- 列表中删除选择的两个符号子节点
为每个可能的路径分配前缀码字；

以下是X= HELLO的Huffman树

Huffman编码同样也不一定惟一，且具有如下性质：

前缀条件：没有一个字符的Huffman 码是任何其他 Huffman 码的前缀，以排除解码中的任何歧义。
最优性(Optimal):实现了最小冗余编码

平均编码长度和信源的熵满足
$$
\overline l < H(X)+1
$$

Extended-Huffman Coding

霍夫曼编码中的所有码字都具有整数位长度,当信源的某个符号出现非常频繁，其带来的自信息几乎为0，这时用1位来编码都十分浪费；

我们可以将许多信源符号打包成一个整体，再统计概率；

对于信源的符号集
$$
S={s_1,s_2, \cdots, s_n}
$$
拓展Huffman编码真正需要对以下字符串集编码：
$$
S^{(k)}={(s_1…s_1), \cdots, (s_k…s_k)}
$$
最优性可进一步缩紧上界：
$$
H(X)\le \overline l\le H(X)+\frac 1k
$$
当$k$比较大，且$n$很大，要编码的字符表的大小为$O(n^k)$,这有时难以接受；

Adaptive Huffman Coding

传统的Huffman编码需要需要预先统计符号的概率，实践中可能信源的统计特性未知，需要对信源的输出作长时间观察才能得到；

自适应霍夫曼编码可以在数据流到达时，将动态收集和更新统计信源信息；

编码和解码的过程如下：

def Encoder():
	Initial()
	while not EOF:
		get(c)
		encode(c)
		update_tree(c)
        
def Decoder():
	Initial()
	while not EOF:
		get(c)
		decode(c)
		update_tree(c)

初始化：使用一些最初商定的代码分配给符号，而无需事先了解频率计数；
更新树：增加符号的频率计数+更新树结构；

自适应霍夫曼树必须维持其兄弟属性(sibling)，具体来说如下：

节点按从左到右、从下到上的顺序编号，括号中的数字表示计数；
所有节点都按计数递增的顺序排列；如果 sibling 属性即将被违反，则调用 swap 过程以通过重新排列节点来更新树。
当需要swap时，计数为$N$的最远节点将与计数刚刚增加到$N+1$的节点交换;

下图是Swap的一个过程：

霍夫曼树还满足一个附加规则：维护一个NEW符号：

如果要首次发送任何字符/符号，则必须在其前面加上特殊符号 NEW。
NEW 的初始代码为 0；
NEW 的计数始终保持为 0（计数永远不会增加）；

假设我们如下初始化AADCCDD的编码信息：

自适应Huffman树更新如下：

Lempel-Ziv Coding

LZW 使用固定长度的码字来表示通常一起出现的可变长度的符号/字符字符串，例如，英文文本中的单词，许多字母成组出现，这就是一个有记忆的信源，用LZW算法就很有效；

LZW算法是基于字典的，LZW 编码器和解码器在接收数据时动态构建相同的字典。

LZW 将越来越长的重复项放入字典中，然后发出元素的代码，而不是字符串本身（如果该元素已放置在字典中）。

BEGIN
	s = next input character;
	while not EOF
	{ 
		c = next input character;

		if s + c exists in the dictionary
		s = s + c;
		else
		{ 
		output the code for s;
		add string s + c to the dictionary with a new code;
		s = c;
		}
	}
	output the code for s;
END

以下是对字符串A B AB BA B C AB ABB A的压缩过程：

最后输出的顺序为A B AB BA B C AB ABB A，编码为1 2 4 5 2 3 4 6 1

解码器初始字符串表与编码器使用的字符串表相同。

BEGIN
	s = NIL;
	while not EOF
	{
		k = next input code;
		entry = dictionary entry for k;
		output entry;
		if (s != NIL)
			add string s + entry[0] to dictionary with a new code;
		s = entry;
	}
END

下图是刚刚编码的解压过程，就是查字典的过程

在实践中，代码的长度存在上下界$[l_0,l_{\max}]$，字典初始大小为$2^{l_0}$,当字典被填满时，码长总体加1；当达到上界时，字典将删除最近最少使用条目；

Arithmetic Coding

算术编码是一种更现代的编码方法，通常优于霍夫曼编码。

消息由半开区间$ [a， b)$ 表示，其中 $a$ 和$ b$ 是介于 $0$ 和 $1$ 之间的实数。

最初，间隔为 $[0， 1)$。当消息变长时，间隔的长度会缩短，表示间隔所需的位数会增加；

这种编码方式需要为消息设置结束符terminator；

区间确定算法如下：

BEGIN
low = 0.0; 	high = 1.0; 	range = 1.0;

while (symbol != terminator)
{
	get (symbol);
  high = low + range * Range_high(symbol); 	
  low = low + range * Range_low(symbol);
	range = high - low;
}

output a code so that low <= code < high;
END

以下是对区间的确定过程，以CAEE$为例：

算术编码的最后一步要求生成一个在 [low， high] 范围内的数字，以下算法将确保找到最短的二进制码字：

BEGIN
code = 0;
k = 1;
while (value(code) < low)
{ 
	assign 1 to the kth binary fraction bit
	if (value(code) > high)
	replace the kth bit by 0
	k = k + 1;
}
END

上述算法的解码过程如下：

BEGIN
get binary code and convert to
decimal value = value(code);
Do
{ 
	find a symbol s so that
		Range_low(s) <= value < Range_high(s);
	output s;
	low = Rang_low(s);
	high = Range_high(s);
	range = high - low;
	value = [value - low] / range;
}
Until symbol s is a terminator
END

Lossless-JPEG图像压缩算法

给定图像$I$，其差分图像定义为每个像素的差分
$$
d(x,y)=I(x,y)-I(x-1,y)\
d(x,y)=4I(x,y)-I(x-1,y)-I(x+1,y)-I(x,y-1)-I(x,y+1)
$$
下式是二维Laplace算子离散版本，以下是原图和差分图像的对比

由于正常图像中存在空间冗余，差异图像将具有较窄的直方图，因此熵较小；

在JPEG中，首先需要建立一种预测模型，预测器将最多三个相邻像素的值组合为当前像素的预测值，如下图的中的X所示。

在预测X之前，A,B,C处像素已经被解码完成，预测模型通常选取下表所示；

算法只需要对真实图像和预测图像之间的差异进行压缩即可，压缩算法选择上述任何一种均可，比如Huffman算法；