知识卡片
字典压缩用标记替代重复短语
霍夫曼按符号频率分配变长码,LZ77则寻找重复短语并以较短引用标记替代。可替换短语必须能从编码双方共享的历史或约定字典恢复,不能任意删去重复内容。
字典法处理的符号不限于文字字符,本章实现以字节为单位。标记本身有开销,重复短语能否带来收益还取决于匹配长度与格式;“高效”不保证所有输入缩小。后续滑动窗口说明将给出本例如何维持可重建字典。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
基于字典的算法,这意味着它试图将长字符串(简称为短语)编码成短小的标记,用小标记代替字典中的短语,从而达到压缩的目的。它通过用小的标记代替数据中多次重复出现的长串来方法来压缩数据。与霍夫曼编码不同的是,其处理的符号不一定是文本字符,可以是任何大小的符号,但其通常选择一个字节的符号。
参考来源
- 位置:《算法精解:C语言描述》第14章《LZ77的描述》(spine1388;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1354.html;u263-ch14-022)。
- 结论依据:263全部短节实读,未先把尚未读取的具体令牌格式归入本节。
- 原始内容:基于字典的算法,这意味着它试图将长字符串(简称为短语)编码成短小的标记,用小标记代替字典中的短语,从而达到压缩的目的。它通过用小的标记代替数据中多次重复出现的长串来方法来压缩数据。与霍夫曼编码不同的是,其处理的符号不一定是文本字符,可以是任何大小的符号,但其通常选择一个字节的符号。