整数压缩方法 [英] integer compression method

问题描述

有一个大数组，其整数范围大多不连续，例如1-100,1-1000等。所有整数都是正数。压缩它的最佳算法是什么？



所有数字都是唯一且不同的增加。



另外，如果你能指出这种算法的vb.net实现很棒。

have a large array with a range of integers that are mostly not continuous, eg 1-100,1-1000 etc. All integers are positive. What would be the best algorithm to compress this?

All numbers are unique and different increasing.

Also if you can point me to the vb.net implementation of such algorithm that would be great.

推荐答案

你可以使用System.IO.Compression命名空间 [ ^ ]。

Quote：

有一个大数组，其整数范围大多不连续，例如1-100,1-1000等。

have a large array with a range of integers that are mostly not continuous, eg 1-100,1-1000 etc.

我不清楚。

This is not clear to me.

Quote：

所有数字都是唯一且不同的增加。

All numbers are unique and different increasing.

如果数字属于一个范围（例如 1-10000 ）那么您可以只使用必要的位来存储它们（ 14 位足以存储 0-16383 ）。

对于单调增加的数字，您可以存储第一个数字，然后存储下一个数字和前一个数字之间的差异。存储这些差异通常比存储整个数字需要更少的比特。

当然，您也可以尝试使用像Richard建议的那样可用的通用压缩工具。

If the numbers belongs to a range (e.g. 1-10000) then you may use just the necessary bits to store them (14 bits are enough for storing 0-16383).
For number increasing monotonically you may store the first number and then the differences between the next and the previous. Storing such differences usually requires fewer bits than storing the whole numbers.
Of course you may also try an available, general compression facility like the one suggested by Richard.

如果您的数字正在增加，请计算差异，如CPallini所说，并观察这些增量的直方图。



如果增量经常重复，您可以使用霍夫曼对它们进行编码（最常用的值用较少的位编码）。



如果计算直方图的熵，可以告诉你有多少位信息将在压缩后保留。

If your numbers are increasing, compute the differences, as CPallini said, and observe the histogram of these deltas.

If the deltas are repeating often enough, you can use Huffman encoding on them (most frequent values encoded with fewer bits).

If you compute the "entropy" of the histogram, that can tell you how many bits of information will remain after compression.

这篇关于整数压缩方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！