知识卡片
滑动历史隐式组成短语字典
前向缓冲区以当前未处理位置为起点,其候选是各长度前缀;滑动窗口中每个起点又提供到窗口末尾的各长度子串。LZ77在二者之间寻找共同短语,用位置和长度表示。
例如前向ABD与历史ABC的最长共同前缀短语为AB。历史中的B、BC、C也属于其他起点的字典短语,而前向匹配不能随意跳过开头A去找后面的字。
随着已编码符号进入历史、旧符号移出,字典随窗口改变。这里的集合表示是逻辑解释,不要求把每个子串复制成独立对象保存;窗口容量决定可回看的历史范围。
268明确本节以单字节为原始符号,并以相同窗口规则编码/恢复。字典随已消费/恢复数据变化,不能把窗口视为与消息无关的永久共享词库。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
最长短语。以之前描述的前向缓冲区和滑动窗口为例,其最长匹配短语为(A,B)。
- · 查看原书依据
不断地更新滑动窗口,这样,在压缩过程中的任何时刻,窗口都能按照规则进行编码。在本节所示的实现中,原始数据中的一个符号占一个字节。
参考来源
- 位置:《算法精解:C语言描述》第14章《短语字典的维护》(spine1388;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1354.html;u264-ch14-023)。
- 结论依据:264全文两个短语集合和ABD/ABC例实读。
- 原始内容:最长短语。以之前描述的前向缓冲区和滑动窗口为例,其最长匹配短语为(A,B)。
- 位置:《算法精解:C语言描述》第14章《LZ77的实现与分析》(spine1392;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1358.html;u268-ch14-023)。
- 结论依据:268明确本节以单字节为原始符号,并以相同窗口规则编码/恢复。字典随已消费/恢复数据变化,不能把窗口视为与消息无关的永久共享词库。
- 原始内容:不断地更新滑动窗口,这样,在压缩过程中的任何时刻,窗口都能按照规则进行编码。在本节所示的实现中,原始数据中的一个符号占一个字节。