知识卡片
滑动词典引用重复片段
LZ77从已处理窗口中匹配后续输入,用距离与长度等信息代替重复文本;解码器从已解码前缀恢复,双方无需事先共享完整词典。LZSS增加字面量与匹配选择,短匹配若不划算就直接输出。示例AABBCBBAABC中BB可编码为距离3长度2,格式和最短长度属于具体方案参数。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 大数据常用的算法与数据结构 · 查看原书依据
LZ77的压缩算法使用了滑动窗口和前向缓冲区的概念(图3-13)。滑动窗口包含了前面处理过的若干源字符,前向缓冲区(Lookahead Buffer)包含了输入数据流中将要处理的所有后续字符。算法尝试将前向缓冲区的开始字符串与滑动窗口中的字符串进行最长匹配。如果没有发现匹配,前向缓冲区的第1个字符输出并且移入滑动窗口,滑动窗口中存在最久的字符被移出。如果找到匹配字符串,那么匹配字符串作为三元组输出<指针,长度,后续字符>。其中的指针指出了匹配字符串在滑动窗口中的起始位置(也可以将指针设置为两个匹配字符串的起始位置差值,代表两者的相对位置),长度标明匹配字符串的长度,后续字符则指出前向缓冲区中除去匹配字符串后的第1个字符。窗口经过这个处理逻辑不断右移就完成了压缩编码过程。
参考来源
- 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html)
- 结论依据:原文以“LZ77的压缩算法使用了滑动窗口”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。
- 原始内容:LZ77的压缩算法使用了滑动窗口和前向缓冲区的概念(图3-13)。滑动窗口包含了前面处理过的若干源字符,前向缓冲区(Lookahead Buffer)包含了输入数据流中将要处理的所有后续字符。算法尝试将前向缓冲区的开始字符串与滑动窗口中的字符串进行最长匹配。如果没有发现匹配,前向缓冲区的第1个字符输出并且移入滑动窗口,滑动窗口中存在最久的字符被移出。如果找到匹配字符串,那么匹配字符串作为三元组输出<指针,长度,后续字符>。其中的指针指出了匹配字符串在滑动窗口中的起始位置(也可以将指针设置为两个匹配字符串的起始位置差值,代表两者的相对位置),长度标明匹配字符串的长度,后续字符则指出前向缓冲区中除去匹配字符串后的第1个字符。窗口经过这个处理逻辑不断右移就完成了压缩编码过程。
- 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。