BucketCompressionTrick:在一个16位值中存储4个5位值的绝妙技巧

铲斗压缩技巧 它是什么？ 当我们不在乎那些5位值的顺序并且想要真正接近Shannon极限时，将四个5位值有效地压缩为单个16位值是一个巧妙的小技巧。 这对于将诸如一系列顺序无关的选项之类的东西存储在一个非常大的哈希表中的条目或条目标识符中很有好处。 请注意，即使对于值> 5位，如果我们愿意移动其余部分以匹配这5位的排序顺序，我们仍然可以应用此技巧，但是显然，您不想只为了将几百个字节改组就可以了。节省4位。 它是如何工作的？ 通过对数字的顺序进行交易控制来实现四个数字的额外精度，此技巧起作用。 对于4个4位值的多集，有multichoose（2 4，4 ）= 3876个可能的唯一值，而对于16位整数，则有65536个可能的唯一值。 log2（multichoose（2 4，4 ））= 11.92因此，如果我们可以将所有可能的值映射到12位表示形式，它将为我们留出4位可用，这足以将多余