CS 121: Information Retrieval — Week 4：网页爬取、文本处理

目录

• 1. 从多种格式到文本的转换
• 2. 字符编码
• 3. Unicode 与 UTF-8
• 4. 文档存储
• 5. TREC Web 格式
• 6. 压缩与 BigTable
• 7. 精确重复：校验和与 CRC
• 8. 近似重复与 N-gram 指纹
• 9. Simhash
• 10. 去除噪声：查找内容块
• 11. 文本统计与 Zipf 定律
• 12. 示例题（附解答）
• 13. 速查与必记的 5 件事

UCI CS 121 / IN4MATX 141: Information Retrieval — Prof. Alberto Krone-Martins, Fall 2026, week of Oct 21
整理自 Lecture 10、11 和 12 的幻灯片（YuJa 视频未收录）。暂定版：课堂用的 Lecture 9.5 幻灯片尚未发布，因此其中的课堂重点和提示暂缺。按概念组织，而不是按讲次组织。
幻灯片致谢 Profs. C. Lopes、A. Krone-Martins、C. Manning、P. Nayak、H. Schütze 等教授；教材插图致谢 Addison Wesley。
📖 本周阅读：Croft et al.，Search Engines: IR in Practice，第 3 章 Crawls and Feeds，以及第 4 章 Processing Text 中直到 §4.4（含）的部分

📅 课程安排：Online Quiz 1 于 10 月 21 日（周三）课上用笔记本电脑完成（晚 7:00 开放，时长 30 分钟）。
Assignment 2（网络爬虫）截止时间为 10 月 30 日（周五）晚 9:00。

1. 从多种格式到文本的转换

本周沿着一个页面从爬虫到索引的路径展开。在架构图上（L11 p3 · L12 p2、p31；在第 1 周第 10 节中有解释），路径是 文本获取 → 本地文档库 → 文本转换/处理：先把页面转换为文本（§1–3），再存储它（§4–6），然后剔除重复和噪声（§7–10），最后开始研究词本身（§11）。

"文本预处理"从转换开始（L10 p2–5，每帧一条要点）：

• 文本以数百种互不兼容的文件格式存储：纯文本、RTF、HTML、XML、Microsoft Word、ODF、PDF。
• 其他并非专门用于文本的文件类型也很重要：PowerPoint、Excel、Keynote、Pages。
• 你通常会使用转换工具或库。它会把文档内容转换为带标签的文本格式，例如 HTML 或 XML，并保留一部分重要的格式信息。
• 有些转换器不保留格式，例如 Unix 工具 pdftotxt、pdf2ps + pdf2ascii。

🔗 延伸阅读：Croft §3.5 The Conversion Problem（书中第 49 页）

2. 字符编码

字形（glyph，源自希腊语 γλυφή，意为"雕刻"）是你看到的符号，它们编码字母或含义（L10 p6–7）。字符编码是比特与字形之间的映射，也就是从文件中的比特得到屏幕上字符的方式，它可能是造成不兼容的主要原因。

• ASCII（自 1963 年起）是英语的基础编码：用 7 位表示 128 个字母、数字、特殊字符和控制字符，并额外加一位以便以字节存储。
• 其他语言的字形要多得多（L10 p8–9）：中文有 40,000 多个字符，其中常用的超过 3,000 个。
• 许多语言有多种编码方案，例如 CJK（中日韩）系列、印地语和阿拉伯语。使用这些旧方案时你必须指定编码，因为文件不是自描述的，而且一个文件中无法同时包含多种语言。
• Unicode 开发于 80 年代末，用于解决这些问题。

🔗 延伸阅读：Croft §3.5.1 Character Encodings（书中第 50 页）

3. Unicode 与 UTF-8

Unicode 是一种从数字到字形的单一映射，它尽量包含所有通用语言中的常用字形（L10 p10–11）。利用其保留的（私用）区域，甚至可以书写自创文字：幻灯片展示了一行这样的文字，旁边是一张注明来源于 Wikipedia 的图片。

Unicode 解决了"数字 → 字形"的问题，但没有唯一确定"比特 → 字形"的映射。这正是 UTF-8、UTF-16、UTF-32 编码所做的：它们把数字（码位，code point）转换为字节。

为什么要有多种编码？出于兼容性和空间的考虑（L10 p12）：

你可以两者混用：许多应用在内部使用 UTF-32（便于快速随机查找），在磁盘上使用 UTF-8（占用空间更少）。

UTF-8 的工作原理（L10 p13）。码位所在的范围决定表中的行；每个 x 依次由码位的比特填充，高位在前：

幻灯片的例子：希腊字母 π 的码位是 960，二进制为 00000011 11000000（十六进制 3C0）。960 位于第二行，因此编码形式是 110xxxxx 10xxxxxx：高 5 位放入第一个字节，接下来的 6 位放入第二个字节。结果为 11001111 10000000 = CF 80。你可以逐步演示，也可以输入其他字符：

{"title": "π 的 UTF-8 编码（L10 p13）", "text": "π", "interactive": true}

前导位决定长度（110 表示 2 个字节，1110 表示 3 个，11110 表示 4 个）；后续字节以 10 开头，因此 ASCII 字节（0xxxxxxx）永远不会是多字节字符的一部分。Python 的结果与此一致：

print("π".encode("utf-8").hex(" "))       # cf 80
print("π".encode("utf-32-be").hex(" "))   # 00 00 03 c0
print(len("中".encode("utf-8")))           # 3

📝 练习：例题 12.1

🔗 延伸阅读：Croft §3.5.1 Character Encodings（书中第 50 页）

4. 文档存储

转换之后，你需要存储文档（L11 p4–5）。保留转换后文本的理由：

• 当页面未更新时，它节省重新爬取的时间；
• 它能高效访问文本，用于摘要生成、额外信息抽取等。

数据库系统可以为某些应用提供文档存储，但网络搜索引擎使用定制的文档存储系统。

搜索引擎文档库的要求（L11 p6）：

大文件（L11 p7）：网页很小，因此把许多页面存入较少的大文件，而不是每个文档一个文件。这样可以避免文件 I/O 开销（每页的打开/关闭），并且相对于读取时间降低寻道时间——一次寻道，然后进行长时间的顺序读取。复合文档格式在一个文件中存储多个文档，例如 TREC Web。

🔗 延伸阅读：Croft §3.6 Storing the Documents（书中第 52 页） · Croft §3.6.1 Using a Database System（书中第 53 页） · Croft §3.6.2 Random Access（书中第 53 页） · Croft §3.6.4 Update（书中第 56 页）

5. TREC Web 格式

一个文件，包含两个被爬取的页面（L11 p8）：

<DOC>
<DOCNO>WTX001-B01-10</DOCNO>
<DOCHDR>
http://www.example.com/test.html 204.244.59.33 19970101013145 text/html 440
HTTP/1.0 200 OK
Date: Wed, 01 Jan 1997 01:21:13 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 270
Last-modified: Mon, 25 Nov 1996 05:31:24 GMT
</DOCHDR>
<HTML>
<TITLE>Tropical Fish Store</TITLE>
Coming soon!
</HTML>
</DOC>
<DOC>
<DOCNO>WTX001-B01-109</DOCNO>
<DOCHDR>
http://www.example.com/fish.html 204.244.59.33 19970101013149 text/html 440
HTTP/1.0 200 OK
Date: Wed, 01 Jan 1997 01:21:19 GMT
Server: Apache/1.0.3
Content-type: text/html
Content-length: 270
Last-modified: Mon, 25 Nov 1996 05:31:24 GMT
</DOCHDR>
<HTML>
<TITLE>Fish Information</TITLE>
This page will soon contain interesting
information about tropical fish.
</HTML>
</DOC>

接下来的五张幻灯片逐一拆解其中的一部分（L11 p9–13）：

💡 关键见解：这就是"大文件"思想的实际应用：爬虫把 <DOC> 块追加到一个大文件中，而一个从 DOCNO（或 URL 哈希）到字节偏移量的小索引提供了随机访问。

6. 压缩与 BigTable

6.1 压缩

文本高度冗余（或可预测）（L11 p14–15；幻灯片展示了 Shannon 1951 年论文 "Prediction and Entropy of Printed English" 的搜索结果）。无损压缩利用这种冗余，在不丢失任何内容的前提下使文件变小；索引也可以压缩。

• 常见算法可将 HTML 和 XML 文本压缩 80%：例如 DEFLATE（zip、gzip）和 LZW（Unix compress、PDF）。
• 大文件可以分块压缩，这样读取一个文档时无需解压整个文件。

6.2 BigTable

BigTable 是 Google 的文档存储系统（L11 p16），专门用于在廉价计算机上存储、查找和更新网页并处理大型集合。图中显示一个逻辑表被切分为许多子表（tablet），每个子表由一台服务器持有。

组织方式（L11 p18–19）：

• 在逻辑上按行组织；一行存储单个网页的数据。
• 列可以有多个时间戳（版本）。行键、列键和时间戳共同指向一个单元格。
• 一行可以有极多的列：所有行具有相同的列组，但并非所有行都有相同的列——这对减少磁盘读取很重要。
• 行按行键划分为子表（例如以某个字母开头的 URL 位于同一子表中），这使得找到正确的服务器变得简单。

幻灯片中 www.example.com 的行：

anchor: 是一个列组；每个链接来源站点都有自己的一列，保存其锚文本——即 §4 中的"添加新锚文本"更新。

优缺点（L11 p17）：

• 没有查询语言：不需要优化复杂查询。
• 只支持行级事务。
• 子表存放在一个可供所有 BigTable 服务器访问的复制文件系统中。
• 对子表的任何更改都会记录在事务日志中，该日志同样位于共享文件系统上。
• 如果子表服务器崩溃，另一台服务器会从文件系统读取子表数据和日志并接管。
• 子表可以被压缩。

🔗 延伸阅读：Croft §3.6.3 Compression and Large Files（书中第 54 页） · Croft §3.6.5 BigTable（书中第 57 页）

7. 精确重复：校验和与 CRC

第 3 周提出了这个问题（约 30% 的页面是重复的；精确副本用哈希，近似副本用指纹——第 3 周第 7 节）。L11–L12 给出了算法。

重复与近似重复来自副本、版本、抄袭、垃圾信息和镜像站点；在大型爬取中，30% 的页面与其他页面完全相同或近似相同（Fetterly et al., 2003）（L11 p21）。它们在爬取、索引和搜索过程中消耗大量资源，而对大多数用户来说几乎没有价值（但在某些用例中可能有价值；幻灯片上的 "buy" 是 "but" 的笔误）。

精确重复检测相对容易（L11 p22–24）。校验和是由文档内容计算出的一个值，例如文件中所有字节的和：

所有数值均为十六进制：508（十六进制）= 1,288（十进制）。

• 文本不同的文件可能具有相同的校验和——字节求和忽略顺序，因此同一组字节的任何重新排列都会产生碰撞。
• 循环冗余校验（CRC）还会考虑字节的位置。它仍然可能发生碰撞，但非常罕见。其他函数包括 BLAKE2/3、MD5、SHA1、SHA2 等。
• 无论使用哪种方法，都需要足够快——因为它要对每个页面运行。

import zlib

for s in [b"Tropical fish", b"Tropical fihs"]:
    print(s, sum(s), hex(sum(s)), hex(zlib.crc32(s)))
# b'Tropical fish' 1288 0x508 0x18f14f94
# b'Tropical fihs' 1288 0x508 0x3ba24de2

交换两个字母会保持字节和不变，但会改变 CRC。

📝 练习：例题 12.2

🔗 延伸阅读：Croft §3.7 Detecting Duplicates（书中第 60 页）

8. 近似重复与 N-gram 指纹

近似重复检测更难（L11 p25–27）。两个文本相同但广告或格式不同的页面是近似重复吗？近似重复由两个文档之间某种相似度度量的阈值来定义——例如，若 D1 与 D2 超过 90% 的词相同，则 D1 是 D2 的近似重复。"你能看出如何在这里用到作业 1 吗？"——作业 1 的分词和词频统计，恰恰是词重叠度量所需要的。

两种场景（L11 p28–29）：

普通的信息检索技术适用于搜索；对于发现任务，则需要称为指纹（fingerprint）的紧凑表示。

指纹算法（L11 p30；框出的部分）：

1. 把文档解析为词；去除标点、HTML 标签和多余的空白。
2. 将词分组为连续的 n-gram（某个 n 值）——通常是重叠的。
3. 选出部分 n-gram 来代表文档。
4. 对选中的 n-gram 取哈希——检索更快，表示更小。
5. 存储哈希值，通常存放在倒排索引中。
6. 通过指纹的重叠程度比较文档。

幻灯片的例子（L11 p31–34），每帧展示一个阶段：

• (a) 文本："Tropical fish include fish found in tropical environments around the world, including both freshwater and salt water species."
• (b) 3-gram：tropical fish include、fish include fish、include fish found、……、salt water species——18 个词得到 16 个 3-gram。
• (c) 哈希值：938 664 463 822 492 798 78 969 143 236 913 908 694 553 870 779。
• (d) 使用 0 mod 4 选出：664 492 236 908。

（示例先对每个 n-gram 取哈希，再进行选择；这与列表中先选择（第 3 步）后哈希（第 4 步）的思路相同。）逐步查看这 16 个 n-gram；也可以编辑文本，使用演示用的哈希：

{"title": "热带鱼文本的 N-gram 指纹（L11 p30–34）", "interactive": true}

比较两个指纹（L11 p35–38）。给定指纹 $F_A$ 和 $F_B$，相似度是交集大小与并集大小之比：

$|F|$ 是集合中哈希值的个数（幻灯片写作 card），$\tau$ 是你自己选择的阈值：在你所定义的阈值下，它们即为近似重复。

⚠️ 易错点："0 mod p" 的选择只保留大约 $1/p$ 的 n-gram，而且选中哪些只取决于它们的哈希值，因此同一文本的两个副本会选中相同的 n-gram。若按位置选择（"每隔 4 个 n-gram 取一个"），则不然：在开头插入一个词，所有被选中的 n-gram 都会改变。

📝 练习：例题 12.3

🔗 延伸阅读：Croft §3.7 Detecting Duplicates（书中第 60 页）

9. Simhash

基于词的表示上的相似度比较，比 n-gram 指纹更有效地找到近似重复；它的问题在于效率（L12 p4–6）。Simhash（Charikar, 2002）结合了基于词的相似度的优点与哈希指纹的效率：两个页面之间的余弦相关性与它们 simhash 指纹中相同比特的数量成正比。

算法（L12 p7–10，在 p16 再次框出）：

1. 把文档处理为一组带权重的特征——这里是按词频加权的词。
2. 为每个词生成一个 b 位哈希（b 为指纹大小）；每个词的哈希唯一。
3. 在 b 维向量 $V$ 中，对每个词，如果其哈希的第 $i$ 位为 1，就把它的权重加到分量 $i$ 上；如果该位为 0，则减去它的权重。
4. 处理完所有词后，指纹的第 $i$ 位在 $V_i$ 为正时为 1，否则为 0。

幻灯片的例子（L12 p11–15），文本与第 8 节相同：

• (b) 带权重的词：tropical 2、fish 2、include 1、found 1、environments 1、around 1、world 1、including 1、both 1、freshwater 1、salt 1、water 1、species 1（in、the、and 被略去）。
• (c) 8 位哈希值：

• (d) $V$ = 1 −5 9 −9 3 1 3 3。
• (e) 指纹 = 1 0 1 0 1 1 1 1。

L12 p14 检查了最后一个分量：tropical 01100001 → - + + - - - - +，fish → + - + - + - + +，include → + + + - - + + -，并沿最后一列向下：$3 = 2 + 2 - 1 - 1 + 1 + 1 - 1 - 1 - 1 + 1 + 1 + 1 - 1$。演示每一步加入一个词：

{"title": "热带鱼文本的 Simhash（L12 p7–16）", "interactive": true}

比较两个 simhash（L12 p17–18）：相似度是相同比特所占的比例：

$H_A, H_B$ 是两个指纹，$\equiv_{\text{bitwise}}$ 在两者比特一致的每个位置计为 1，$n$ 是比特数——等价于 $1 - \text{Hamming distance}/n$。

⚠️ 易错点：Simhash 与普通哈希恰恰相反。好的哈希在一个字节改变时会完全改变（§7）；simhash 的设计目标是让相似的文档得到的指纹只在少数比特上不同——只改一个词，只会使 $V$ 改变该词的权重那么多。

📝 练习：例题 12.4

🔗 延伸阅读：Croft §3.7 Detecting Duplicates（书中第 60 页）

10. 去除噪声：查找内容块

许多网页包含与主要内容无关的文本、链接和图片（L12 p20）。这些材料大多是噪声，可能会损害页面的排名。一些技术用于检测内容块；在建索引时，非内容材料会被忽略或降低重要性。

噪声示例（L12 p21–22）：一个新闻页面，其横幅和侧栏被框为噪声块；以及 CNN.com 的 "Science & Space" 文章（"Aquarium plays whale shark matchmaker"），其正文被框为内容块，周围是导航、搜索框和广告。"那么，如何检测出内容？"

技术一：标签的累积分布——文档斜率曲线（Finn, Kushmerick & Smyth, 2001），在第 3 周第 7 节中介绍过（L12 p23–24）。沿页面的 token 逐个遍历，统计到目前为止看到的标签数：token 数（0–3,500）在 x 轴，标签数（0–1,000）在 y 轴。曲线在标签密集的导航区域稳步上升，而正文是中间的"平台"（标记为 "Text area"，约 1,000–1,500 个 token），在那里很多 token 经过时几乎没有标签。

作为优化问题（L12 p25–27）：把页面表示为一个比特序列，若第 $n$ 个 token 是标签则 $b_n = 1$。寻找 $i$ 和 $j$，使得 $i$ 之前和 $j$ 之后的标签数，加上 $i$ 与 $j$ 之间的非标签 token 数，最大：

$N$ 是 token 的数量；token $i$ … $j$ 构成内容块。第一项和第三项奖励块外部的标签，中间一项奖励块内部的文本。

替代方法（L12 p28）：把曲线切分为纵向片段，求每个片段内的斜率，并迭代，不断缩小片段大小，直到找到零斜率窗口。

其他方法（L12 p29）利用文档对象模型（DOM）结构和视觉（布局）特征：HTML 解析器把 HTML 转换为 DOM 树。幻灯片中的 CNN 树：#document → HTML → HEAD、BODY（contentArea），其中 DIV 和 TABLE 名为 cnnCeil、cnnBreakingNewsBanner、iframecnnBreakingNewsBanner、cnnCeilSearch、cnnArticleWireFrame、cnnFootBox、csiIframe——并且高亮显示了 TABLE → TBODY → TR → TD cnnArticleContent，即文章本身。

🔗 延伸阅读：Croft §3.8 Removing Noise（书中第 63 页）

11. 文本统计与 Zipf 定律

处理文本是把文档转换为索引词项的关键步骤（L12 p32）。为什么不直接索引原始字符串？

• 对网络搜索来说，精确匹配用户输入的字符串限制太多，效果不好（例如，区分大小写的搜索可能是也可能不是你想要的）。
• 搜索中并非所有词的价值都相同。
• 有时词从哪里开始、到哪里结束都不清楚——在中文和韩文等语言中，甚至不清楚什么是"词"。

（分词、停用词去除和词干提取属于第 5 周的内容。）

文本统计（L12 p33–34）：文本使用的词种类繁多，但词出现的许多统计特征是可以预测的，例如词频的分布。检索模型和排序算法高度依赖这些特征：对检索重要的词，通常在某个文档中出现频繁，但在整个语料库中并不常见。

Zipf 定律（L12 p35–36）。词频分布高度偏斜：少数词出现非常频繁，许多词几乎从不出现。最常见的两个词（"the"、"of"）约占所有词出现次数的 10%。Zipf 的"定律"是：第 $r$ 个最常见词的频率与 $r$ 成反比——秩与频率的乘积大致为常数：

$r$ 是秩（词按频率从高到低排序），$f$ 是词的频率，$P_r$ 是其出现概率（频率 / 词出现总数），$k$、$c$ 为常数。L12 p37 绘制了英语的 $P_r$（0–0.1）与秩（0–100）的关系：曲线起点接近 0.1，在前约 10 个秩内急剧下降，然后趋于 0——即 $0.1/r$ 的形状。

AP89（Associated Press 1989 年新闻）统计（L12 p38）：

AP89 最常见的词（$P_r$ 单位为 %）：

变化最大的是频率最高的词——但如果继续往下看：前 10 名中 $r \cdot P_r$ 在 0.056 到 0.140 之间摆动，然后从第 11 名到第 50 名稳定在 0.081 到 0.096 之间，接近 Zipf 的 $c \approx 0.1$。

AP89 的 Zipf 定律（L12 p39）是一张对数-对数图：纵轴为概率（$10^{-8}$ 到 1），横轴为秩（1 到 $10^6$），图中有 Zipf 直线 $P_r = 0.1/r$（斜率为 −1 的直线）以及 AP89 的数据点。数据点在中间的秩段贴近该直线，在最靠前的几个秩处低于直线，而对超过约 10,000 的秩则向下偏离，最后形成罕见词的阶梯状平台。注意高频和低频处的问题。只出现一次的词称为 hapax legomena（希腊语 ἅπαξ λεγόμενον，意为"只说过一次"）——AP89 的 198,763 个词中有 70,064 个，约占 35%。

⚠️ 易错点：幻灯片的 $P_r$ 列并不使用左侧表格中的 39,749,179 总数；用它相除会得到 "the" = 6.09%，而不是 6.49%。该列与约 3730 万次出现的总数一致，因此其中每个 $P_r$ 和 $r \cdot P_r$ 都比左表隐含的值高约 6%。Zipf 的结论并不改变。→ 例题 12.5

🔗 延伸阅读：Croft §4.1 From Words to Terms（书中第 73 页） · Croft §4.2 Text Statistics（书中第 75 页） · Croft §4.2.1 Vocabulary Growth（书中第 80 页） · Croft §4.2.2 Estimating Collection and Result Set Sizes（书中第 83 页）

12. 示例题（附解答）

12.1 π 的 UTF-8 编码（L10 p13）

π 是 Unicode 码位 960。UTF-8 会存储哪些字节？UTF-32 需要多少字节？

✍️ 先自己试一试。

解答。 960 = 0x3C0 = 00000011 11000000。它位于 128–2047 范围内，因此模板是 110xxxxx 10xxxxxx，有 5 + 6 = 11 个有效载荷位：960 用 11 位表示为 01111000000。高 5 位 01111 → 110+01111 = 11001111；接下来 6 位 000000 → 10+000000 = 10000000。结果为 CF 80，共 2 个字节。UTF-32 始终使用 4 个字节：00 00 03 C0。返回第 3 节。

12.2 字节和校验和（L11 p24）

对 "Tropical fish" 的字节求和。字节和是检测精确重复的安全方法吗？

✍️ 先自己试一试。

解答。 以十六进制计算：54 + 72 + 6F + 70 + 69 + 63 + 61 + 6C + 20 + 66 + 69 + 73 + 68 = 508（十六进制）= 1,288。这并不安全：求和忽略顺序，因此 "Tropical fihs" 的和也是 1,288。CRC 会按位置对字节加权：CRC-32 得到 0x18f14f94 与 0x3ba24de2。返回第 7 节。

12.3 热带鱼的指纹（L11 p31–34）

用幻灯片中的 3-gram 和哈希值，"0 mod 4" 会选出哪些值？

✍️ 先自己试一试。

解答。 18 个词 → 18 − 3 + 1 = 16 个 3-gram。对 4 取余：

$F$ = {664, 492, 236, 908}：16 个值中的 4 个，分别来自 "fish include fish"、"found in tropical"、"the world including" 和 "including both freshwater"。与另一文档的指纹比较时，使用 $|F_A \cap F_B| / |F_A \cup F_B| \ge \tau$。返回第 8 节。

12.4 热带鱼文本的 Simhash（L12 p11–15）

使用幻灯片的权重和 8 位哈希，计算 $V$ 和指纹。

✍️ 先自己试一试。

解答。 每个词对 1 位加上 +权重，对 0 位加上 −权重。按列计算：

第 8 位，如 L12 p14 所示：tropical +2，fish +2，include −1，found −1，environments +1，around +1，world −1，including −1，both −1，freshwater +1，salt +1，water +1，species −1 → 3 > 0 → 1。指纹为 10101111，与幻灯片一致。两个文档的 simhash $H_A, H_B$ 通过 8 位中相同比特的比例与 $\tau$ 比较。返回第 9 节。

12.5 在 AP89 上检验 Zipf 定律（L12 p35–39）

根据 AP89 的表格：“the” 和 “of” 占文本的多少？$r \cdot P_r$ 是否保持在 0.1 附近？hapax legomena 占词表的比例是多少？

✍️ 先自己试一试。

解答。

• "the" + "of"：幻灯片上的 $P_r$ 为 6.49% + 2.80% = 9.29%——即 "about 10%"。根据频次和 39,749,179 的总数，则为 3,466,511 / 39,749,179 = 8.7%。
• $r \cdot P_r$：秩 1 得 0.065，秩 2 为 0.056，秩 6 为 0.140（最大的波动）；秩 11–50 保持在 0.081–0.096。用幻灯片上四舍五入的 $P_r$ 重新计算 $r \times P_r$，"and" 得 0.116（幻灯片为 0.120），"in" 得 0.136（幻灯片为 0.140）——这是舍入造成的。
• 用左表的总数，$r \cdot P_r$ 会更低，例如 "the" 为 2,420,778 / 39,749,179 = 0.061，"people" 为 50 × 68,988 / 39,749,179 = 0.087；幻灯片的那一列隐含的总数约为 3730 万（见第 11 节中的易错点）。
• hapax legomena：70,064 / 198,763 = 35% 的词表只出现一次；只有 4,169 个词（2.1%）出现超过 1,000 次。

Zipf 在中间段大致成立，在两端失效——即 L12 p39 所示的高频和低频问题。返回第 11 节。

13. 速查与必记的 5 件事

必记的 5 件事

1. Unicode 把字形映射为数字；UTF-8/16/32 把数字映射为字节。π = U+03C0 = 960 → 11001111 10000000 = CF 80。
2. 搜索引擎把文档存储在大型复合文件（TREC Web）或 BigTable 中——通过 URL 哈希实现随机访问、压缩和更新，而不是每个页面一个文件。
3. 精确重复：校验和/CRC；近似重复：n-gram 指纹（"0 mod p" 选择，交集除以并集 ≥ τ），或 simhash（相同比特的比例 ≥ τ）。
4. Simhash：$V_i$ 在比特 $i$ 为 1 时加上权重，为 0 时减去权重；当 $V_i > 0$ 时比特为 1——相似的文档得到相似的指纹。
5. Zipf：秩 × 概率 ≈ 0.1；少数词占主导，AP89 词表中约 35% 的词只出现一次；该定律在两端都会偏离。