免费网站域名空间学信网登录

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

免费网站域名空间,学信网登录,查询网官网,公司的分类前言#xff1a;在接触文本隐写研究领域时了解到这本书。本书可算作《数据压缩》的入门书籍之一#xff0c;这本书对熵编码、变长编码、统计编码、自适应统计编码、字典编码、上下文编码等常用编码方式的定义及来源进行介绍#xff0c;对不同场景下不同格式的压缩数据有针对… 前言在接触文本隐写研究领域时了解到这本书。本书可算作《数据压缩》的入门书籍之一这本书对熵编码、变长编码、统计编码、自适应统计编码、字典编码、上下文编码等常用编码方式的定义及来源进行介绍对不同场景下不同格式的压缩数据有针对性地分析笔风幽默强烈推荐本书中共有15个章节本人主要阅读了前9个章节以下是阅读本书过程中的一些笔记供大家参考。 目录 ◆ 序◆ 第1章 并非无趣的一章◆ 第2章 不容错过的一章◆ 第3章 突破熵◆ 第4章 VLC◆ 第5章 统计编码◆ 第6章 自适应统计编码◆ 第7章 字典编码◆ 第8章 上下文数据转换◆ 第9章 数据建模◆ 第13章 序列化数据 ◆ 序 无损方法 • 去掉重复数据LZ算法 • 熵压缩哈夫曼编码、算术编码 有损方法 • 降低精度截断或降采样 • 图像 / 视频压缩 • 音频压缩 ◆ 第1章 并非无趣的一章 数据压缩无非是用最紧凑的方式来表示数据。 数据压缩算法有5类变长编码(variable-length codesVLC、统计压缩statistical compression、字典编码dictionary encodings、上下文模型context modeling和多上下文模型multicontext modeling。所有这5类算法都有很多变种。 1948年香农又发表了《通信的数学理论》在这篇论文中他详细论述了发送者怎样对要发送的信息进行编码才能达到最佳效果由此开创了信息论information theory这一全新的学术领域。对消息进行编码有多种方式“字母表”与“摩尔斯码”只是其中常见的两种。但是对每一个特定的消息来说都有一个最佳的编码方式这里的“最佳”指的是传递消息时用到的字母或者符号也可以说是二进制位即信息的单位最少。至于这里说的“最少”到底是多少则取决于消息所包含的信息内容。香农发明了一种度量消息所携带信息内容的方法并称之为信息熵information entropy。数据压缩其实是香农的研究工作的一项实际应用它所研究的问题是“在保证信息能恢复的前提下我们能将消息变得多么紧凑”。 对数据进行压缩通常有两个思路 减少数据中不同符号的数量即让“字母表”尽可能小用更少的位数对更常见的符号进行编码即最常见的“字母”所用的位数最少。
60年来的数据压缩研究都可以归结到上面两个重要思路上数据压缩中的每一个算法都聚焦于解决这两件事情中的一件。每一个压缩算法要么通过打乱符号或减少符号的数量将数据转换得更便于压缩要么利用其中一些符号比其他符号更常见的事实通过用最少的位数编码最常见的符号实现压缩的目的。 虽然数据压缩的思路简单明了但在实际应用中数据压缩很复杂。其原因在于由于要压缩的数据的类型不同针对上述两条思路中的每一条能采用的方法都有很多。因此进行实际的数据压缩时需要综合考虑以下因素。 不同数据的处理方法不同比如压缩一本书中的文字和压缩浮点型的数其对应的算法就大不相同。有些数据必须经过转换才能变得更容易压缩。数据可能是偏态的。例如夏天的整体气温偏高也就是说高气温出现的频率比接近零度的气温出现的频率高很多。 互联网诞生的那一年也就是1978年。 在很长一段时间内莱娜图是用来测试图像压缩算法的标准测试图。幸运的是从此以后很少再出现这样有争议性的图像语料库。我们两位作者则更喜欢使用柯达公司的图像测试集。然而即使是今天仍然有很多图像压缩方面的论文将莱娜图用作检验算法的标准。
◆ 第2章 不容错过的一章 数据压缩所做的无非就是尽可能减少表示特定数据集时所需的二进制位数量。 根据信息论的观点一个数值所包含的信息内容等于为了在一个集合中唯一地确定这个数值需要做出的二选一是/否决定的次数。 给定任意一个整数我们都能将它转换为二进制形式。然而令人遗憾的是给定一个整数如果不经过二进制转换这一过程我们很难直接知道它需要占几个二进制位。转换过程很无趣但好在数学家已准备了下面的公式让我们可以更轻松地处理这个问题 L O G 2 ( x ) c e i l ( l o g ( x 1 ) / l o g ( 2 ) ) LOG2(x) ceil(log(x1)/log(2)) LOG2(x)ceil(log(x1)/log(2)) : 表示一个数所需要的二进制位数 给定任意一个十进制整数通过计算它对应的LOG2函数的值我们就能知道用二进制来表示这个数最少需要多少二进制位。香农将一个变量对应的LOG2函数的值定义为它的熵entropy也就是用二进制来表示这个数所需的最少二进制位数。 数值的LOG2表示形式虽然高效但对于制造计算机元件的方式来说并不实用。这其中的问题在于如果用最少的二进制位数来表示一个数在解码相应的二进制字符串时会产生混乱因为我们并不知道该数对应的LOG2长度会与硬件的执行性能相冲突两者不能兼顾。现代计算机采用了折中的方案用固定长度的二进制位数来表示大小不同的整数。最基本的存储单元是一个字节由8个二进制位组成。在现代编程语言中通常可用的整数的存储类型包括短整型16个二进制位、整型32个二进制位、长整型64个二进制位。因此对于十进制数10虽然其对应的二进制数为1010但在实际存储中是短整型在计算机中的实际表示为0000000000001010。显然这样做浪费了很多的二进制位。
◆ 第3章 突破熵 香农博士将一个数对应的LOG2函数值称为该数的熵也就是表示这个数所需要的最少二进制位数。他进一步将熵的概念既然已经提出了这一术语了为什么不重复利用呢……扩展到整个数据集也就是表示整个数据集所需要的最少二进制位数。他完成了所有这方面的数学工作并给出了下面这个优美的公式来计算一个集合的熵 H ( S ) − ∑ i 1 n p i ⋅ l b ( p i ) , l b ( p i ) l o g ( p i ) / l o g ( 2 ) ) H(S) -\sum{i1}^{n}{p{i}} · {lb(p{i})}, lb(p{i}) log(p_{i})/log(2)) H(S)−∑i1n​pi​⋅lb(pi​),lb(pi​)log(pi​)/log(2)) https://rosettacode.org/wiki/Entropy 熵的各种语言实现。 为了使表示某个数据集所需的二进制位数最少数据集中的每个符号平均所需的最小二进制位数就是熵。 从本质上来说香农所定义的熵是以一种倒排序的方式建立在数据流中每个符号出现概率的估算之上的。 总的来说一个符号出现得越频繁它对整个数据集包含的信息内容的贡献就会越少这看起来似乎完全违背直觉。 数据集中包含的总体信息很少因此对应的熵值也很小。 突破熵的关键在于通过利用数据集的结构信息将其转换为一种新的表示形式而这种新表示形式的熵比源信息的熵小。 需要记住的是熵定义的只是在对数据流进行编码时每个符号平均所需的最小二进制位数。这就意味着有些符号需要的二进制位数比熵小而有些符号需要的二进制位数则比熵大。 柯尔莫哥洛夫复杂性Kolmogorov complexity度量的是确定一个对象所需要的计算资源。
◆ 第4章 VLC 摩尔斯码根据各个符号在英语中出现的概率来为其分配点和划。一个符号出现得越频繁其对应的编码就越短。即使是追溯到19世纪这也是对符号分配变长编码variable-length codesVLC的最初实现之一其目的则在于减少传输信息过程中所需要的总工作量。 为了进行数据压缩我们的目的很简单给定一个数据集中的符号将最短的编码分配给最可能出现的符号。 设计VLC集的码字时必须考虑两个原则一是越频繁出现的符号其对应的码字越短二是码字需满足前缀性质。
◆ 第5章 统计编码 统计编码算法通过数据集中符号出现的概率来进行编码使结果尽可能与熵接近。 哈夫曼编码 算术编码 主流的统计编码方法有哈夫曼编码和算术编码但ANS非对称数字系统编码改变了一切。虽然它在数据压缩领域里出现的时间还不长但是已开始取代过去20多年里占据主流地位的哈夫曼编码和算术编码。例如ZHuff、LZTurbo、LZA、Oodle和LZNA这些压缩工具已开始使用ANS。鉴于其速度和性能ANS成为主要的编码方法似乎只是时间问题。实际上在2013年这一算法又出现了一个被称为有限状态熵Finite State EntropyFSE的更注重性能的版本它只使用加法、掩码和移位运算使ANS对开发人员更具吸引力。它的性能是如此强大以至于2015年推出了一款名为LZFSE的GZIP变种作为苹果下一代iOS版本的核心API。
◆ 第6章 自适应统计编码 数据中总会存在某种类型的局部偏态locality-dependent skewing将某些符号、想法或者单词集中在数据集的某个子区间里。 ◆ 第7章 字典编码 虽然信息论的创立是在20世纪40年代哈夫曼编码的提出是在20世纪50年代而互联网的出现在20世纪70年代但是直到20世纪80年代数据压缩才真正引起了人们的兴趣。随着互联网的快速发展人们分享的内容已不再局限于文字而是开始分享比文本大得多的照片以及其他格式的数据。同时这种分享又发生在网络带宽有限、存储昂贵的时期数据压缩因此成了缓解这些瓶颈的关键。虽然VLC一直都在发挥作用但它与熵绑定的事实也限制了数据压缩未来的发展。因此当大多数研究人员在尝试寻找更有效的VLC技术时也有少数研究人员选择了不同的路他们找到了使统计压缩可以更有效地预处理数据的新方法。这种新方法通常被称为“字典转换”dictionary transforms它完全改变了人们对数据压缩的认知。突然间压缩变成了一种对各种类型的数据都有用的算法。它的应用范围非常广泛事实上今天所有的主流压缩算法比如GZIP或者7-Zip都会在核心转换步骤中使用字典转换。 字典编码的关键是要找到那些能生成最小熵的词。1977年两位研究人员Abraham Lempel和Jacob Ziv提出了几种解决“理想分词”问题的方法。这些算法根据提出的年份分别被命名为LZ77 和LZ78它们在找出最佳分词方面非常高效30多年来还没有其他算法可以取代它们。
◆ 第8章 上下文数据转换 给定一组相邻的符号集对它们进行某种方式的变换使其更容易压缩。我们通常称这样的变换为“上下文变换”contextual transform因为在思考数据的理想编码方式时这些方法考虑到了邻近符号的影响。 这些变换的目标是一致的即通过对这些信息进行某种方式的变换使统计编码算法对其进行压缩时更高效。 变换数据的方法有很多种但其中有3种对现代的数据压缩来说最为重要即行程编码(run-length encodingRLE、增量编码delta coding和伯罗斯–惠勒变换Burrows-Wheeler transformBWT。 增量编码的目的就是缩小数据集的变化范围。更确切地说是为了减少表示数据集中的每个值所需要的二进制位数。
◆ 第9章 数据建模 LZ、RLE、增量编码以及BWT这些算法都是基于这样的假设数据的相邻性与它的最佳编码方式有关。 其中游程编码Run-Length Encoding比较适合针对数据中冗余部分比较多的情况 ◆ 第13章 序列化数据 序列化是将高级数据对象转化为二进制字符串的过程与之相反的过程则称为反序列化 相关资料 [笔记] 数据压缩入门Understanding Compression | Fu Zhe’s Blog (fuzhe1989.github.io)LZW压缩算法原理解析 - 个人文章 - SegmentFault 思否