【技术白皮书】外功心法 | 第五部分 | 亲身体验数据压缩之旅

亲身体验数据压缩之旅热身问题前提介绍压缩技术的基本原理行程长度编码Run-Length Encoding (RLE)有损压缩和无损压缩文件以字节为单位保存文件是字节数据的集合体行程长度编码算法计算RLE压缩比RLE的算法逻辑RLE算法在传真中的应用RLE的算法的缺点文件类型分析哈夫曼编码算法哈夫曼编码核心思想莫尔斯编码莫尔斯编码的分析二叉树实现哈夫曼编码二叉树哈夫曼算法的实现出现频率和编码构建哈夫曼树步骤一步骤二步骤三压缩算法的总结说明热身问题的答案解析热身问题文件储存的基本单位是什么DOC、LZH和TXT这些扩展名中哪一个是压缩文件的扩展名文件内容用“数据的值×循环次数”来表示的压缩方法是RLE 算法还是哈夫曼算法在 Windows 计算机经常使用的 SHIFT JIS 字符编码中1个半角英数是用几个字节的数据来表示的BMPBITMAP格式的图像文件是压缩过的吗你是不是发现有些问题并不像表面看起来那样简单最后笔者的答案和解析或许能为你提供一些参考。前提介绍要理解文件压缩的原理首先需要知道文件中存在着大量的“冗余信息”。简单来说就是文件里有很多重复出现的数据或者可以用更简洁方式表示的信息。比如一篇文章里可能多次出现“的”“是”“在”这样的常用字或者一张图片中某一区域的像素颜色完全相同。这些重复或可简化的信息就是压缩的对象。压缩技术的基本原理压缩技术的核心就是通过特定的算法将这些冗余信息进行“精简”或“替代”从而减少文件所占用的存储空间。行程长度编码Run-Length Encoding (RLE)一种简单的压缩思路即“行程长度编码”RLE。当然实际的压缩算法要复杂得多但基本逻辑都是通过识别和消除数据中的冗余来实现体积的减小。文本文件为例假设一段文字是“ABABABABAB”这里“AB”重复了5次。如果直接存储需要10个字符的空间。但如果我们用一种算法记录为“AB 5”意思是“AB”这个组合重复了5次那么只需要很少的空间就能表示同样的内容。有损压缩和无损压缩图像、音频、视频等多媒体文件冗余信息的表现形式更加多样。比如BMP格式的位图图像每个像素的颜色信息都是独立存储的即使相邻像素颜色相同也不例外这就存在大量空间冗余。有损压缩JPEG格式则会通过离散余弦变换等方法将图像从空间域转换到频率域然后对高频部分人眼不太敏感的细节进行量化和丢弃从而实现高效压缩。这种压缩会损失一部分数据因此被称为“有损压缩”无损压缩像ZIP格式对文本文件的压缩通常能精确还原原始数据属于“无损压缩”。无论是哪种方式都是利用数据本身的特性通过数学和逻辑的方法去除冗余让文件“变瘦”。文件以字节为单位保存在探讨文件压缩机制的细节之前让我们首先剖析数据在文件中的存储形式。文件作为数据在磁盘等存储介质中的组织形式其基本存储单元是字节。程序文件中的信息正是以字节为单位进行存储的这正是文件大小通常以KB、MB等计量单位表示的原因其中B代表Byte字节。文件是字节数据的集合体文件是字节数据的集合。1字节等于8位可表示256种数据用二进制表示范围为0000000011111111。{{{width“auto” height“auto”}}}存储文字的文件是文本文件存储图形的文件是图像文件。无论何种文件字节数据都是连续存储的需注意这一点。行程长度编码算法在上一节中我们已经对行程长度编码算法RLE有了基本的了解。现在让我们更深入地分析这一算法并探讨它是如何应用于文件压缩的。为了更好地理解这一点我们将以一个包含17个半角字符的文件文本文件为例进行压缩演示尽管这些字符本身没有实际意义但它们非常适合用来解释RLE算法的压缩机制。这个文件的内容是AAAAAABBCDDEEEEEF。由于在半角字母中每个字符均以1个字节的形式保存在文件中因此上述文件的大小即为17个字节。那么我们该如何压缩这个文件呢这确实值得大家思考一番。只要最终能使文件大小小于17字节任何压缩方法都是可以尝试的。计算RLE压缩比在此时人们或许会采用一种将文件内容压缩的策略即以“字符乘以重复次数”的形式来表示。当观察诸如AAAAAABBCDDEEEEEF这样的数据时不难发现其中存在大量重复的字符。在每个字符后标注其重复出现的次数AAAAAABBCDDEEEEEF便可简洁地表示为A6B2C1D2E5F1。如此一来原本的数据便被转换为仅有12个字符即12字节从而实现了对原文件的压缩相较于原本的17字节减少了70%。恭喜你成功地完成了数据压缩RLE的算法逻辑将文件内容以“数据 × 重复次数”的形式进行表示的压缩方法被称为RLERun Length Encoding行程长度编码算法。{{{width“auto” height“auto”}}}RLE算法是一种颇为有效的压缩手段经常被应用于压缩传真图像等文件。由于图像文件在本质上也是字节数据的集合因此可以利用 RLE 算法进行压缩处理。RLE算法在传真中的应用RLE算法在传真FAX等领域的应用十分广泛。以G3类传真机为例其在发送文字和图形时均将其视为黑白图像进行处理。由于在黑白图像的数据中白色或黑色像素往往会出现连续的情况因此无需逐一发送每个像素的值而是通过记录连续相同颜色的像素数量来实现数据的压缩从而显著提高了压缩效率。例如对于一幅图像其中白色像素连续出现5次接着是黑色像素连续出现7次再然后是白色像素连续出现4次最后是黑色像素连续出现6次那么我们可以将这段图像数据压缩为表示重复次数的字符串“5746”。通过这种方式RLE算法有效地减少了数据的存储空间和传输带宽。RLE的算法的缺点然而在实际的文本文件中相同字符频繁重复出现的情况并不多见。尽管RLE算法在处理图像、文件等时常有相同数据连续出现的情形时表现良好但它并不适用于文本文件的压缩。不过由于这种压缩机制极为简单采用RLE算法的程序也相对易于编写。文件类型压缩前文件大小压缩后文件大小压缩比率文本文件14862 字节29506 字节199%图像文件96062 字节38328 字节40%EXE 文件24576 字节15198 字节62%应用 RLE 算法对文本文件进行压缩后文件大小反而增加了几乎是压缩前的两倍。这是因为在文本文件中连续出现相同字符的情况并不多见。例如对于存储了 “This is a pen.” 这 14 个字符的文本文件使用 RLE 算法压缩后变成了 “T1h1i1s1 1i1s1 1a1 1p1e1n1.1”总共 28 个字符是压缩前的两倍。由于文章中字符大量连续出现的情况并不多见因此使用 RLE 算法后大部分字符后面都会加上 1这样压缩后的文件自然就变成了之前的的两倍。压缩后同压缩前文件大小的比率称为压缩比率或压缩比文件类型分析相较于文本文件图像文件的压缩比率A成功达到了40%。而程序的EXE文件压缩比率更是高达60%这是由于在EXE文件中连续的数据部分初始值为0的情况十分常见。此外我们还可以在RLE算法的基础上进行进一步优化不再以单个字符为单位而是以字符串为单位来检测重复次数。例如在句子This is a pen.中is重复出现了两次。通过运用这一压缩技巧压缩后的文件体积能进一步减小。由此可见压缩效率的高低往往取决于所投入的努力和方法的巧妙程度。哈夫曼编码算法接下来我们探讨第二种值得关注的压缩技巧——哈夫曼法。这种由D. A. Huffman在1952年提出的压缩算法在数据压缩领域占据了举足轻重的地位。值得注意的是哈夫曼算法被广泛应用于日本人日常使用的压缩软件LHA中。LHA 是吉崎荣泰开发的一款免费压缩软件。为了更深入地理解哈夫曼算法我们首先需要摒弃一个固有观念即“半角英文数字的一个字符占用一个字节8位的数据”。文本文件实际上是由多种不同类型的字符组合而成的并且这些字符在文件中出现的频率也各不相同。哈夫曼编码核心思想例如在某一文本文件中字母A可能出现大约100次而字母Q可能仅出现3次这种情况十分常见。哈夫曼算法的核心思想在于对于频繁出现的数据使用小于8位的字节数进行编码表示而对于不常用的数据则可以采用超过8位的字节数表示。如果A和Q都用8位来表示原始文件的大小将是100次乘以8位加上3次乘以8位即824位。然而如果假设A用2位表示Q用10位表示压缩后的文件大小则是100次乘以2位加上3次乘以10位即230位。无论数据不足8位还是超过8位最终都会以8位为单位保存至文件中。原因在于磁盘存储数据的基本单位是字节即8位如下图所示。为实现这一操作压缩程序的内部逻辑将变得更为复杂但作为补偿其最终实现的压缩效率也将显著提高。{{{width“auto” height“auto”}}}接下来我们暂时将当前话题搁置一旁以便更深入地探讨哈夫曼算法。在此之前让我们先了解一下莫尔斯编码。莫尔斯编码由塞缪尔·芬利·布里斯·莫尔斯于1837年首次提出它并不是依靠语言进行信息传递而是通过巧妙地组合长点和短点即‘嗒’和‘嘀’的声音来实现文本信息的交流。莫尔斯编码莫尔斯编码的基本规则即短点表示0长点表示1每个字符通常由8位组成。然而实际上莫尔斯电码的符号长度会根据不同字符而变化。在这些编码中我们可以将“1”视为短点嘀而“11”则视为长点嗒。这种编码方式通过不同的信号长度和间隔有效地传递了各种字符信息。字符对应的位数据位长A10114 位B110101018 位C1101011019 位D1101016 位E11 位F101011018 位字符间隔002 位1 短点、 11 长点、 0短点和长点的分隔符莫尔斯编码的分析莫尔斯编码用短编码表示高频字符这里的频率基于印刷活字的数量而非实际文章统计。例如E嘀编码为1C嗒 嘀 嗒 嘀编码为110101101。实际编码中短点为1长点为3间隔为1长度指声音长度。对于AAAAAABBCDDEEEEEF这17个字符用莫尔斯编码表示为A×6 B×2 C×1 D×2 E×5 F×1 字符间隔×16 106位 ≈ 14字节。文件以字节存储不满1字节需圆整。因此若所有字符占1字节8位这17个字符应为17字节莫尔斯电码的压缩比率为14÷17 ≈ 82%效果不突出。二叉树实现哈夫曼编码莫尔斯编码通过日常文本中各个字符的出现频率来决定其编码长度。然而这种编码方式在处理AAAAAABBCDDEEEEEF这样特殊的文本时却显得不那么适用。在莫尔斯编码体系中字母E的编码长度最短。但是在AAAAAABBCDDEEEEEF这个文本中字母A的出现频率却是最高的。因此如果给字母A分配最短的编码数据长度压缩效果将会更加显著。这样的调整能够更有效地提升压缩率。二叉树哈夫曼算法的实现具体采用何种形式的编码即哈夫曼编码来对数据进行分割完全取决于各个文件自身的特性。经过哈夫曼算法压缩处理后的文件不仅包含了至关重要的哈夫曼编码信息还存储了经过压缩处理的数据。这种算法巧妙地利用编码体系来提升压缩效率从而在数据存储和传输中发挥着重要作用。{{{width“auto” height“auto”}}}接下来让我们尝试对字符串AAAAAABBCDDEEEEEF中的字符A至F依据“高频字符使用短编码”的原则进行编码整理。按照字符出现频率从高到低的顺序整理结果如下表所示。该表同时列出了所提出的编码方案。出现频率和编码字符编码的数据位数随出现频率降低而增加从1位、2位到3位。但此编码体系存在问题如100三位编码无法区分是表示E、A、A还是B、A或C。因此无区分符号的编码方案不可用。字符出现频率编码方案位数A601E511B2102D2112C11003F11013哈夫曼算法通过构建哈夫曼树来创造编码体系无需字符区分符号即可实现明确区分的编码。尽管各字符的数据位数不同也能制成可区分的编码。掌握哈夫曼树的制作方法并通过程序实现即可利用哈夫曼算法压缩文件。但与RLE算法相比程序更为复杂。构建哈夫曼树如何构建哈夫曼树。在自然界中树是从根部开始生长分枝和树叶的而哈夫曼树的构建过程则恰恰相反它从叶子节点开始逐渐形成树枝最后生成根部。下图展示了对于字符串“AAAAAABBCDDEEEEEF”进行编码时哈夫曼树的构建过程。建议大家也亲自尝试绘制一下通过一次实践你将能够更清晰地理解哈夫曼树的构建顺序和原理。步骤一以下是整理后的数据及其出现频率按降序排列数据频率A6E5B2D2C1F1步骤二从给出的数字中挑选出出现频率最小的两个数字并分别引出两条直线。在这两条直线的交叉点上标注出这两个数字之和。如果存在多种选择可以任意选取其中的一组进行标注。{{{width“auto” height“auto”}}}通过重复执行步骤二你能够连接位于任何位置的数值。{{{width“auto” height“auto”}}}步骤三最终这些数值将汇聚于一点这一关键点便是树的根部至此哈夫曼树便完整构建而成。遵循从树根至叶子的顺序我们将在左侧的树枝上标记0右侧的树枝上标记1。随后从根部出发顺着树枝抵达目标字符依据所经过树枝上的标记依次记录下0或1便生成了哈夫曼编码。{{{width“auto” height“auto”}}}压缩算法的总结说明压缩算法的种类繁多大约有一二十种之多。之所以存在如此众多的压缩算法是因为压缩比率、所需的处理时间程序的复杂程度以及各种文件的需求皆有所不同。因此迄今为止学界尚未能提出一种普遍适用的万能压缩算法。这无疑为各位读者展示才华提供了一个绝佳的机会。大家不妨尝试亲手设计一个独特的压缩算法。不过需要注意的是文本文件不宜进行非可逆压缩。原因想必大家都已心知肚明无需赘述。热身问题的答案解析文件储存的基本单位是什么答案1 字节 8 位 文件是字节数据的集合体。DOC、LZH和TXT这些扩展名中哪一个是压缩文件的扩展名答案LZH 它是用 LHA 等工具压缩过的文件的扩展名。文件内容用“数据的值×循环次数”来表示的压缩方法是RLE算法还是哈夫曼算法答案RLE算法,例如AAABB 这个数据压缩后就是 A3B2在 Windows 计算机经常使用的 SHIFT JIS 字符编码中1个半角英数是用几个字节的数据来表示的答案1 字节 8 位半角英文数字是用 1 个字节来表示的汉字等全角字符是用两个字节来表示的。BMPBITMAP格式的图像文件是压缩过的吗没有压缩过因为BMP格式的图像文件是没有被压缩的因此要比JPEG格式等压缩过的图像文件大不少。