词典编码词典编码主要利用数据本身包含许多重复的字符串的特性.例如:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮. 我们如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的相关性.字符串与代号的对应表就是词典. 实用的词典编码算法的核心就是如何动态地形成词典,以及如何选择输出格式以减小冗余. 第一类词典编码第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过,然后用已经出现过的字符串替代重复的部分,它的输出仅仅是指向早期出现过的字符串的"指针".
LZ77算法 LZ77 算法在某种意义上又可以称为"滑动窗口压缩",该算法将一个虚拟的,可以跟随压缩进程滑动的窗口作为词典,要压缩的字符串如果在该窗口中出现,则输出其出现位置和长度.使用固定大小窗口进行词语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;随着压缩的进程滑动词典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串.
LZ77编码的基本流程
1,从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤 2,否则进行步骤 3.
2,输出三元符号组 ( off, len, c ).其中 off 为窗口中匹配字符串相对窗口边界的偏移,len 为可匹配的长度,c 为下一个字符,即不匹配的第一个字符.然后将窗口向后滑动 len + 1 个字符,继续步骤 1.
3,输出三元符号组 ( 0, 0, c ).其中 c 为下一个字符.然后将窗口向后滑动 1 个字符,继续步骤 1.
LZ77算法 LZ77编码举例 C A B A B B C B A A 5, 3, A ABC 7 5 2, 1, B B 5 4 0, 0, C -- 4 3 1, 1, B A 2 2 0, 0, A -- 1 1 输出匹配串位置步骤
LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息.冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符.
LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH),否则就输出真实字符.另外要输出额外的标志位区分是指针还是字符.
LZSS编码的基本流程
1,从当前压缩位置开始,考察未编码的字符,并试图在滑动窗口中找出最长的匹配字符串,如果匹配串长度len大于等于最小匹配串长度(len >= MIN_LENGTH),则进行步骤 2,否则进行步骤 3.
2,输出指针二元组 ( off, len).其中 off 为窗口中匹配字符串相对窗口边界的偏移,len 为匹配串的长度,然后将窗口向后滑动 len 个字符,继续步骤 1.
3,输出当前字符c,然后将窗口向后滑动 1 个字符,继续步骤 1.
LZSS编码举例 C B A A B B C B B A A 字符 11 10 9 8 7 6 5 4 3 2 1 位置 C C 11 8 (7,3) AAB 8 7 (3,2) BB 6 6 C -- 5 5 B B 4 4 B -- 3 3 A A 2 2 A -- 1 1 输出匹配串位置步骤输入数据流: 编码过程 MIN_LEN =2 LZSS算法在相同的计算机环境下,LZSS算法比LZ77可获得比较高的压缩比,而译码同样简单.这也就是为什么这种算法成为开发新算法的基础,许多后来开发的文档压缩程序都使用了LZSS的思想.例如,PKZip, GZip, ARJ, LHArc和ZOO等等,其差别仅仅是指针的长短和窗口的大小等有所不同. LZSS同样可以和熵编码联合使用,例如ARJ就与霍夫曼编码联用,而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码.
第二类词典编码第二类算法的想法是企图从输入的数据中创建一个"短语词典 (dictionary of the phrases)",这种短语可以是任意字符的组合.编码数据过程中当遇到已经在词典中出现的"短语"时,编码器就输出这个词典中的短语的"索引号",而不是短语本身.
LZ78算法 LZ78的编码思想是不断地从字符流中提取新的字符串(String),通俗地理解为新"词条",然后用"代号"也就是码字(Code word)表示这个"词条".这样一来,对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream),生成码字流(Code stream),从而达到压缩数据的目的. LZ78编码器的输出是码字-字符(W,C)对,每次输出一对到码字流中,与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String),然后添加到词典中.
LZ78编码算法
步骤1:将词典和当前前缀P都初始化为空.
步骤2:当前字符C:=字符流中的下一个字符.
步骤3:判断P+C是否在词典中 (1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2. (2)如果"否",则输出与当前前缀P相对应的码字W和当前字符C, 即(W,C); 将P+C添加到词典中; 令P:=空值,并返回到步骤2
LZ78编码举例 A B A C B C B B A 字符 9 8 7 6 5 4 3 2 1 位置 (2, A) BA 8 5 (3, A) BCA 5 4 (2, C) BC 3 3 (0, B) B 2 2 (0, A) A 1 1
输出词典位置步骤输入数据流: 编码过程: LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章.在他们的研究基础上,Terry A.Welch在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码.
在编码原理上,LZW与LZ78相比有如下差别:
LZW只输出代表词典中的字符串(String)的码字(code word).这就意味在开始时词典不能是空的,它必须包含可能在字符流出现中的所有单个字符.即在编码匹配时,至少可以在词典中找到长度为1的匹配串. LZW编码是围绕称为词典的转换表来完成的.
LZW算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换.LZW编码器的输入是字符流(Char stream),字符流可以是用8位ASCII字符组成的字符串,而输出是用n位(例如12位)表示的码字流 (Code stream),码字代表单个字符或多个字符组成的字符串(String).
LZW编码算法
步骤1:将词典初始化为包含所有可能的单字符,当前前缀P初始化为空.
步骤2:当前字符C:=字符流中的下一个字符.
步骤3:判断P+C是否在词典中 (1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2. (2)如果"否",则输出与当前前缀P相对应的码字W; 将P+C添加到词典中; 令P:=C,并返回到步骤2
LZW编码举例 C A B A B A B B A 字符 9 8 7 6 5 4 3 2 1 位置 2 BB 5 2 2 2 BA 6 3 3 4 ABA 7 4 4 7 ABAC 8 6 5 4 3 2 1 码字 1 AB 1 1 C B A
输出词典位置步骤输入数据流: 编码过程: LZW算法 LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作.对LZW算法进一步的改进是增加可变的码字长度,以及在词典中删除老的缀-符串.在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法. LZW算法取得了专利,专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司),除了商业软件生产公司之外,可以免费使用LZW算法. 预测编码预测编码是数据压缩理论的一个重要分支.它根据离散信号之间存在一定相关性的特点,利用前面的一个或多个信号对下一个信号进行预测,然后对实际值和预测值的差(预测误差)进行编码.如果预测比较准确,那么误差信号就会很小,就可以用较少的码位进行编码,以达到数据压缩的目的. 第n个符号Xn的熵满足: 所以参与预测的符号越多,预测就越准确,该信源的不确定性就越小,数码率就可以降低.
LZ77算法 LZ77 算法在某种意义上又可以称为"滑动窗口压缩",该算法将一个虚拟的,可以跟随压缩进程滑动的窗口作为词典,要压缩的字符串如果在该窗口中出现,则输出其出现位置和长度.使用固定大小窗口进行词语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;随着压缩的进程滑动词典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串.
LZ77编码的基本流程
1,从当前压缩位置开始,考察未编码的数据,并试图在滑动窗口中找出最长的匹配字符串,如果找到,则进行步骤 2,否则进行步骤 3.
2,输出三元符号组 ( off, len, c ).其中 off 为窗口中匹配字符串相对窗口边界的偏移,len 为可匹配的长度,c 为下一个字符,即不匹配的第一个字符.然后将窗口向后滑动 len + 1 个字符,继续步骤 1.
3,输出三元符号组 ( 0, 0, c ).其中 c 为下一个字符.然后将窗口向后滑动 1 个字符,继续步骤 1.
LZ77算法 LZ77编码举例 C A B A B B C B A A 5, 3, A ABC 7 5 2, 1, B B 5 4 0, 0, C -- 4 3 1, 1, B A 2 2 0, 0, A -- 1 1 输出匹配串位置步骤
LZSS算法 LZ77通过输出真实字符解决了在窗口中出现没有匹配串的问题,但这个解决方案包含有冗余信息.冗余信息表现在两个方面,一是空指针,二是编码器可能输出额外的字符,这种字符是指可能包含在下一个匹配串中的字符.
LZSS算法的思想是如果匹配串的长度比指针本身的长度长就输出指针(匹配串长度大于等于MIN_LENGTH),否则就输出真实字符.另外要输出额外的标志位区分是指针还是字符.
LZSS编码的基本流程
1,从当前压缩位置开始,考察未编码的字符,并试图在滑动窗口中找出最长的匹配字符串,如果匹配串长度len大于等于最小匹配串长度(len >= MIN_LENGTH),则进行步骤 2,否则进行步骤 3.
2,输出指针二元组 ( off, len).其中 off 为窗口中匹配字符串相对窗口边界的偏移,len 为匹配串的长度,然后将窗口向后滑动 len 个字符,继续步骤 1.
3,输出当前字符c,然后将窗口向后滑动 1 个字符,继续步骤 1.
LZSS编码举例 C B A A B B C B B A A 字符 11 10 9 8 7 6 5 4 3 2 1 位置 C C 11 8 (7,3) AAB 8 7 (3,2) BB 6 6 C -- 5 5 B B 4 4 B -- 3 3 A A 2 2 A -- 1 1 输出匹配串位置步骤输入数据流: 编码过程 MIN_LEN =2 LZSS算法在相同的计算机环境下,LZSS算法比LZ77可获得比较高的压缩比,而译码同样简单.这也就是为什么这种算法成为开发新算法的基础,许多后来开发的文档压缩程序都使用了LZSS的思想.例如,PKZip, GZip, ARJ, LHArc和ZOO等等,其差别仅仅是指针的长短和窗口的大小等有所不同. LZSS同样可以和熵编码联合使用,例如ARJ就与霍夫曼编码联用,而PKZip则与Shannon-Fano联用,它的后续版本也采用霍夫曼编码.
第二类词典编码第二类算法的想法是企图从输入的数据中创建一个"短语词典 (dictionary of the phrases)",这种短语可以是任意字符的组合.编码数据过程中当遇到已经在词典中出现的"短语"时,编码器就输出这个词典中的短语的"索引号",而不是短语本身.
LZ78算法 LZ78的编码思想是不断地从字符流中提取新的字符串(String),通俗地理解为新"词条",然后用"代号"也就是码字(Code word)表示这个"词条".这样一来,对字符流的编码就变成了用码字(Code word)去替换字符流(Char stream),生成码字流(Code stream),从而达到压缩数据的目的. LZ78编码器的输出是码字-字符(W,C)对,每次输出一对到码字流中,与码字W相对应的字符串(String)用字符C进行扩展生成新的字符串(String),然后添加到词典中.
LZ78编码算法
步骤1:将词典和当前前缀P都初始化为空.
步骤2:当前字符C:=字符流中的下一个字符.
步骤3:判断P+C是否在词典中 (1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2. (2)如果"否",则输出与当前前缀P相对应的码字W和当前字符C, 即(W,C); 将P+C添加到词典中; 令P:=空值,并返回到步骤2
LZ78编码举例 A B A C B C B B A 字符 9 8 7 6 5 4 3 2 1 位置 (2, A) BA 8 5 (3, A) BCA 5 4 (2, C) BC 3 3 (0, B) B 2 2 (0, A) A 1 1
输出词典位置步骤输入数据流: 编码过程: LZW算法 J.Ziv和A.Lempel在1978年首次发表了介绍第二类词典编码算法的文章.在他们的研究基础上,Terry A.Welch在1984年发表了改进这种编码算法的文章,因此把这种编码方法称为LZW(Lempel-Ziv Walch)压缩编码.
在编码原理上,LZW与LZ78相比有如下差别:
LZW只输出代表词典中的字符串(String)的码字(code word).这就意味在开始时词典不能是空的,它必须包含可能在字符流出现中的所有单个字符.即在编码匹配时,至少可以在词典中找到长度为1的匹配串. LZW编码是围绕称为词典的转换表来完成的.
LZW算法的词典 LZW编码器(软件编码器或硬件编码器)就是通过管理这个词典完成输入与输出之间的转换.LZW编码器的输入是字符流(Char stream),字符流可以是用8位ASCII字符组成的字符串,而输出是用n位(例如12位)表示的码字流 (Code stream),码字代表单个字符或多个字符组成的字符串(String).
LZW编码算法
步骤1:将词典初始化为包含所有可能的单字符,当前前缀P初始化为空.
步骤2:当前字符C:=字符流中的下一个字符.
步骤3:判断P+C是否在词典中 (1)如果"是",则用C扩展P,即让P:=P+C,返回到步骤2. (2)如果"否",则输出与当前前缀P相对应的码字W; 将P+C添加到词典中; 令P:=C,并返回到步骤2
LZW编码举例 C A B A B A B B A 字符 9 8 7 6 5 4 3 2 1 位置 2 BB 5 2 2 2 BA 6 3 3 4 ABA 7 4 4 7 ABAC 8 6 5 4 3 2 1 码字 1 AB 1 1 C B A
输出词典位置步骤输入数据流: 编码过程: LZW算法 LZW算法得到普遍采用,它的速度比使用LZ77算法的速度快,因为它不需要执行那么多的缀-符串比较操作.对LZW算法进一步的改进是增加可变的码字长度,以及在词典中删除老的缀-符串.在GIF图像格式和UNIX的压缩程序中已经采用了这些改进措施之后的LZW算法. LZW算法取得了专利,专利权的所有者是美国的一个大型计算机公司—Unisys(优利系统公司),除了商业软件生产公司之外,可以免费使用LZW算法. 预测编码预测编码是数据压缩理论的一个重要分支.它根据离散信号之间存在一定相关性的特点,利用前面的一个或多个信号对下一个信号进行预测,然后对实际值和预测值的差(预测误差)进行编码.如果预测比较准确,那么误差信号就会很小,就可以用较少的码位进行编码,以达到数据压缩的目的. 第n个符号Xn的熵满足: 所以参与预测的符号越多,预测就越准确,该信源的不确定性就越小,数码率就可以降低.
回复Comments
{commenttime}{commentauthor}
{CommentUrl}
{commentcontent}