数据压缩算法

Question

我想知道是否有人有数据压缩算法的列表。我基本上对数据压缩一无所知，我希望学习更多关于不同算法的知识，看看哪些算法是最新的，还没有在许多ASIC上开发。

我希望实现一个数据压缩ASIC，它独立于传入的数据类型(音频、视频、图像等)。

如果我的问题太开放，请让我知道，我会修改的。谢谢

Answer 1

市面上有大量的压缩算法。这里你需要的是一个无损压缩算法。无损压缩算法对数据进行压缩，这样就可以对其进行解压缩，以达到压缩前给定的效果。相反的是有损压缩算法。有损压缩可以从文件中删除数据。PNG图像使用无损压缩，而JPEG图像可以并且经常使用有损压缩。

一些最广为人知的压缩算法包括：

• RLE
• Huffman
• LZ77

ZIP归档使用霍夫曼编码和LZ77的组合来提供快速的压缩和解压缩时间，和具有相当好的压缩比。

LZ77几乎是RLE的一种推广形式，它通常会产生更好的结果。

Huffman允许重复最多的字节来表示最少的比特数。想象一个文本文件，它看起来像这样：

aaaaaaaabbbbbcccdd

Huffman的典型实现将产生以下映射：

Bits Character
   0         a
  10         b
 110         c
1110         d

因此，该文件将被压缩为：

00000000 10101010 10110110 11011101 11000000
                                       ^^^^^
                              Padding bits required

18个字节变成5个字节。当然，表必须包含在文件中。此算法在数据越多时效果越好:P

Alex Allain有关于霍夫曼压缩算法的a nice article，以防维基不够用。

请随时询问更多信息。这个话题相当广泛。

Answer 2

我的论文A Survey Of Architectural Approaches for Data Compression in Cache and Main Memory Systems (permalink here)回顾了许多压缩算法，以及在现代处理器中使用它们的技术。它回顾了研究级和商业级的压缩算法/技术，因此您可能会发现其中一种尚未在ASIC中实现。

Answer 3

以下是一些无损算法(使用这些算法可以完美地恢复原始数据)：

• LZ78(和LZW variation)
• LZ77
• Arithmetic coding
• Sequitur
• prediction

partial match (Ppm)

• LZ78

的哈夫曼代码

许多众所周知的格式，如png或gif，都使用这些格式的变体或组合。

另一方面，也有一些有损算法(为了压缩数据而影响精度，但通常效果很好)。最先进的有损技术结合了差分编码、量化和DCT等技术的思想。

要了解有关数据压缩的更多信息，我推荐使用https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7。这是一个非常容易理解的介绍文本。第三版在pdf online上发布。