数据压缩入门

不容错过的一章

｜

15

这里最终的输出值是二进制值

1010

，这个值很有意思，它恰好是我们要查找的数值

10

的

二进制形式。对元素个数等于２

n

–1

的数据集，我们通过记录为了明确描述一个数，做了多

少次“是”或“否”的决定，来表示这个数。

如果你希望能在聚会中独处，不妨试试与其他人讨论这个话题。我敢肯定，

这样做之后，你很快就会成为那个很尴尬的人。

2.2.2

　熵

：

表示一个数所需要的最少二进制位数

可以看到，给定任意一个整数，我们都能将它转换为二进制形式。然而令人遗憾的是，给

定一个整数，如果不经过二进制转换这一过程，我们很难直接知道它需要占几个二进制

位。转换过程很无趣，但好在数学家已准备了下面的公式，让我们可以更轻松地处理这个

问题

4

：

lb(

x

)

=

(log(

x

)/log(2))

=

表示一个数所需要的二进制位数

从数学上来说，

lb

将产生一个浮点数，例如，

lb(10)

=

3.321

。

然而，从技术角度来说，由于现代的计算机硬件无法表示

3.321

个二进制位（这是因为二进

制位已经是数据的最小单位，我们能使用的最小的二进制位数就是

1

），因此我们必须对这

个值向上取整，也就是使用向上取整函数，即

ceil

（或

ceiling

）函数，从而将上面的公式更

新为下式（由于这是一个更整洁的版本，因此我们决定用大写字母来表示，以示区别）：

LOG2(

x

)

=

ceil(log(

x

)/log(2))

不过，这又产生了另外一个问题，因为从技术上来说，如果一个数正好是

2

的幂，那么通

过这一公式所得的结果要比实际需要的二进制位数小

1

。