当前位置: 首页 > news >正文

zlib压缩原理

数据压缩的本质

去除数据中的冗余信息,对于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

w:01

l:00

e:110

i:1111

r:11101

u:11100

可以看出,对于出现频率越高的字符,编码后的长度越小

字符串编码

有了上面的编码表之后,”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编码进行解码

 

相关文章:

zlib压缩原理

数据压缩的本质 去除数据中的冗余信息,对于ABABABABABABAB字样的字符串,AB出现了7次,占用14个字节,如果将该字符串编码为7AB,只占用3个字节。 为什么需要对数据压缩 数据需要存储或者传输,为了节省磁盘空…...

论文阅读笔记《DEEP GRAPH MATCHING CONSENSUS》

核心思想 本文提出一种基于图神经网络的图匹配方法,首先利用节点相似度构建初始的匹配关系,然后利用局部的一致性对初始的匹配关系进行迭代优化,不断筛除误匹配点,得到最终的匹配结果。本文还提出几种措施来降低计算复杂度&#x…...

华为OD机试题 - 开放日活动(JavaScript)

最近更新的博客 2023新华为OD机试题 - 斗地主(JavaScript)2023新华为OD机试题 - 箱子之形摆放(JavaScript)2023新华为OD机试题 - 考古学家(JavaScript)2023新华为OD机试题 - 相同数字的积木游戏 1(JavaScript)2023新华为OD机试题 - 最多等和不相交连续子序列(JavaScri…...

(考研湖科大教书匠计算机网络)第四章网络层-第八节:网际控制报文协议ICMP

获取pdf:密码7281专栏目录首页:【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一:网际控制报文协议ICMP(1)ICMP差错报告报文A:终点不可达B:源点抑制C:时间超过D&#xff…...

华为OD机试 - GPU 调度 | 备考思路,刷题要点,答疑 【新解法】

最近更新的博客 【新解法】华为OD机试 - 关联子串 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 停车场最大距离 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试 - 任务调度 | 备考思路,刷题要点,答疑,od Base 提供【新解法】华为OD机试…...

华为OD机试题 - 任务总执行时长(JavaScript)

最近更新的博客 2023新华为OD机试题 - 斗地主(JavaScript)2023新华为OD机试题 - 箱子之形摆放(JavaScript)2023新华为OD机试题 - 考古学家(JavaScript)2023新华为OD机试题 - 相同数字的积木游戏 1(JavaScript)2023新华为OD机试题 - 最多等和不相交连续子序列(JavaScri…...

还在想假期去哪玩?直接做一个旅游攻略小程序

憋了几年好不容易解封准备出去散散心,但看着大江南北这么多景点是不是有点让你选择强迫症呢?那就先制作一个旅游攻略小程序看看驴友们的分享吧。...

十四、vue3项目如何使用three.js

近期在开发过程中,因为项目已经接近尾声,就需要对项目中的数据进行整合,而数据看板不失为一个比较直观的展现形式。在数据看板中3D的展现形式是比较流行的展现形式,那么如何在项目引入一个大的场景,并且能够和后台发生…...

python 向excel表中添加新的sheet页或者向旧sheet中写入数据

import xlwt import xlrd from xlutils.copy import copy import os import numpy as np import pandas as pd class Excel_Add_Sheet():def save_table(self, table, file_name):# 保存表table.save(file_name)def add_new_sheet(self, file_name, sheet_name, titleNone):&q…...

RPC-grpc实践

参考:https://developer.aliyun.com/article/1152352?spma2c6h.12873639.article-detail.33.344f6446zEnbRi&scm20140722.ID_communityarticle1152352._.ID_communityarticle1152352-OR_rec-V_1 参考:https://onejson.blog.csdn.net/article/detai…...

JavaEE——MyBatis配置文件的详细介绍

简单介绍: 需要我们编写的配置文件主要有三个,分别是核心配置文件(mybatis-config.xml),数据库连接信息文件(db.properties),SQL语句映射文件(Mappers)&…...

bwmarrin/snowflake生成ID重复问题排查记录

现象 某日,运营反馈,在某个时间区间丢失了一段日志,让看看是什么问题。 排查 查看项目日志有无错误 发现项目日志有报错信息Error 1062 Duplicate entry 149059529550598144 for key PRIMARY,很显然,问题在此,数据库…...

操作系统题目收录(十)

1、在存储管理中,采用覆盖与交换技术的目的是()。 A:节省主存空间B:物理上扩充主存容量C:提高CPU效率D:实现主存共享 解析 覆盖和交换的提出就是为了解决主存空间不足的问题,但不…...

IOS 自动化测试环境搭建

购买MacPDD 比TB JD 便宜500,下单安装homebrew/bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)"安装npm cnpmbrew install node; npm install -g cnpm --registryhttps://registry.npm.taobao.org;安装类似Andro…...

系统设计原则

系统设计原则 好的系统是迭代出来的。先解决核心问题,预测未来可能出现的问题,对现有的问题有方案,对未来的问题有预案。不是一上来就按1亿用户量设计,也不要过度复杂化系统。 业务千变万化,技术层出不穷&#xff0c…...

推荐130个网站,非常实用,比涨工资都重要

搞学习 TED(最优质的演讲):https://www.ted.com/ 谷粉学术:https://gfsoso.99lb.net/scholar.html 大学资源网:http://www.dxzy163.com/ 简答题:http://www.jiandati.com/ 网易公开课:https…...

手机棋牌游戏开发的流程是怎样的?

最近几年,随着网络游戏的兴起,棋牌手游开发也越来越受欢迎,在国内,几乎随处可见从事手游和手游的公司。不过,虽然公司和产品很多,但效果也不一样,区别就在于,他们能不能掌握好这款游…...

浅谈C++函数重载

C相较于C语言来说,重载是一重大特性,让我们一起简单的回顾一下重载那些事 传送门函数重载是什么为什么有函数重载函数重载是如何实现的总结函数重载是什么 函数重载:是函数的一种特殊情况,C允许在同一作用域中声明几个功能相似的同名函数 这些同名函数的形参列表(参数个数or类…...

数据分析spss应急考试

数据分析spss应急考试 前言 单项选择 15(项)*2(分)30 判断题 10*1 10 计算题 2*10 案例分析题目(考实验内容) 总四十分,分值不等 老师重点强调了回归分析因子分析方差分析参数、非参数检验 2独立样本的非参数检验应该用什么方法多独立样本…...

Handler postDelayed的实现原理

Handler postDelayed的实现原理 问题描述 Handler.postDelayed()的原理是如何保证延时执行的? 扩展:这样实现的好处是什么? 题目分析 猜测一下 以我们对Handler的了解,内部使用了Looper对消息队列进行循环获取执行&#xff0…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色&#xf…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

Bean 作用域有哪些?如何答出技术深度?

导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答&#xff0c…...

渗透实战PortSwigger靶场:lab13存储型DOM XSS详解

进来是需要留言的&#xff0c;先用做简单的 html 标签测试 发现面的</h1>不见了 数据包中找到了一个loadCommentsWithVulnerableEscapeHtml.js 他是把用户输入的<>进行 html 编码&#xff0c;输入的<>当成字符串处理回显到页面中&#xff0c;看来只是把用户输…...