原书出处
大数据日知录_架构与算法
03 大数据常用的算法与数据结构
LZ77的压缩算法使用了滑动窗口和前向缓冲区的概念(图3-13)。滑动窗口包含了前面处理过的若干源字符,前向缓冲区(Lookahead Buffer)包含了输入数据流中将要处理的所有后续字符。算法尝试将前向缓冲区的开始字符串与滑动窗口中的字符串进行最长匹配。如果没有发现匹配,前向缓冲区的第1个字符输出并且移入滑动窗口,滑动窗口中存在最久的字符被移出。如果找到匹配字符串,那么匹配字符串作为三元组输出<指针,长度,后续字符>。其中的指针指出了匹配字符串在滑动窗口中的起始位置(也可以将指针设置为两个匹配字符串的起始位置差值,代表两者的相对位置),长度标明匹配字符串的长度,后续字符则指出前向缓冲区中除去匹配字符串后的第1个字符。窗口经过这个处理逻辑不断右移就完成了压缩编码过程。
原书定位详情
来源:a19c7933-4eda-4176-aebd-30fe7e1ad292
正文位置:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html
EPUB SHA-256:e45b74c4bdd8959aef24f2a5183280eb73ec5f173108f8679a4bbf44bbd5b34d