知识卡片
前缀码让叶子到达即可解码
二元码若没有任何符号码字是另一个码字的前缀,就可沿码树逐位走,到叶子便输出一个符号并回根开始下一个。左走0、右走1只是需共享的一种标记约定。
本例U=101、V=01、W=100、X=00、Y=11;如读到01即可输出V,因为没有其他码字从01继续延长。每个符号都放叶子,防止既可结束又可继续的歧义。
原文称“属于前缀树”在这里要表达的是前缀码性质。完整解码还要知道使用哪棵树和有效结束条件,不能把末尾补齐字节的填充位也当数据无限读下去;本例后续格式以原符号数帮助停止。
259强调编码树与解码重建树一致,字节符号是本实现范围,不是抽象霍夫曼唯一选择。格式保存哪些元数据及平局处理需按260/261具体实现再确认。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
前缀树。前缀树是指一组代码中的任何一个编码都不是另一个编码的前缀。这就保证了编码被解码时不会有多义性。例如,"V"的编码是01,01不会是任何其他编码的前缀。因此,只要在压缩数据中碰到了01,就可以确定它表示的是符号"V"。
- · 查看原书依据
重建压缩过程中的霍夫曼树,同时将编码解码成符号本身。在本节介绍的实现过程中,一个原始符号都用一个字节表示。
参考来源
- 位置:《算法精解:C语言描述》第14章《压缩和解压缩数据》(spine1382;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1348.html;u256-ch14-012)。
- 结论依据:256全部编码/解码过程与五码字实读,03018 U路径101已完整看过;260/261头部原符号数文字已读,未宣称实现已完整检查。
- 原始内容:前缀树。前缀树是指一组代码中的任何一个编码都不是另一个编码的前缀。这就保证了编码被解码时不会有多义性。例如,"V"的编码是01,01不会是任何其他编码的前缀。因此,只要在压缩数据中碰到了01,就可以确定它表示的是符号"V"。
- 位置:《算法精解:C语言描述》第14章《霍夫曼编码的分析与实现》(spine1385;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1351.html;u259-ch14-012)。
- 结论依据:259强调编码树与解码重建树一致,字节符号是本实现范围,不是抽象霍夫曼唯一选择。格式保存哪些元数据及平局处理需按260/261具体实现再确认。
- 原始内容:重建压缩过程中的霍夫曼树,同时将编码解码成符号本身。在本节介绍的实现过程中,一个原始符号都用一个字节表示。