logo标签列表

一组整数的最佳压缩算法

algorithmcompression
79

我有一个大的数组，其中包含一系列整数，这些整数大多数是连续的，例如1-100、110-160等。所有整数都是正数。 哪种算法最适合压缩这个数组？

我尝试了deflate算法，但只能让我压缩50％。 请注意，该算法不能有损。

所有数字都是唯一的且逐步增加。

另外，如果您可以为我指出这种算法的java实现，那就太好了。

如果您提供一个真实/更大的样本数据集，也许您会得到更好的答案？ - conny
好的，这里有一个关于数据的例子 -int[] data; for (int i =0;i < SIZE; i++) { data[i] = i; }但是，在某些情况下，分布可能不完全连续，例如我们可能有从1-100的值，然后是从122-230的值。 但是，所有的值都是唯一且始终递增的。 - pdeva
9
你已经通过描述你的序列的方式提供了很好的压缩。 - sbeliakov
15个回答
2

我无法将压缩比提高到0.11以上。我通过Python解释器生成了测试数据，这是一个由1-100和110-160的整数组成的换行分隔列表。我使用实际程序作为数据的压缩表示。我的压缩文件如下：

main=mapM_ print [x|x<-[1..160],x`notElem`[101..109]]

这只是一个Haskell脚本，可以通过以下方式生成可运行的文件：

$ runhaskell generator.hs >> data

g.hs文件的大小为54字节，Python生成的数据为496字节。这使得压缩比为0.10887096774193548。我认为如果有更多时间，可以缩小程序，或者可以压缩已经压缩过的文件（即Haskell文件）。

另一种方法可能是保存4个字节的数据。每个序列的最小值和最大值，然后将它们提供给一个生成函数。尽管如此，加载文件会给解压缩器添加更多字符，增加复杂性和解压缩器的字节数。同样，我通过一个程序表示了这个非常具体的序列，它并不通用，它是一种特定于数据的压缩。此外，增加通用性会使解压缩器变得更大。

另一个问题是必须拥有Haskell解释器才能运行此程序。当我编译程序时，它变得更大了。我真的不知道为什么。Python也存在同样的问题，所以也许最好的方法是给出范围，以便某些程序可以解压缩文件。

2
我建议看一下Huffman编码，它是算术编码的一个特殊情况。在这两种情况下，你需要分析起始序列以确定不同值的相对频率。出现更频繁的值使用比较少的比特进行编码，而出现较少的值则需要使用更多的比特。
1
正如我所提到的，数组中的所有值都是唯一的，没有重复。 - pdeva
抱歉，我想我应该更明确：你当然需要像RLE建议那样预处理你的集合。 - Martin
1
如果增量大多数是+1，对增量进行哈夫曼编码应该非常高效。 - Mark Lakata
1

你的情况非常类似于搜索引擎中索引的压缩。常用的压缩算法是PForDelta算法和Simple16算法。您可以使用kamikaze库来满足您的压缩需求。

1

你应该使用的基本思路是，对于每个连续整数范围（我将称之为范围），存储起始数字和范围大小。例如，如果你有一个包含1000个整数的列表，但只有10个不同的范围，你可以仅存储20个整数（每个范围1个起始数字和1个大小）来表示这些数据，这将是98%的压缩率。幸运的是，还有一些更多的优化可以帮助处理范围更大的情况。

  1. 存储偏移量，相对于前一个起始数字而不是起始数字本身。这样做的好处是，您存储的数字通常需要更少的位数（这可能在以后的优化建议中会派上用场）。此外，如果您只存储了起始数字，这些数字将全部是唯一的，而存储偏移量则有机会使数字接近或甚至重复，这可能允许在之后应用另一种方法进行进一步压缩。

  2. 对于两种类型的整数，使用尽可能少的位数。您可以迭代数字以获取起始整数的最大偏移量以及最大范围的大小。然后，您可以使用最有效地存储这些整数的数据类型，并在压缩数据的开头简单地指定数据类型或位数。例如，如果起始整数的最大偏移量仅为12,000，而最大范围为9,000，则可以为所有这些使用2字节无符号整数。然后，您可以将2,2这对数字塞入压缩数据的开头，以显示两个整数都使用了2字节。当然，您可以使用一些位操作将此信息适配到单个字节中。如果您熟悉大量的位操作，您可以将每个数字存储为最小可能的位数，而不是符合1、2、4或8字节表示。

通过这两个优化，让我们来看几个例子（每个例子都是4,000字节）：

  1. 1,000个整数，最大偏移量为500，10个范围
  2. 1,000个整数，最大偏移量为100，50个范围
  3. 1,000个整数，最大偏移量为50，100个范围

没有优化

  1. 20个整数，每个4个字节=80个字节。压缩率=98%
  2. 100个整数，每个4个字节=400个字节。压缩率=90%
  3. 200个整数，每个4个字节=800个字节。压缩率=80%

有优化

  1. 1 字节头 + 20 个数字，每个占用 1 字节 = 21 字节。压缩率 = 99.475%
  2. 1 字节头 + 100 个数字，每个占用 1 字节 = 101 字节。压缩率 = 97.475%
  3. 1 字节头 + 200 个数字，每个占用 1 字节 = 201 字节。压缩率 = 94.975%
说一下，变长编码将允许您偶尔具有大值而无需使所有内容变宽。 - Marc Gravell
0

如果您有一系列重复的值，RLE是最容易实现且可以给您带来良好结果的算法。然而，其他更先进的算法，如考虑熵的LZW（现在不受专利保护），通常可以实现更好的压缩。

您可以在这里查看这些和其他无损算法。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接