数据压缩算法

Question

43

我想知道是否有人有数据压缩算法列表。我对数据压缩基本上一无所知，希望了解不同的算法，并看看哪些是最新的，且尚未在许多ASIC上开发。

我希望实现一种数据压缩ASIC，它独立于输入数据的类型（音频、视频、图像等）。

如果我的问题过于开放，请告诉我，我会进行修改。谢谢

- Veridian

1

嗯，有很多压缩算法，你在寻找“最佳”方面是指速度、完全无损还是最高的压缩比？至于哪些算法有专门为它们设计的ASIC，那更多是一个研究问题。我相信大多数主流的压缩算法都有某种形式的ASIC实现。 - Nomad101

1

http://www.ccs.neu.edu/home/jnl22/oldsite/cshonor/jeff.html - taocp

1

@taocp 链接失效 - nz_21

5个回答

5

以下是一些无损算法（可以使用这些完全恢复原始数据）：

许多知名格式，如png或gif，使用这些算法的变种或组合。

另一方面，也有失真算法（为了压缩数据而牺牲精度，但通常效果良好）。最先进的失真技术结合了差分编码、量化和DCT等思想。

要了解更多关于数据压缩的内容，我推荐阅读https://www.elsevier.com/books/introduction-to-data-compression/sayood/978-0-12-809474-7。这是一本非常易懂的介绍性文本，第三版可在网上以pdf形式获取。

- sma

4

我的论文《缓存和主存储器系统中数据压缩的架构方法调查》（永久链接在此）综述了许多数据压缩算法以及在现代处理器中使用它们的技术。它综述了研究级别和商业级别的压缩算法/技术，因此您可能会找到一个尚未在ASIC中实现的算法。

- user984260

4

有很多数据压缩算法。如果你正在寻找百科全书式的内容，我推荐Salomon等人的《数据压缩手册》，它是你能得到的最全面的（并且还有关于数据压缩原理和实践的好章节）。

我最好的猜测是ASIC-based压缩通常是为特定应用程序实现的，或者作为SoC的专门元素实现，而不是作为独立的压缩芯片。我也怀疑寻找“最新和最伟大”的压缩格式不是这里的正确方法 - 我会期望标准化、成熟度和适合特定目的更为重要。

- comingstorm

0

LZW或Lempel Ziv算法是一种非常优秀的无损算法。伪代码在这里：http://oldwww.rasip.fer.hr/research/compress/algorithms/fund/lz/lzw.html

- schilippe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user123 · Accepted Answer

有很多种压缩算法可用。在这里你需要的是一种无损压缩算法，它可以将数据压缩，以便可以将其解压缩为与压缩前完全相同的内容。相反的是有损压缩算法，它可以从文件中删除数据。PNG图像使用无损压缩，而JPEG图像则可以并且通常使用有损压缩。

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

ZIP档案使用Huffman编码和LZ77的组合，以提供快速压缩和解压缩时间，以及相当不错的压缩比。

LZ77基本上是RLE的一个广义形式，通常会产生更好的结果。

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

aaaaaaaabbbbbcccdd

哈夫曼编码的典型实现将会得到以下映射:

Bits Character
   0         a
  10         b
 110         c
1110         d

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

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

18字节减少到5字节。当然，表必须包含在文件中。这个算法在处理更多数据时效果更好:P

Alex Allain写了一篇关于Huffman压缩算法的不错的文章，如果维基百科不足够的话。

如需更多信息，请随时询问。这个主题相当广泛。