当前位置: 首页 > 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…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...