聊聊字符集编码与数据压缩( 三 )

2022-04-18 数据压缩

文章插图

当压缩数据的时候，前向缓冲区与移动窗口之间在做短语匹配的是后会存在 2 种情况:
（1）找不到匹配时：将未匹配的符号编码成符号标记（多数都是字符本身）
（2）找到匹配时：将其最长的匹配编码成短语标记。
短语标记包含三部分信息:
（1）滑动窗口中的偏移量（从匹配开始的地方计算）；
（2）匹配中的符号个数；
（3）匹配结束后的前向缓冲区中的第一个符号。
一旦把 n 个符号编码并生成相应的标记，就将这 n 个符号从滑动窗口的一端移出，并用前向缓冲区中同样数量的符号来代替它们，如此，滑动窗口中始终有最新的短语。
（1）开始

文章插图

(2) 滑动窗口中没有数据，所以没有匹配到短语，将字符 A 标记为 A

文章插图

(3)滑动窗口中有 A,没有从缓冲区中字符（BABC）中匹配到短语，依然把 B 标记为
B

文章插图

(4)缓冲区字符（ABCB）在滑动窗口的位移 6 位置找到 AB,成功匹配到短语 AB,将AB 编码为(6,2,C) ，之所以是 6 ，是因为窗口的 A 在滑动窗口的索引[6]位置。

文章插图

（5）缓冲区字符（BABA）在滑动窗口位移 4 的位置匹配到短语 BAB,将 BAB 编码为
(4,3,A) 。

文章插图

(6) 缓冲区字符（BCAD）在滑动窗口位移 2 的位置匹配到短语 BC ，将 BC 编码为
（2,2,A）

文章插图

(7) 缓冲区字符 D,在滑动窗口中没有找到匹配短语，标记为 D

文章插图

(8)缓冲区中没有数据进入了，结束

文章插图

6.LZ77解压
解压就是压缩的逆向过程，当解码字符标记:将标记编码成字符拷贝到滑动窗口中，解码短语标记:在滑动窗口中查找相应变量，同时找到指定长短的短语进行替换。
(1)开始

文章插图

(2)符号标记 A 解码

文章插图

(3)符号标记 B 解码

文章插图

(4)短语标记(6,2,C)解码。根据 3 中的索引[6]开始，得到 AB ，就是重复 AB 再加入上 C ，就成了 ABABC ，并且滑动窗口滑到最右边的位置。

文章插图

(5)短语标记(4,3,A)解码
根据4中的进行标记。

文章插图

(6)短语标记(2,2,A)解码
根据5中进行标记。

文章插图

(7) 符号标记 D 解码

文章插图

LZ77 压缩算法优点:
压缩比相当高。也和你选择滑动窗口大小，以及前向缓冲区大小，以及数据熵有关系。
解压很快，每个标记都明确告知在哪个位置可以读取。
缺点:
压缩过程是比较耗时的，因为要花费很多时间寻找滑动窗口中的短语匹配。
6.Huffman 算法原理
哈夫曼设计了一个贪心算法来构造最优前缀码，被称为哈夫曼编码（Huffman code），其正确性证明依赖于贪心选择性质和最优子结构。哈夫曼编码可以很有效的压缩数据，具体压缩率依赖于数据本身的特性。
先介绍几个概念：码字、码字长度、定长编码与变长编码。

推荐阅读

上一篇：云环境下密钥泄露导致的安全问题

下一篇：淘宝地址总是提示违禁词淘宝网重要处罚通知是什么意思