像素规律重复的图像压缩场景下哈夫曼编码是否会失效

直接给出核心结论：哈夫曼编码在该场景下不会完全零压缩增益，但压缩效率极低，相对于该序列本身可达到的理论压缩上限，基本等同于压缩失效。

原理拆解 #

哈夫曼编码属于逐符号的统计编码，压缩边界完全由单个符号的全局出现概率分布决定：它只会根据符号出现频率分配码字长度，完全不识别符号间的排列规律、相邻关联、周期重复这类结构冗余，最终平均码长会无限贴近信源的信息熵。

你给出的像素序列为无限循环的1 2 3 4 5 6排列，只要序列长度为6的整数倍，6个像素值的出现概率完全均等，每个值的出现占比均为1/6。

实际码长计算 #

• 该信源的理论信息熵约为2.58bit/像素，这是所有逐符号统计编码能达到的压缩极限。
• 对这6个等概率符号构建哈夫曼树后，会有2个符号被分配长度为2bit的码字，剩余4个符号被分配长度为3bit的码字，计算可得平均码长约为2.67bit/像素，已经非常贴近熵极限。

压缩效果判定 #

需要分两个参照系判断实际效果：

• 若和最小固定长度编码对比：6个不同像素值用等长编码存储，最少需要3bit/像素（2bit仅能表示4种不同值，无法覆盖6个符号），此时哈夫曼编码比等长编码节省约11%的存储空间，并非完全没有压缩效果。
• 若和该序列的实际可压缩上限对比：该序列是固定6值循环的强规律结构，用游程编码、LZ类字典编码的话，仅需要存储1组6像素的周期模板加总重复次数，压缩率可以做到原长的1%甚至更低，此时哈夫曼编码的压缩增益几乎可以忽略，本质原因是它完全无法捕捉跨符号的结构冗余，实际表现等同于压缩失效。

高相似度像素场景的通用表现 #

哈夫曼编码在高相似度图像上的表现只和像素值的概率分布有关，和像素排列规律无直接关联：

• 如果高相似度体现为像素值高度集中（比如整张图90%区域都是同一个灰度值，剩余区域分散为少量其他值），哈夫曼编码的效率会非常高，给高频值分配1-2bit的短码即可大幅拉低平均码长。
• 如果高相似度体现为像素值等概率规律排列（比如本次举例的周期序列，或是棋盘格式交替的黑白像素），哈夫曼编码的压缩率会极低，无法发挥压缩作用。

内容的提问来源于stack exchange，提问作者Slam Rsps