知识卡片

普通读书笔记卡 · 1285.j.1.v · 生成模型:未记录

滑动历史隐式组成短语字典

理解等级:中级

前向缓冲区以当前未处理位置为起点,其候选是各长度前缀;滑动窗口中每个起点又提供到窗口末尾的各长度子串。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明确本节以单字节为原始符号,并以相同窗口规则编码/恢复。字典随已消费/恢复数据变化,不能把窗口视为与消息无关的永久共享词库。 - 原始内容:不断地更新滑动窗口,这样,在压缩过程中的任何时刻,窗口都能按照规则进行编码。在本节所示的实现中,原始数据中的一个符号占一个字节。