文件压缩是如何工作的？

Question

所以，我今天意识到我认为文件压缩是理所当然的。能够将几个文件捆绑在一起，并使其比任何一个文件都小，这是我接受的事实，但它实际上是如何工作的？

我对它的了解有限，包括用指针替换所有重复条目，以这种方式缩小，但除此之外我相当无能为力！

因为我总是对新知识持开放态度，正如我想象我们这里的大多数人一样，我想我会问。那么，超级用户，压缩实际上是如何工作的？

Answer 1

无损压缩

无损压缩是没有数据丢失的地方。输入的所有内容都可以完美检索。这适用于将注意到最小错误的文本或二进制文件。

文件压缩的​​工作原理是获取文件并扫描模式，然后将这些模式转换为占用较少空间的其他内容。

例如“AAAAAAAAA”可以变成“8A”。

当然，这不是它的工作原理，因为如果“8A”在明文中，您会遇到问题。你会解压缩文件，它会是错误的。一个好的起点是 Wikipedia 或LZW 数据压缩算法。

下面复制了一些简单的伪代码：

STRING = get input character
WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
        STRING = STRING+character
    ELSE
        output the code for STRING
        add STRING+CHARACTER to the string table
        STRING = CHARACTER
    END of IF
END of WHILE
output the code for STRING

所有压缩都使用用于压缩和解压缩文件的查找字典。字典越大，你就越能压缩它，尽管你确实遇到了收益递减法则。

还值得注意的是，压缩并不总是产生较小的文件。在某些情况下（对于小文件，或压缩随机数据时），压缩后您将无法获得较小的文件。有一些有趣的挑战与压缩随机数据的能力有关。

“有损”压缩

以上主要与无损压缩有关。MP3、JPG 和 h.264 等视频/音频应用程序中使用的其他类型的压缩是有损压缩的示例。

有损压缩的工作原理是丢弃最不可能被注意到的数据。在音频中，这是大约 30,000 赫兹和低于 100 赫兹的声音，以及其他各种声音。在图片（静态）中，它删除各种事物并将像素合并在一起，同时丢弃数据。

有损压缩是一种变换编码形式。它平均数据以减少整体大小。例如，图像中 10 个像素的块，所有略有不同的颜色可能会合并为一种颜色，从而进行压缩。

在视频压缩中，通常会放置指令以仅重绘自上一帧或关键帧以来发生变化的像素。

Answer 2

压缩的工作原理是在数据中查找模式，然后用特殊的较小模式替换这些模式。解压是相反的：找到特殊的模式，并用它们代表的更大的模式替换它们。知道什么模式是可能的很重要；例如，在文本中发现的模式可能与在图像中发现的模式完全不同。一些压缩技术是有损的；他们不保证扩展会准确地恢复输入。如果损失足够小，这通常适用于模拟数据，例如音乐和图像。但是文本等数据必须使用无损技术进行压缩。

重要的是要认识到，即使是一个比特，也不可能在不丢失的情况下压缩随机数据。考虑一个包含 N 位二进制数据的文件。有 2^N 个可能的文件。如果将这些文件中的任何一个压缩一位，那么压缩文件的大小为 N-1 位，则只有 2^(N-1) 种可能的压缩表示。换句话说，每个可能的压缩文件必须代表多个可能的未压缩文件。如果没有唯一的压缩表示，解压算法就不能保证无损解压。