第 2 章 · 数据

位、压缩与信息

计算机保存的一切，无论是数字、名字、照片还是歌曲，归根到底都是一串位的模式。

位（二进制数字的简称，bit）不是 0 就是 1。计算设备以数字形式表示数据：任何值最底层的组成部分都是位。

图中是在用二进制计数。每个方块是一位，0 用纸面，1 用红面，位值标在下方：128, 64, 32, 16, 8, 4, 2, 1。每一步加 1：最右边的位翻转，凡是 1 变成 0 的地方，进位就向左传递一位，就像 00000111（7）变成 00001000（8）那样。

程序把数据值保存在变量中、项目的列表中，或者作为独立的常量，并把它们作为输入传给过程，再以输出的形式取回。不管是哪种形式，这些值都是以位的形式存储的，程序再把它们转换成人能读懂的形式。

本章是 AP Computer Science Principles 的大概念 2：数据，占选择题考试的 17–22%：二进制数（2.1）、数据压缩（2.2）、从数据中提取信息（2.3）以及用程序处理数据（2.4）。

2.1 · 同一种模式，多种含义

位被归并成抽象

字节是 8 位。单独看，一个字节没有任何意义：它的含义取决于读取它的程序把它当作什么。

抽象是通过关注主要思想来降低复杂度的过程。抽象把与当前问题无关的细节隐藏起来，把相关而有用的细节集中在一起，让你思考的是这个想法，而不是一个个位。

位可以归并起来表示各种抽象，包括（但不限于）数、字符和颜色。图中用三种方式读取同一个字节 01000001：

所以同一串位在不同的上下文中可以表示不同类型的数据。彩色图像通常每个像素存三个这样的数，红、绿、蓝各一个：3 字节，24 位。

2.1 · 二进制转十进制

位值，从最右边的 0 起编号

包括二进制和十进制在内的各种进制，都被用来表示数据。十进制（基数为 10）只用数字 0–9；二进制（基数为 2）只用 0 和 1。

和十进制一样，数字的位置决定它的值：数值等于该数字乘以其所在位置的位值。位值是基数的位置次幂，位置从最右边的 0 开始编号，向左每次增加 1。在十进制中，305 = 3 × 10² + 0 × 10¹ + 5 × 10⁰。

在二进制中，每一位的值是它右边一位的两倍。对于 10110101：

把位为 1 的位值加起来：128 + 32 + 16 + 4 + 1 = 181。位为 0 则什么也不加。图从左向右读取；每个 1 都把它的位值落入总和中。

2.1 · 十进制转二进制

取能放下的最大位值

要把一个正整数写成二进制，从最大的位值开始往下做：如果这个位值能放进剩下的数里，就写 1 并把它减去；放不下就写 0。

用八位表示 100：

所以 100 = 01100100：64 + 32 + 4 = 100。前导零不改变数值，所以 01100100 和 1100100 是同一个数。

第二种方法：不断除以 2，把余数从最后一个读到第一个。100 ÷ 2 = 50 余 0; 50 ÷ 2 = 25 余 0; 25 ÷ 2 = 12 余 1; 12 ÷ 2 = 6 余 0; 6 ÷ 2 = 3 余 0; 3 ÷ 2 = 1 余 1; 1 ÷ 2 = 0 余 1。从下往上读：1100100。

图中的蓝色条是 100 剩下的部分；每个 1 从条上截下它的位值，并使它的方块变红。

2.1 · n 位，2ⁿ 个值

以及二进制数的比较

一位有 2 种模式。每多一位，数量翻倍：原来的每种模式，一次前面加 0，一次前面加 1。所以 n 位有 2ⁿ 种模式。

图中把它们构造出来：1 位, 2; 2 bits, 4; 3 bits, 8; 4 bits, 16。一个字节有 2⁸ = 256 种模式，即整数 0 到 255。最大的 n 位数是全 1：2ⁿ − 1。

要给 26 个字母各分配一个独一无二的模式，需要多少位？2⁴ = 16 不够；2⁵ = 32 够了：5 位。

比较与排序。让两个数有相同的位数（在前面补零），从左向右扫描。第一个不同的位置决定结果：那里是 1 的数更大，因为这一个位值比它右边所有位值加起来还大（2^p > 2^p − 1）。

01101100 和 01011111 在位置 5 第一次不同，也就是 32 的那一位，第一个数在那里是 1：108 > 95，不管其后的位是什么。

2.1 · 固定位数的限制

溢出与舍入误差

在许多编程语言中，整数用固定的位数表示。这限制了整数值的范围和对它们所做的运算，并可能造成溢出或其他错误。

图中的计数器（假设的）有 4 位：能存 0 到 15。给 15（1111）加 1 需要第五位；进位无处可去，计数器显示 0。这就是溢出。

其他语言提供了一种抽象，其中整数的大小只受计算机内存大小的限制。考试参考表中的语言就属于这一类：它的整数不会溢出。

实数（带小数部分）同样存储在固定的位数中，这限制了它们的范围和对它们所做的运算，并可能造成舍入误差和其他错误：有些实数只能以近似值存储。有 3 位小数位时（图中，假设的），只存在 1/8 = 0.125 的整数倍；0.1 被存为 0.125，差了 0.025。

真实的语言用的位数多得多，所以误差小得多，但并没有消失：在许多语言中，0.1 + 0.2 的结果是 0.30000000000000004。实数范围的具体限制不在本课程和考试的范围之内。

2.1 · 被采样的模拟数据

一种数字近似

模拟数据的值随时间平滑地变化，而不是按离散的间隔变化：音乐的音高和音量、一幅画的颜色、短跑运动员在比赛中的位置。

计算机存储的是位，所以只能近似地表示模拟数据。用数字数据来近似真实世界的模拟数据，是抽象的一个例子。

模拟数据可以通过采样很好地用数字近似：在固定的间隔测量模拟信号的值，这些测量称为样本。对每个样本进行测量，以确定存储它所需的确切位数。

图对同一条光滑信号采样了两次。第一次是 8 个样本，每个舍入到 4 个级别之一（2 位）：8 × 2 = 16 位，是一个粗糙的阶梯。然后是 16 个样本、8 个级别（3 位）：16 × 3 = 48 位，阶梯更贴近曲线（它与信号的平均距离减小了 43%）。

样本越多、每个样本的位数越多，近似就越接近，同时存储或发送所需的位也越多。再多的有限个样本也无法做到精确。

2.2 · 无损压缩

变小了，还能精确还原

数据压缩可以减小传输或存储的数据的大小（位数）。无损算法通常能减小数据大小，同时保证完整地重建原始数据。

图中的这一行有 20 个像素，每个一字节：共 20 字节（假设的）。游程编码把同一种颜色的每一段连续像素存为一个计数和一种颜色：7W 4R 6W 3B，4 段 × 2 字节 = 8 字节。

解码得到 7 white, 4 red, 6 white, 3 blue：与原来的一行完全相同，逐个像素一致。什么也没有丢失，所以位数更少不一定意味着信息更少。

大小缩减的程度取决于原始数据中的冗余量和所用的压缩算法。长的连续段压缩效果好。如果一行每个像素都交替变色（WRWRWR…），就有 20 段长度为 1 的连续段：编码后需要 40 字节，比最初的 20 字节还多。

2.2 · 有损压缩

压得更小，但只是近似

有损算法可以显著减少存储或发送的位数，但只能重建原始数据的一个近似。

图中的 16 个像素（假设的亮度，每个一字节）只保留每两个像素的平均值：8 字节，大小减半。解码时，每个像素取它所在一对的平均值：16 个中有 14 个与原来不同，最多相差 10。灰色虚影是原始数据，8 字节中的任何内容都无法把它们找回来：200、180 这一对和 190、190 这一对的平均值都是 190。

有损算法通常比无损算法能减少更多的位数。选哪一种取决于具体情况：

2.3 · 从数据中获得信息

模式，以及它们不能证明的事

信息是从数据中提取出来的事实和模式的集合。数据提供了发现趋势、建立联系和解决问题的机会。

图中画出了一个海滨小镇的 24 个假设的日子：卖出的冰淇淋与晒伤病例。一个上升，另一个也随之上升：这是很强的相关性（相关系数 r = 0.86；1 表示完美的直线）。

冰淇淋不会导致晒伤。按气温给这些日子上色，原因就显现了：这 7 个炎热的日子（红色，27 °C 或更高）既带来更多冰淇淋销量，也带来更多阳光。在数据中发现的相关性不一定表明存在因果关系；需要进一步研究才能弄清这种关系的确切性质。

在这里，仅凭销售记录是看不出来的。通常，单一来源并不包含得出结论所需的数据，必须把来自多个来源的数据（销售、诊所就诊、天气记录）合并起来。

2.3 · 元数据

关于数据的数据

元数据是关于数据的数据。照片是数据；它的元数据可能包括创建日期、文件大小、尺寸和标签。

对元数据的修改和删除不会改变原始数据。图中删除了标签“日落”；64 个像素没有一个发生变化。

元数据用于查找、组织和管理信息：照片库可以列出在 6月14日 拍摄的所有照片，或所有带“海滩”标签的照片，而无需查看任何一个像素。元数据通过提供附加信息来提高数据的使用效率，并使数据能够被结构化和组织起来。

在考试中，题目会给出收集到的数据和元数据，并问能查出什么。要问每个字段记录了什么。只有日期和标签的照片库可以回答“6 月拍了多少张照片？”，但回答不了“这张照片是在哪里拍的？”：没有任何字段记录地点。

2.3 · 清洗数据

使其统一，但不改变含义

无论规模大小，数据集都带来一些挑战：需要清洗数据、不完整的数据、无效的数据，以及需要合并数据来源。处理数据的能力取决于用户及其工具的能力。

根据数据的收集方式，它们可能并不统一。当用户在开放字段中键入内容时，缩写、拼写或大小写的方式因人而异。图中的注册表单（假设的）里，2 个城市有 7 种不同的拼写。

清洗通过把所有等价的缩写、拼写和大小写替换成同一个词，使数据统一而不改变其含义：5 个条目被改写，7 种拼写变成 2。现在，按城市统计注册人数的程序就能统计正确了。

清洗无法凭空补出缺失的内容。有一行没有年龄（不完整），有一行年龄是 −4（无效）；它们被标记出来，等待核对或排除在分析之外，而不是靠猜。

2.3 · 偏差与规模

更多的数据不等于更好的数据

偏差问题往往由所收集数据的类型或来源造成。偏差不会因为简单地收集更多数据而消除。

图中的民意调查（假设的）只能触及总体的左侧，比如说一个网站的读者。在整个总体中，41% 持红色观点。回答 30 个后，调查给出 80%；回答 60 个后，是 78%。回答数翻了一倍，错误的结果却没变，因为每个回答都来自同一个不具代表性的来源。

规模仍然重要：数据集的大小影响能从中提取的信息量。但大型数据集很难用单台计算机处理，可能需要并行系统，即许多处理器同时处理数据的各个部分。

处理数据集时，系统的可扩展性是一个重要的考虑因素，因为系统的计算能力会影响数据集如何被处理和存储。

2.4 · 过滤与转换

处理列表的程序

可以用程序处理数据来获取信息。搜索工具对高效查找信息很有用，数据过滤系统则是查找信息和识别数据模式的重要工具。

过滤只保留满足某个条件的元素，例如只保留列表中的正数，或只保留报名参加乐队的学生：

data ← [4, -2, 7, 0, -5, 3] positives ← [] FOR EACH n IN data { IF(n > 0) { APPEND(positives, n) } }

图中用红色标出正在运行的那一行。每个 n 都会被检验；只有满足 n > 0 的才会被追加。最后 positives 是 [4, 7, 3]；0 不会保留，因为 0 > 0 为 false。

转换会改变每个元素，例如把列表中的每个元素翻倍，或给每条学生记录加上家长的电子邮件。先有 doubled ← []：

FOR EACH n IN data { APPEND(doubled, 2 * n) }

最后 doubled 是 [8, −4, 14, 0, −10, 6]。把数据翻译和转换后可以产生新的见解，使用程序转换数据时，模式可能会浮现出来。程序员也用程序来过滤和清洗数据。

2.4 · 合并与可视化

由多个数得到一个数，以及一张图表

合并或比较数据，可以把许多值归结为一个答案：把一个列表中的数加起来，或找出 GPA 最高的学生。可视化则把数据集显示为图表、图形或其他视觉表示。

一个社团记录了 6 周的报名人数（假设的）：signups ← [12, 18, 9, 22, 15, 20]。

total ← 0 most ← signups[1] FOR EACH n IN signups { total ← total + n IF(n > most) { most ← n } } DISPLAY(total) DISPLAY(most)

它显示 96 22：6 周，一共 96 人报名，最好的一周有 22 人。most 从 signups[1]（第一个值）开始，而不是从 0 开始，所以即使所有的值都是负数，它也依然有效。程序运行时，图把每一周画成一根柱子：图表随着数据被读取而成形。

表格、图示、文字和其他视觉工具，可以用来传达从数据中获得的见解和知识。电子表格这类程序有助于高效地组织信息并发现其中的趋势。

程序是以迭代和交互的方式使用的：看图表，提出新的问题，再次过滤或转换。合并数据来源、对数据做聚类（把相似的项分组）和分类（把项归入不同类别），都是用程序从数据中获得见解和知识的组成部分。