Dav*_*vid 24
一个好的起点是查找霍夫曼压缩方案.霍夫曼背后的基本思想是,在给定文件中,某些字节比其他字节更频繁出现(在纯文本文件中,许多字节根本不会出现).而不是花费8比特来编码每个字节,为什么不使用较短的比特序列来编码最常见的字符,而使用较长的序列来编码较不常见的字符(这些序列通过创建霍夫曼树来确定).
一旦你掌握了使用这些树来根据字符频率对文件进行编码/解码的想法,想象一下你开始处理字频 - 而不是将"它们"编码为4个字符的序列,为什么不认为它是单个字符字符由于其频率,允许在霍夫曼树中为其分配自己的叶子.这或多或少是ZIP和其他无损类型压缩的基础 - 它们在文件中寻找常见的"字"(字节序列)(如果足够常见,则包括仅1个字节的序列)并使用树对它们进行编码.然后,zip文件只需要包含树信息(每个序列的副本及其出现的次数),以允许重建树以及要解码的文件的其余部分.
跟进:
为了更好地回答原始问题,无损压缩背后的想法不是删除空白空间,而是删除重复信息.
如果您创建了一个存储音乐歌词的数据库,您会发现有很多空间用于存储多次重复的合唱.你可以简单地在合唱线的第一个实例之前放置单词CHORUS,然后每次重复合唱时,只需使用CHORUS作为占位符(实际上这几乎就是这个想法)在LZW压缩之后 - 在LZW中,歌曲的每一行都会有一个数字显示在它之前.如果一首行在歌曲中稍后重复,而不是写出整行,只显示数字)
基本概念是,不是使用8位来表示每个字节,而是使用更短的表示来表示更频繁出现的字节或字节序列.
例如,如果您的文件仅包含A重复十六次的字节0x41(),则不是将其表示为8位序列,01000001而是将其缩短为1位序列0.然后该文件可以表示为0000000000000000(十六0秒).那么0x41重复十六次的字节文件可以由0x00重复两次的字节组成的文件表示.
所以我们在这里得到的是,对于这个文件(0x41重复十六次),这些位01000001不会在该位上传达任何附加信息0.因此,在这种情况下,我们丢弃无关的位以获得更短的表示.
这是压缩背后的核心理念.
另一个例子,考虑八字节模式
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
现在重复2048次.遵循上述方法的一种方法是使用三位表示字节.
000 0x41
001 0x42
010 0x43
011 0x44
100 0x45
101 0x46
110 0x47
111 0x48
现在我们可以通过00000101 00111001 01110111(这是三字节模式0x05 0x39 0x77)重复上述字节模式来重复2048次.
但更好的方法是表示字节模式
0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
单位0.然后我们可以通过0重复2048次表示上述字节模式,这将成为0x00重复256次的字节.现在我们只需要存储字典
0 -> 0x41 0x42 0x43 0x44 0x45 0x46 0x47 0x48
并且字节模式0x00重复256次,我们将文件从16,384字节压缩到(模数字典)256字节.
简而言之,压缩是如何工作的.整个业务归结为在给定文件中找到字节和字节序列的简短有效表示.这是一个简单的想法,但细节(找到表示)可能非常具有挑战性.
参见例如: