基于指针复用的压缩原理
文本压缩的一种基础思路是把重复片段替换成”指针”——指向该片段此前首次出现的位置加长度值,而非再存一遍原始字符。这能省空间的前提是指针占用的比特数要小于被替代文本,而这取决于引用距离:越近编码代价越低。这解释了为什么压缩算法偏爱局部重复而非任意距离重复,也是[[LZ77与LZ78的取舍]]等字典模型压缩算法的雏形。
主题对照
比较以熵为下限的文本压缩方法:哈夫曼与算术编码、静态与自适应建模、PPM、块排序与LZ字典压缩,以及压缩与随机访问、解码速度的取舍。
文本压缩的一种基础思路是把重复片段替换成”指针”——指向该片段此前首次出现的位置加长度值,而非再存一遍原始字符。这能省空间的前提是指针占用的比特数要小于被替代文本,而这取决于引用距离:越近编码代价越低。这解释了为什么压缩算法偏爱局部重复而非任意距离重复,也是[[LZ77与LZ78的取舍]]等字典模型压缩算法的雏形。
[[基于指针复用的压缩原理]]依赖对已出现文本的引用,这意味着压缩后的文件难以随机访问——读中间某段必须从头解压到目标位置。解决办法是切块分别压缩,需要哪块就只解压哪块,代价是压缩率下降:块内可引用的历史文本变少,块切得越细、随机访问越快但压缩效果越差。这是纯粹的空间-时间权衡,没有免费方案,只能按场景选粒度。
文本压缩必须无损——任何偏差都可能改变含义。图像压缩可接受有损,因为数字图像本身是对连续色彩的离散近似,肉眼难辨细微误差。这个边界可以推广到索引:索引整体应无损,但若某索引项除指向真正含关键词的段落外,也捎带指向少量不含该词的段落,只要能换来更高压缩率且检索时会被自动过滤,也是可接受的。判断标准不是”文本还是图像”,而是”错误能否被后续环节可靠发现或忽略”。
一个符号的信息量由其出现概率决定:概率越低,信息量越大,需要的编码位数也越多(信息量=-log₂概率)。字母表所有符号信息量的加权平均称为”熵”,是这个概率分布下无损压缩的理论极限,只能逼近不能突破,只在预测概率与真实分布完全一致时才达到最大压缩。这解释了为什么压缩研究重心从”编码方法”转向”概率建模方法”——真正决定压缩上限的是模型对数据规律的刻画能力。
估计概率分布(建模)有三种策略:静态建模用固定通用概率表,不需额外传输但遇到分布迥异的文本效果会变差;半静态建模先扫描全文统计专属分布再传输模型,适配度高但要付出两趟扫描加传输代价;自适应建模从平缓分布出发动态调整,兼顾单趟扫描与适配,效果最好但解码必须从头开始,不适合需要随机访问的全文检索系统,参见[[分块压缩与随机访问的权衡]]中的同样矛盾。
文本压缩两大流派不是谁更好的关系,而是从两个角度切入同一问题。符号方法一次处理一个符号,依赖对概率的精准估计决定编码长度;字典方法把多个符号打包成”短语”用一个码字整体替换,编码本身很简单。关键差异在于上下文信息藏在哪:符号方法把上下文显式建到概率分布里,字典方法把上下文隐含在”短语被分组”这件事本身之中。
哈夫曼编码给每个符号分配整数长度码字,这是它压缩效果不如算术编码的根本原因。当某符号概率极高(如99%)时,理论上只需0.015比特,但哈夫曼编码器受限于整数位长最少也要1比特——多花的部分纯是浪费,概率越极端越严重。理论上可打包多个符号成”块”编码缓解,但块内组合数随块长指数增长,实际不可行。哈夫曼用”接近最优、实现简单”换掉了”绝对最优、实现复杂”的算术编码。
标准哈夫曼解码要从树根沿指针走到叶子,每解码一位就访问一次几乎不会被重复引用的内存节点,大字母表下会造成大量缓存不命中,且存整棵树本身要耗费巨大内存。范式哈夫曼只要保证同一码长的码字数值连续且按字典序排列,就不需遍历树,只需知道每种码长的第一个码字即可定位,额外内存从”一整棵树”降到”码长种类数”,特别适合全文检索这种高频随机解码场景,MG系统就用它压缩正文。
算术编码不给单个符号分配固定整数长度码字,而把整个序列映射成不断收窄的实数区间,能突破[[哈夫曼编码的整数位长天花板]]无限逼近熵,尤其在某符号概率极高、极不均衡时优势明显。代价是计算更慢,且天生不支持中途开始解码,因为区间由从头到尾所有历史累积收窄而成。全文检索里这个代价往往比压缩率提升更致命,因此正文用哈夫曼编码,图像数据用算术编码。
部分匹配预测(PPM)优先尝试较长上下文(如前4个字符),如果该上下文从未出现过或对当前符号预测概率为0,就发送一个”转义”符号,通知解码器降级到更短上下文重新尝试,最坏情况降级到”所有符号等概率”的兜底模型。这本质是把”该用多长上下文预测”这个决策也变成了可编码传输的信息。转义符号本身也占编码空间,转义发生越少(预测越准),压缩效果越好,这也是PPM系列改进多打磨转义概率估计的原因。
Burrows-Wheeler变换(块排序压缩核心)不直接压缩原文,而是先按每个字符所在上下文排序,让原本分散但后面跟着相似字符的位置聚在一起。重排后文本本身没变小,但极易压缩:局部字符高度重复,用move-to-front编码器就能取得接近PPM的压缩效果,不需要PPM那样复杂的多阶上下文回退逻辑。这种”先做可逆变换让规律显性化,再用简单方法压缩”的思路和离散余弦变换是同一类设计思想。
两大自适应字典压缩流派对”字典从哪来”给出不同答案。LZ77把已解码全部文本当作字典,允许指针指向窗口内任意位置的任意子串,实现简单、速度快,但同一子串可能被反复以不同方式指向,存在编码冗余。LZ78限制只能引用之前已正式识别出的短语(构成一棵短语树),代价是树本身要占内存且不断增长,但避免重复编码浪费。LZ77选择不限制以换速度,LZ78选择限制以换更紧凑表示,其变体LZW后来居上。
高性能压缩方法默认从头解码到尾——变长编码没有固定码字边界,自适应模型状态依赖此前全部历史,两者都排斥随机访问。全文检索要求任意跳转到某文档直接解码,因此必须在文档边界处人为创造”同步点”:记录该文档在压缩流中的精确起始位置(通常是位偏移),并标记文档结束,平均每篇文档只多花约1比特。算术编码创造同步点的额外开销比哈夫曼编码更大,这是全文检索场景哈夫曼编码更受青睐的又一原因。
把各种压缩方法的压缩率和解码速度画在同一张图上,多数方法符合”压缩得越狠、跑得越慢”的直觉,但少数方法能打破这个权衡曲线。书中观察到这类方法的共同特征不是用了更聪明的概率模型,而是”每一步解码能吐出多个字符”——如基于单字建模的哈夫曼方案(huffword),一次解码对应一个完整单词而非一个字母,单位工作量产出更高。发散:解码速度的瓶颈往往不在”每次操作有多快”,而在”每次操作能处理多少内容”。
哈夫曼编码码长理论上没有硬性上限,用32位整数存储看起来绰绰有余——直觉上要处理2的33次方个符号才可能逼近溢出。但这直觉错了:迫使哈夫曼算法生成超长码字所需的最小符号数由斐波那契数列增长速度决定,其增长率远小于2。构造刻意的病态频率分布,只需一千三百万个符号就能把某码字撑到32位溢出,比朴素估计的90亿低近千倍。真正解法是理论上限长编码或把整数精度提高到64位,提醒要先推导最坏情况的真实增长率。
基于字的哈夫曼压缩要把每个出现过的词存进字典才能解码,但字典随文档集合增大会膨胀到数MB,成为解码内存开销主因。优化是只保留按频率排序的高频词,低频词用转义标记通知解码器按字符拼出来,代价可忽略。TREC实测:字典从10MB砍到1MB,压缩率只从29.4%恶化到30.0%。选词策略也关键——按频率排序取前N个明显优于按先出现先入选,是找到高度不均衡分布、保留头部就拿到几乎全部收益的帕累托改进范式。
压缩在 Hadoop 中不是单纯节省磁盘,而是在 CPU、网络和 I/O 间重新分配成本。数据量巨大且网络/磁盘常是瓶颈时,适度消耗 CPU 做压缩反而提高整体吞吐。发散:性能优化要看系统瓶颈,不看单点开销。
CompressionCodec 把压缩算法封装成统一接口,调用方只关心输入输出流,不关心 Gzip、BZip2 或 Snappy 的细节。算法可替换后,系统能按场景选择压缩率或速度。相关:[[Writable取舍]]。
数据压缩最适合放在客户端:它既能把大量小对象打包成大对象,又能在本地压缩,同时节省网络带宽和存储空间。压缩效果取决于算法和数据特征,随机二进制数据几乎压不动,文本则好得多。只有在没有专门客户端、用户多用浏览器且上传的多是适合压缩的文档时,才考虑在服务端压缩存储;下载时若客户端支持,也可传输压缩数据。
压缩算法没有绝对最优:lzw 实现简单,可在硬件上实现以获得很高速度;DEFLATE 用 LZ77 去重复串,再用 Huffman 编码;gzip 基于 DEFLATE,并使用自己的格式封装与完整性信息;bzip2 单文件压缩率更高,但慢得多。书中选 gzip,既不是最快也不是压缩比最高,但足够好且简单;有要求的场景应按压缩速度和压缩比另选。
原书把gzip多成员串联与更高压缩比相连,这不能作为普遍比较结论。gzip格式允许独立成员串联,并不保证因此比同等DEFLATE编码更省空间。此处按2026-10-23核对的RFC 1952与Go gzip文档限定表述。
前缀码要求任一码字都不是另一完整码字的前缀。串接后可从开头唯一确定第一个字符,再继续解码;若一个码字是另一个的前缀,就不能如此即时判定码字是否结束。
前缀码可用二叉树表示:字符在叶子,左边为0、右边为1,根到叶路径形成码字。
字符频率乘叶深再求和就是编码文件的总位数;优化编码可转为最小化频率加权叶深。
字符频率均为正时,最优前缀树可取满二叉树:每个非叶节点都有两个孩子。
若有单孩子节点,可删除它并缩短其下码字而不破坏前缀性质;有n个字符时,满树有n−1个内部节点。
重复n−1轮后得到编码树;正确性仍须证明。
该界依赖堆实现,不能脱离数据结构直接断言。
字符编码给每个字符唯一二进制码字。
存在一棵最优前缀树,使频率最低的两个字符处在最深的兄弟叶上。
把任意最优树的最深兄弟叶与这两个低频叶交换,由于低频放在更深处不会增加频率加权路径成本,所得树仍最优。
将最低频的两个字符合并成一个频率为二者之和的伪字符,求合并后字母表的最优编码树,再把伪字符展开为两个孩子,可得到原问题的最优树。
展开前后成本只差二者频率之和,反证可说明次级树若不最优就会改进原树。
BWT先给文本末尾加一个小于原字母表全部字符的唯一终止符,再列出所有循环旋转并按字典序排序。
顺序读取排序结果的最后一列,就得到变换后的字符串。
BWT常把相同字符移到相邻或较近的位置,为后续前移编码、游程编码及霍夫曼编码创造压缩机会。
BWT本身只是可逆重排,压缩率仍取决于后续编码和输入文本。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
分布式存储系统类
书籍类型:工程实践
清单覆盖 7/7
44 张卡片
来源书籍
算法与数据结构类
书籍类型:经典原理
清单覆盖 7/7
1142 张卡片
来源书籍
分布式存储系统类
书籍类型:未标注
清单覆盖 5/5
75 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
173 张卡片
来源书籍
数据工程与数据架构方法类
书籍类型:工程实践
类别清单尚未核对
145 张卡片
来源书籍
信息检索/搜索引擎类
书籍类型:经典原理
清单覆盖 7/7
58 张卡片
来源书籍
书籍类型:工程实践
39 张卡片
主题索引
比较二值图像的上下文建模、有损与无损压缩、JPEG、文本图像的字典压缩与版面切分方法。
与 4 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类