学校门户网站建设的意义,十大软件app排行免费,做美团旅游网站多少钱,娄底市建设局网站数据压缩的本质
去除数据中的冗余信息#xff0c;对于ABABABABABABAB字样的字符串#xff0c;AB出现了7次#xff0c;占用14个字节#xff0c;如果将该字符串编码为7AB#xff0c;只占用3个字节。
为什么需要对数据压缩
数据需要存储或者传输#xff0c;为了节省磁盘空…数据压缩的本质
去除数据中的冗余信息对于ABABABABABABAB字样的字符串AB出现了7次占用14个字节如果将该字符串编码为7AB只占用3个字节。
为什么需要对数据压缩
数据需要存储或者传输为了节省磁盘空间和网络带宽在存储或传输时可以将数据先进行压缩到真正需要使用数据的时候再进行解压。
zlib压缩
zlib压缩是一种无损压缩底层使用deflate数据流压缩算法。
zlib压缩的特点 无损压缩 压缩率取决于数据的重复性
deflate的三种压缩模型 不压缩数据。对于已经压缩过的数据不再进行压缩。 压缩数据。先用LZ77进行压缩再使用huffman编码。压缩树是deflate规定的。 压缩数据。先用LZ进行压缩再使用huffman编码。压缩树是压缩其生成的 LZ77压缩算法
LZ77压缩算法的核心思想是对字符串进行扫描对于前面已经出现过的子字符串用偏移量匹配的字符串的长度进行编码。LZ77中有三个重要的概念短语字典、滑动窗口、前向缓冲区。 前向缓冲区待编码的数据 滑动窗口存放已经编码的数据 短语字典用滑动窗口中的数据更新字典并与前向缓冲区中的数据进行匹配
LZ77算法的步骤 步骤1逐字符扫描前向缓冲区在滑动窗口中找出匹配的最长子字符串如果找到则执行步骤2,如果没有找到执行步骤3 步骤2对前向缓冲区中匹配的字符串进行编码并输出编码的格式为前向缓冲区中匹配开始位置距离滑动窗口中匹配开始位置的偏移量匹配的长度将匹配的字符串移入滑动窗口中继续执行步骤1 步骤3将当前字符编码为0,0,当前字符值并输出表示滑动窗口中没有出现过该字符并将该字符移入到滑动窗口中继续执行步骤1
例子
现在对ABABCBABABCAD这个字符串进行压缩。
滑动窗口大小为8,前向缓冲区大小为4。 开始执行步骤1将ABAB四个字符读入前向缓冲区扫描到字符A此时滑动窗口为空没有找到匹配执行步骤3, 将字符A编码为0,0,A并将字符A移入滑动窗口中将C移入前向缓冲区。 继续执行步骤1扫描到字符B缓冲区中没有字符B执行步骤3, 将字符B编码为0,0,B并将字符B移入滑动窗口中。 继续执行步骤1,扫描到字符A滑动窗口中有字符A继续扫描字符A后面的字符当前字符串为AB滑动窗口中有AB继续向后扫描得到字符串ABC但滑动窗口中没有ABC扫描结束执行步骤2,将AB编码为2,2将AB移入滑动窗口 继续执行步骤1扫描到字符C缓冲区中没有字符C执行步骤3, 将字符C编码为0,0,C并将字符C移入滑动窗口中 继续执行步骤1匹配到BAB执行步骤2, 将BAB编码为4,3移动缓冲区 继续执行步骤1匹配到ABC执行步骤2将ABC编码为6,3移动缓冲区 继续执行步骤1匹配到A执行步骤2将A编码为(5,1),移动缓冲区 继续执行步骤1滑动窗口中没有字符D执行步骤3,将D编码为0,0,D移动缓冲区 前向缓冲区为空结束 最终的输出为(0,0,A)(0,0,B)2,2(0,0,C)(4,3)(6,3)(5,1)(0,0,D)可以按照这个序列进行解码
(0,0,A)-A
(0,0,B)-AB
(2,2)-ABAB
(0,0,C)-ABABC
(4,3)-ABABCBAB
(6,3)-ABABCBABABC
(5,1)-ABABCBABABCA
(0,0,D)-ABABCBABABCAD
Huffman编码
参考https://blog.csdn.net/FX677588/article/details/70767446
哈夫曼Huffman编码算法是基于二叉树构建编码压缩结构的它是数据压缩中经典的一种算法。算法根据文本字符出现的频率重新对字符进行编码。我们希望出现频率越高的字符的编码后的长度越小。
重要的性质
哈夫曼编码是一种前缀编码。前缀编码指的是任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。比如将字符A编码为0,那么则不能将字符B编码为01。
这个性质对于解码起着重要的作用
构建哈夫曼二叉树
对于字符串“we will we will r u”如果直接使用ASCII编码编码后每个字符表示为包括空格
119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117可见需要19个字节存储这段信息共152位。
现在对每个字符出现的频率进行统计得到下表 首先按照字符出现的频率从低到高的顺序对字符进行排序存储到一个优先队列中优先队列中每个元素可以看成一个节点每个节点具有值和权重出现的次数两种属性 为了得到哈夫曼树需要对优先队列进行从左到右进行合并将u作为左节点r作为右节点将r和u的权重出现的次数相加得到一个新的节点作为u和r的父节点。 继续将这个新节点与节点i进行合并 此时优先队列中的元素不再按照权重从低到高的顺序进行排列了对优先队列进行重新排序 重复进行合并与排序操作直到优先队列中只有一个根节点最后得到huffman树 问一个问题为什么要将元素按照出现次数从低到高排列
根据haffman树进行编码
得到huffman树后将该二叉树中分支中的左支路编码为0,右支路编码为1得到编码二叉树 最后根据编码二叉树得到每个字符的编码 空格10
w01
l00
e110
i1111
r11101
u11100
可以看出对于出现频率越高的字符编码后的长度越小
字符串编码
有了上面的编码表之后”we will we will r u”这句重新进行编码就可以得到很大的压缩编码表示为01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100。这样最终我们只需50位内存比原ASCII码表示节约了2/3空间效果还是很理想的。当然现实中不是简单这样表示的还需要考虑很多问题。
解码
由于huffman编码是前缀编码在解码时从哈夫曼树的根开始从左到右把二进制编码的每一位进行判别若二进制编码为0则选择左分支走向下一个结点若遇到1则选择右分支走向下一个结点
现在根据huffman树对01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100这个huffman编码进行解码
