【Algorithms 4】算法(第4版)学习笔记 24 - 5.5 数据压缩

文章目录

    • 前言
    • 参考目录
    • 学习笔记
      • 1:介绍
      • 2:游程编码 run-length encoding
      • 2.1:介绍
      • 2.2:Java 实现
      • 3:霍夫曼压缩 Huffman compression
      • 3.1:变长前缀码 variable-length codes
      • 3.1.1:介绍
      • 3.1.2:前缀码单词查找树
      • 3.2:霍夫曼编码
      • 3.2.1:概述
      • 3.2.2:Java 实现:单词查找树节点
      • 3.2.3:Java 实现:扩展
      • 3.2.4:Java 实现:单词查找树、编译表
      • 3.2.5:Java 实现:压缩
      • 3.3:demo 演示
      • 3.4:小结
      • 4:LZW 压缩算法
      • 4.1:统计方法
      • 4.2:LZW 压缩
      • 4.3:LZW 扩展
      • 4.4:特殊情况
      • 4.5:Java 实现
      • 4.6:小结

前言

本篇主要内容包括:游程编码霍夫曼压缩算法LZW 压缩算法

建议在学习本篇之前先行学习或回顾 《5.2 单词查找树》的内容。

参考目录

  • B站 普林斯顿大学《Algorithms》视频课
    (请自行搜索。主要以该视频课顺序来进行笔记整理,课程讲述的教授本人是该书原版作者之一 Robert Sedgewick。)
  • 微信读书《算法(第4版)》
    (本文主要内容来自《5.5 数据压缩》)
  • 官方网站
    (有书本配套的内容以及代码)

学习笔记

注1:下面引用内容如无注明出处,均是书中摘录。
注2:所有 demo 演示均为视频 PPT demo 截图。
注3:如果 PPT 截图中没有翻译,会在下面进行汉化翻译,因为内容比较多,本文不再一一说明。

1:介绍

这个世界充满了数据,而能够有效表达数据的算法在现代计算机基础架构中有着重要的地位。压缩数据的原因主要有两点:节省保存信息所需的空间和节省传输信息所需的时间。

对于通用数据压缩:

image-20240405170417042

2:游程编码 run-length encoding

2.1:介绍

![L21-55DataCompression_15]

将 40 位长的比特字符串拆解可得:15个0,7个1,7个0,11个1(交替出现的 0 和 1)
用 4 位表示长度并以 0 开头,可以得到:15=1111,7=0111,7=0111,11=1011
即:1111011101111011

问题一:用多少比特表示游程长度?
答:用 8 位(但本例中使用 4 位)
问题二:当某个游程的长度超过了能够记录的最大长度时怎么办?
答:当运行长度超过最大值时,插入长度为0的运行进行间隔。

2.2:Java 实现

edu.princeton.cs.algs4.RunLength

![image-20240405171955560]

edu.princeton.cs.algs4.RunLength#compress

![image-20240405172110231]

3:霍夫曼压缩 Huffman compression

3.1:变长前缀码 variable-length codes

3.1.1:介绍

根据不同字符采用不同位数进行编码。

![L21-55DataCompression_19]

Q. 如何避免歧义?
**A. ** 确保任何编码都不作为其他编码的前缀存在。

示例 1. 固定长度编码。
示例 2. 在每个编码字后附加特殊终止字符。
示例 3. 实现通用的前缀码。

3.1.2:前缀码单词查找树

注:建议回顾《5.2 单词查找树》 。

![L21-55DataCompression_20]

Q. 如何表示前缀码?
A. 单词查找树!

  • 字符存储在叶子节点上。
  • 每个编码对应从树的根节点到某个叶子节点的一条路径。

![L21-55DataCompression_21]

压缩:

  • 方法1:从叶子节点开始,沿路径向上追溯至根节点,反向输出各节点对应的二进制位。
  • 方法2:创建键-值对的符号表。

扩展:

  • 从根节点开始。
  • 若当前位为 0,则向左子树移动;若为 1,则向右子树移动。
  • 若到达叶子节点,则输出该节点所代表的字符,并返回到根节点继续处理下一个位。

![image-20240405174020211]

3.2:霍夫曼编码

3.2.1:概述

![L21-55DataCompression_22]

动态模型: 针对每条消息使用自定义的前缀码进行压缩。

压缩过程:

  • 读取待压缩的消息。
  • 根据消息内容构建最优的前缀码。如何构建?
  • 将生成的前缀码(单词查找树)写入文件。
  • 利用构建好的前缀码对消息进行压缩。

扩展过程:

  • 从文件中读取前缀码(单词查找树)。
  • 读取已压缩的消息,并利用单词查找树对其进行扩展还原。

3.2.2:Java 实现:单词查找树节点

![image-20240405174719041]

edu.princeton.cs.algs4.Huffman.Node

![image-20240405175437498]

3.2.3:Java 实现:扩展

edu.princeton.cs.algs4.Huffman#expand

![image-20240405174941646]

3.2.4:Java 实现:单词查找树、编译表

edu.princeton.cs.algs4.Huffman#buildTrie

![image-20240405175922898]

edu.princeton.cs.algs4.Huffman#buildCode

![image-20240405175938985]

3.2.5:Java 实现:压缩

edu.princeton.cs.algs4.Huffman#compress

/*** Reads a sequence of 8-bit bytes from standard input; compresses them* using Huffman codes with an 8-bit alphabet; and writes the results* to standard output.* 从标准输入中读取8位字节序列; 使用具有8位字母的霍夫曼代码对其进行压缩; 并将结果写入标准输出。*/public static void compress() {// read the inputString s = BinaryStdIn.readString();char[] input = s.toCharArray();// tabulate frequency countsint[] freq = new int[R];for (int i = 0; i < input.length; i++)freq[input[i]]++;// build Huffman trieNode root = buildTrie(freq);// build code tableString[] st = new String[R];buildCode(st, root, "");// print trie for decoderwriteTrie(root);// print number of bytes in original uncompressed messageBinaryStdOut.write(input.length);// use Huffman code to encode inputfor (int i = 0; i < input.length; i++) {String code = st[input[i]];for (int j = 0; j < code.length(); j++) {if (code.charAt(j) == '0') {BinaryStdOut.write(false);}else if (code.charAt(j) == '1') {BinaryStdOut.write(true);}else throw new IllegalStateException("Illegal state");}}// close output streamBinaryStdOut.close();}

3.3:demo 演示

  • 计算输入字符的频率。

![image-20240405180301604]

  • 从每个字符开始,对应创建一个节点,并赋予其权重等于该字符的出现频率。(按照权重排序)

![image-20240405180339783]

  • 找到最小权重的两个。
  • 合并成一个累计权重的单词查找树。

![image-20240405180714577]

将新的树放回原本的队列中,按照权重排序。

![image-20240405181057070]

重复以上的构建步骤,具体过程如下:

![image-20240405181146423]

![image-20240405181226901]

![image-20240405181332540]

![image-20240405181352694]

![image-20240405181407305]

![image-20240405181435345]

![image-20240405181451244]

最终构建结果:

![L21-55DataCompression_29]

3.4:小结

![L21-55DataCompression_30]

Q. 如何找到最佳的前缀码?

霍夫曼算法:

  • 计算输入字符串中每个字符 i 的出现频率 freq[i]
  • 针对每个字符 i,初始化一个节点,节点的权重设置为其频率 freq[i]
  • 重复以下过程直到形成一个单一的单词查找树:
    • 选择两个具有最小权重 freq[i]freq[j] 的节点。
    • 将这两个节点合并成为一个新节点,新节点的权重为原两个节点权重之和 freq[i] + freq[j]

![L21-55DataCompression_32]

对应书本命题 U:

![image-20240405182201039]

4:LZW 压缩算法

4.1:统计方法

![L21-55DataCompression_34]

静态模型: 应用于所有文本的固定模型。

  • 速度快。
  • 不是最优:因为各类文本具有各自的统计特征差异。
  • 示例:ASCII码、摩尔斯电码。

动态模型: 根据文本内容动态生成压缩模型。

  • 需要先进行一次预处理遍历来建立模型。
  • 在传输压缩数据时,必须同时发送模型信息。
  • 示例:霍夫曼编码。

适应性模型: 在读取文本过程中不断学习和更新模型。

  • 精确的模型构建可带来更高的压缩率。
  • 解压时需从起始位置开始解码整个文件。
  • 示例:LZW算法。

4.2:LZW 压缩

demo 演示:

![image-20240405195218117]

压缩:

![L21-55DataCompression_36]

LZW压缩:

  • 创建一张关联 W 位长度编码值和字符串的符号表。
  • 初始化 ST,其中包含单个字符键对应的码字。
  • 在输入未扫描部分中查找 ST 中最长的字符串 s,该字符串是输入的一个前缀。
  • 写出与字符串s关联的W位码字。
  • 将 s 与输入中的下一个字符 c 拼接起来,形成新的字符串,并将其添加到 ST 中。

Q. 如何表示 LZW 压缩的码表?
A. 使用一个单词查找树(Trie)结构来支持最长前缀匹配。

4.3:LZW 扩展

demo 演示:

![image-20240405200135556]

![image-20240405200147524]

扩展:

![L21-55DataCompression_38]

LZW 扩展:

  • 创建一个符号表,用于关联 W 位宽的码键与对应的字符串值。
  • 初始化 ST,填充所有可能的单字符解码结果。
  • 读取一个 W 位码键。
  • 在 ST 中查找与该码键关联的字符串值并输出。
  • 更新ST。

Q. 如何表示 LZW 解压缩的码表?
A. 使用大小为 2W 的数组来表示。

4.4:特殊情况

![image-20240405200955157]

![image-20240405201005888]

4.5:Java 实现

edu.princeton.cs.algs4.LZW

![image-20240405201101502]

edu.princeton.cs.algs4.LZW#compress

![image-20240405201120034]

edu.princeton.cs.algs4.LZW#expand

![image-20240405201135239]

4.6:小结

![L21-55DataCompression_45]

无损压缩:

  • 使用变长编码表示固定长度的符号。[霍夫曼编码]
  • 使用固定长度的编码表示变长的符号。[LZW 编码]

有损压缩: [本课程未涵盖]
· JPEG、MPEG、MP3等。
· FFT(快速傅里叶变换)、小波分析、分形等技术。

压缩的理论极限: 香农信息熵。

压缩实践: 尽可能利用所有可利用的信息。

(完)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/306689.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于ssm餐饮掌上设备点餐系统论文

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了餐饮掌上设备点餐系统的开发全过程。通过分析餐饮掌上设备点餐系统管理的不足&#xff0c;创建了一个计算机管理餐饮掌上设备点餐系统的方案。文章介绍了餐饮掌…

OpenHarmony编译构建系统

这篇来聊聊OpenHarmony的编译构建&#xff0c;经过前面的实践&#xff0c;再来看编译构建。 编译构建概述 在官网中提到了&#xff0c;OpenHarmony编译子系统是以GN和Ninja构建为基座&#xff0c;对构建和配置粒度进行部件化抽象、对内建模块进行功能增强、对业务模块进行功能…

代码随想录第38天| 509. 斐波那契数 70. 爬楼梯

理论基础 刷题大纲&#xff1a; 动态规划5步曲&#xff1a; 1、确定dp数组以及下标的含义 2、确定递推公式 3、dp数组如何初始化 4、确定遍历顺序 5、举例推导dp数组 509. 斐波那契数 509. 斐波那契数 - 力扣&#xff08;LeetCode&#xff09; 代码随想录 (programmercarl.co…

数据结构-----枚举、泛型进阶(通配符?)

文章目录 枚举1 背景及定义2 使用3 枚举优点缺点4 枚举和反射4.1 枚举是否可以通过反射&#xff0c;拿到实例对象呢&#xff1f; 5 总结 泛型进阶1 通配符 ?1.1 通配符解决什么问题1.2 通配符上界1.3 通配符下界 枚举 1 背景及定义 枚举是在JDK1.5以后引入的。主要用途是&am…

RAID磁盘阵列

一.raid简介 独立硬盘冗余阵列&#xff0c;旧称廉价磁盘冗余阵列&#xff0c;简称磁盘阵列。利用虚拟化存储技术把多个硬盘组合起来&#xff0c;成为一个或多个硬盘阵列组&#xff0c;目的为提升性能或数据冗余&#xff0c;或是两者同时提升。RAID把多个硬盘组合成为一个逻辑硬…

【Docker】docker快速安装部署fastdfs的镜像详细记录

部署nacos的docker镜像 第一步&#xff1a; 获取fastdfs镜像1、查看镜像列表2、创建本地映射文件夹 第二步&#xff1a;运行镜像1.使用docker镜像构建tracker服务2.使用docker镜像构建Storage服务3.Storage服务中默认安装了Nginx服务4.如果需要修改storage则配置则进到以下目录…

python用循环新建多个列表

​在Python编程中&#xff0c;我们经常需要创建多个列表来存储和管理数据。有时候&#xff0c;列表的数量是已知的&#xff0c;我们可以手动逐一创建&#xff1b;但更多时候&#xff0c;列表的数量是动态的&#xff0c;或者我们希望通过某种模式来批量生成列表。这时候&#xf…

典型新能源汽车热管理系统方案分析

目前行业具有代表性的热管理系统有PTC电加热方案、热泵方案&#xff08;特斯拉八通阀热泵、吉利直接式热泵&#xff09;、威马的柴油加热方案以及以理想为代表的插电式混动车方案。 小鹏P7整车热管理方案分析&#xff08;PTC电加热方案&#xff09; 小鹏P7作为小鹏汽车的第2款…

设计模式——组合模式08

组合模式&#xff1a;把类似对象或方法组合成结构为树状的设计思路。 例如部门之间的关系。 设计模式&#xff0c;一定要敲代码理解 抽象组件 /*** author ggbond* date 2024年04月06日 08:54* 部门有&#xff1a;二级部门&#xff08;下面管三级部门&#xff09; 三级部门 &a…

网工内推 | 网络工程师,13薪,周末双休,华三、华为认证优先

01 路邦远大 招聘岗位&#xff1a;网络工程师 职责描述&#xff1a; 1、配合市场销售人员&#xff0c;做好产品的售后服务工作&#xff1b; 2、负责项目方案安装调试指导以及日常客户使用培训&#xff0c;对客户提出的问题提出解决方案&#xff1b; 3、为客户提供专业、规范的…

solidity(3)

地址类型 pragma solidity ^0.8.0;contract AddressExample {// 地址address public _address 0x7A58c0Be72BE218B41C608b7Fe7C5bB630736C71;address payable public _address1 payable(_address); // payable address&#xff0c;可以转账、查余额// 地址类型的成员uint256…

小样本计数网络FamNet(Learning To Count Everything)

小样本计数网络FamNet(Learning To Count Everything) 大多数计数方法都仅仅针对一类特定的物体&#xff0c;如人群计数、汽车计数、动物计数等。一些方法可以进行多类物体的计数&#xff0c;但是training set中的类别和test set中的类别必须是相同的。 为了增加计数方法的可拓…

揭秘大前端开发方向的新机遇!

众所周知&#xff0c;华为开发者大会2023&#xff0c;宣布不再兼容安卓&#xff0c;同时宣布了“鸿飞计划”&#xff0c;欲与iOS、安卓在市场三分天下&#xff0c;这对中国国产操作系统而言&#xff0c;具有划时代的意义。 鸿蒙应用开发的兴起&发展 鸿蒙操作系统是华为自…

如何开辟动态二维数组(C语言)

1. 开辟动态二维数组 C语言标准库中并没有可以直接开辟动态二维数组的函数&#xff0c;但我们可以通过动态一维数组来模拟动态二维数组。 二维数组其实可以看作是一个存着"DataType []"类型数据的一维数组&#xff0c;也就是存放着一维数组地址的一维数组。 所以&…

阿里云4核16G服务器可以用来做什么?

阿里云4核16G服务器可以用来做什么&#xff1f;可用来搭建游戏服务器&#xff0c;阿里云4核16G服务器10M带宽30元1个月、90元3个月&#xff0c;优惠活动 aliyunfuwuqi.com/go/youhui 阿里云4核16G服务器可以用来做什么&#xff1f;除了搭建游戏服务器&#xff0c;还可以用来哪…

python小游戏

这些游戏你玩过几个&#xff1f; 1.贪吃蛇2.吃豆人3.加农炮4.四子棋5. Fly Bird<font color #f3704ab>6.记忆&#xff1a;数字对拼图游戏&#xff08;欢迎挑战&#xff01;用时&#xff1a;2min&#xff09;7.乒乓球8.上课划水必备-井字游戏&#xff08;我敢说100%的人都…

springCloud项目打包 ,maven package或install打包报错

解决思路一&#xff1a; <build><plugins><plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-plugin</artifactId><version>2.3.7.RELEASE</version></plugin><plugin>&…

智能合约:未来数字经济的基石

智能合约是一种自动执行交易的计算机协议&#xff0c;它以代码形式规定了交易双方的权利和义务&#xff0c;具有高度的可靠性和安全性。随着数字经济的发展&#xff0c;智能合约的重要性日益凸显&#xff0c;将成为未来数字经济的基石。 首先&#xff0c;智能合约在金融领域的应…

雨云:不只是一阵清风,更是一场暴雨的力量

引言 在网络时代&#xff0c;服务器是任何在线业务的核心。无论你是运营一家小型博客还是承载着数百万用户的大型电商平台&#xff0c;都需要一个稳定、高效的服务器来支持你的业务。然而&#xff0c;在众多服务器提供商中&#xff0c;有一家备受推崇&#xff0c;那就是雨云。 …

AI算力报告:算力大时代,AI算力产业链全景梳理

今天分享的是AI算力专题系列深度研究报告&#xff1a;《算力大时代&#xff0c;AI算力产业链全景梳理》。 &#xff08;报告出品方&#xff1a;中信建投证券&#xff09; 报告共计&#xff1a;98页 核心观点 生成式 AI取得突破&#xff0c;我们对生成式 A 带来的算力需求做…