知识卡片
匹配搜索把成本偏向压缩端
LZ77编码端搜索历史以决定用哪个位置、匹配多长;解码端已有位置和长度,只需按格式复制并更新窗口。这使一次压缩、多次分发恢复的场景有机会承担较高编码成本来减少接收负担。
重复短语出现距离、窗口大小、最大匹配长度与标记开销都影响压缩率。历史窗口看不到的重复无法直接引用,短匹配也未必抵得过标记成本。
原文关于LZ77通常比霍夫曼压缩更多、恢复更快是该实现背景下的经验说明,不能推作所有输入和所有现代编码器的固定排名。恢复同样有复制、分配和窗口维护常数,不能字面理解为不受常数影响。
271用软件发布的一次压缩/多次恢复与交互传输的双端实时成本说明取舍,这是工作负载维度,不是必须二选一的永久规则。实际格式也可组合字典匹配和熵编码;RFC1951第2节明确DEFLATE结合LZ77与霍夫曼,2026-11-06实读相关段:RFC1951。未把该组合格式等同本书三元组示例。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 匹配搜索把成本偏向压缩端
- · 问与答
原书出处 · 2 处
- · 查看原书依据
寻找滑动窗口中的匹配短语。然而,在通常情况下,LZ77的解压缩过程要比霍夫曼编码的解压缩过程耗时要少。LZ77的解压缩过程非常快是因为每个标记都明确地告诉我们在缓冲区中哪个位置可以读取所需要的符号。事实上,我们最终只从滑动窗口中读取了与原始数据数量相等的符号而已。
- · 查看原书依据
大型软件包时。在这种情况下,LZ77性能较佳,因为数据只需要压缩一次(在软件生产过程中),而客户端却能享受到由高速的解压缩过程所带来的便利。另一方面,假如要在一个网络中交互发送大量的数据,并且在每次传输之前要对数据进行压缩。在这种情况下,对于每一次传输,都必须在网络的一端进行数据压缩,在网络的另一端
参考来源
- 位置:《算法精解:C语言描述》第14章《LZ77的效率》(spine1390;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1356.html;u266-ch14-025)。
- 结论依据:266全文与269/270复杂度文字实读,限制经验比较范围,未引用未测试性能数值。
- 原始内容:寻找滑动窗口中的匹配短语。然而,在通常情况下,LZ77的解压缩过程要比霍夫曼编码的解压缩过程耗时要少。LZ77的解压缩过程非常快是因为每个标记都明确地告诉我们在缓冲区中哪个位置可以读取所需要的符号。事实上,我们最终只从滑动窗口中读取了与原始数据数量相等的符号而已。
- 位置:《算法精解:C语言描述》第14章《问与答》(spine1394;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1360.html;u271-ch14-025)。
- 结论依据:271用软件发布的一次压缩/多次恢复与交互传输的双端实时成本说明取舍,这是工作负载维度,不是必须二选一的永久规则。实际格式也可组合字典匹配和熵编码;RFC1951第2节明确DEFLATE结合LZ77与霍夫曼,2026-11-06实读相关段:[RFC1951](https://www.rfc-editor.org/rfc/rfc1951.html#section-2)。未把该组合格式等同本书三元组示例。
- 原始内容:大型软件包时。在这种情况下,LZ77性能较佳,因为数据只需要压缩一次(在软件生产过程中),而客户端却能享受到由高速的解压缩过程所带来的便利。另一方面,假如要在一个网络中交互发送大量的数据,并且在每次传输之前要对数据进行压缩。在这种情况下,对于每一次传输,都必须在网络的一端进行数据压缩,在网络的另一端