我有一段数据,可以是从1到7的数字.我可以将其中的多少压缩成一个字节,以及如何压缩



由于单个字节最多可以容纳256个值,因此每个字节应该可以唯一映射多个值。然而,我不确定我能储存多少而不会丢失。

如果我有一个特定的值范围需要覆盖,有没有一个通用的算法可以做到这一点?

如果我映射到更大的单词大小,我可以改进映射吗?

理想化的答案是一种将大小为n到m位的x(独立)范围映射的算法。

在最一般的情况下,当你有一个从1到7的值(我假设包括在内),这相当于范围[0..6]时,你可以把它想象成基数7中的一个数字。

这意味着它们的字符串形成了一个以7为底的数字。然后,你能做的最简单的事情就是把这个数字存储在一个计算机变量中(实际上,把它变成基数2,但你通常不必考虑这个问题,因为数字就是一个数字。)

现在让我们来计算一下你的值中有多少适合多少位。显然,一个值将适合3位(您将浪费8个值中的1个,即3位中的12.5%)两个值(相当于以7为基数的两位数)的范围为0到48,可容纳6个完整的位(将浪费64个二进制值中的15个,即23.4%)三个值的范围为0到342,将适合9个完整的比特,并浪费大量的值。

我想你可以算出其余的。注意,存储每个数字所需的实际(小数)位数(在本例中为7)根据定义是其以2为底的对数

要以这种方式进行实际编码和解码,您只需要依次乘以7(编码)或除以7(解码),这与您将数字转换为任何其他基数的方式相同。例如,如果您的值是xyz,则以下内容将保持:

// x,y,z must be in [0..6], so probably have to subtract 1 from each first...
// then:
encoded = x * 1 + y * 7 + z * 49;  // encoded will fit in 9 bits.
decoded_x = (encoded /  1) % 7;     // also need a plus one.
decoded_y = (encoded /  7) % 7;     // same
decoded_z = (encoded / 49) % 7;     // ditto

通常,要将[0..m-1]范围内的任意数量的值映射并打包为多个位,请执行与上面相同的操作。将您的每个值想象成m中一个(可能很大的)数字中的一个数字,然后将该数字存储在任何可以容纳它的变量中。

注意1:通常,在一个数字中包含的值越多,浪费的比特就越少。例如,一些评论和其他答案建议将每个以7为基数的值打包为3位。如果这样做,那么在一个32位变量中只能存储其中的10个。但实际上,您可以将11个(整)值打包为32位。诚然,每3位存储1个值的编码和解码速度更快(仅使用移位和掩码),这使得选择取决于您的需求。

注意2:有一些方法可以谈论(并解释)分数位计数。例如,每个以7为基数的数字将占用2.81位。还有其他方法可以将它们编码并存储为集合。但在编码和压缩领域,这是一个更复杂的问题。如果你很好奇,你可以阅读关于";算术编码";。

注意3:说到压缩,有更好的方法可以将多个值打包到多个位中,如果您对它们了解更多。也就是说,如果其中一些更有可能是特定的值,或者彼此相等,或者其他什么。此外,如果有足够多的值,则可以从数据本身提取这些关系。从本质上讲,这就是通用无损压缩机的作用。

注意4:请记住,如果值的范围不相同,您甚至可以进行这种编码和解码(我建议的方式)。例如,如果xz在[0..6]范围内,但y在[0..4]范围内,则可以像这样对它们进行编码和解码:

同样可能的
encoded = x * 1 + y * 7 + z * (7 * 5);  // encoded will fit in 8 bits now!
decoded_x = (encoded /  1) % 7;
decoded_y = (encoded /  7) % 5;
decoded_z = (encoded / 35) % 7;

n符号将采用lg nbit,其中lg是以2为底的对数。您可以存储m位中的floor(m/lg n),将它们编码为m比特,作为基数n整数的数字。

对于n=7m=8,您可以存储2。通常情况下,您会希望选择一个m,使未使用的位数量较少m=48(六个字节)是一个不错的选择,您可以在其中存储17符号717=2232630513987207,接近但小于248=2814749767100656。只有大约四分之一的比特被浪费,或者大约是48个比特的0.5%。此外,可以利用64位算术有效地进行基本转换。

也许我完全误解了你的意思,但一个字节包含8位。每一位都可以是零或一。现在一个字节可以分别处于256种不同的状态,最多可以容纳255个数字。要表示1到7(或0到6)之间的数字,需要三个比特。类似001=1;010=2;011=3。。。等等。所以通常情况下,你可以在一个字节中存储两个介于1到7之间的数字。但是你浪费了两块钱。也许你可以使用重叠的字节。在三个字节中,您可以存储8个值,并且不会浪费任何一位。也许你可以想出一些奇特的算法,在一个字节中存储三个值,但有一些限制。例如,如果您知道至少有一个值与其他值不相同,则可以尝试对字节内的值进行排序。你会想到想象中的第九位。如果第一个值小于第二个值,则为1,否则为0。但是,更深入地了解一些关于数据和用例的额外信息将是非常棒的。

最新更新