984 Terry Welch (LZW)?LZ77 vs. LZ78?两种不同的方法?有很多变种?是很多主流压缩的基础7LZ77?基本方法:字典为先前已编码序列的一部分?搜索缓冲区为当前字典,通常为几千字节?机制:滑动窗口?搜索缓冲区(Search buffer)、前向(look ahead)缓冲区、搜索指针(search pointer)?目标:在搜索缓冲区中,寻找与搜索指针指向的字符串匹配的最长串,并对其进行编码?基本原理:如果某些模式在局部重复出现,能得到更有效的表示8LZ77 (2)?(o)ffset = search ptr - match ptr = 7?(l)ength = 连续匹配的字符数= 4?(c)odeword = C(‘r’)?编码?<o, l, c> = <7, 4, C(‘r’)>?If |search buff| = S, |A| = A, S + |LA buff| = W?定长码:?log2S?+ ?log2W?+ ?log2A?Search pointer9LZ77 编码举例?序列?cabracadabrarrarrad?W = 13, S = 7?|cabraca|dabrar|rarrad?对d,没有匹配的字符串?发送<0, 0, C(d)> (可以做得更好?)?|abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad?发送<7, 4, C(r)>10LZ77 编码举例(2)?|cadabrar|rarrad||cadabrar|rarrad||cadabrar|rarrad|?发送<3, 3, C(r)>?可以做得更好??发送<3, 5, C(d)>!?总结:三种情况?没有匹配?匹配?匹配串超过了搜索缓冲区
全文预览