拼写检查器

要解决的问题

对于这个问题，你将实现一个程序，使用哈希表对文件进行拼写检查，如下所示。

演示

分发代码

对于这个问题，你将扩展 CS50 工作人员提供给你的代码功能。

$

wget https://cdn.cs50.net/2026/x/psets/5/speller.zip

unzip speller.zip

rm speller.zip

cd speller

speller/ $

dictionaries/  dictionary.c  dictionary.h  keys/  Makefile  speller.c  speller50  texts/

背景

从理论上讲，对于大小为 n 的输入，运行时间为 n 的算法在 O 的意义上与运行时间为 2n 的算法是”渐进等价的”。事实上，在描述算法的运行时间时，我们通常关注主导项（即影响最大的项）（在这种情况下是 n，因为 n 可能远大于 2）。但在现实世界中，实际情况是 2n 的速度感觉是 n 的两倍慢。

你面临的挑战是实现你能做到的最快的拼写检查器！不过，我们说的”最快”是指实际的”墙上时钟”时间，而不是渐进时间。

在 speller.c 中，我们组合了一个程序，该程序的设计目的是在从磁盘将单词字典加载到内存中后对文件进行拼写检查。同时，该字典在名为 dictionary.c 的文件中实现。（它也可以直接在 speller.c 中实现，但随着程序变得越来越复杂，将其拆分为多个文件通常更方便。）同时，其中函数的原型不是定义在 dictionary.c 本身中，而是定义在 dictionary.h 中。这样，speller.c 和 dictionary.c 都可以 #include 该文件。不幸的是，我们还没来得及实现加载部分。或者检查部分。这两者（还有更多）都留给你了！但首先，让我们浏览一遍。

理解

dictionary.h

打开 dictionary.h，你会看到一些新的语法，包括几行提到 DICTIONARY_H 的内容。这些不用担心，但如果好奇的话，这些行只是确保即使 dictionary.c 和 speller.c（你稍后会看到）都 #include 此文件，clang 也只会编译它一次。

接下来注意我们如何 #include 一个名为 stdbool.h 的文件。这就是 bool 本身被定义的文件。你以前不需要它，因为 CS50 库曾经为你 #include 了它。

还要注意我们使用了 #define，这是一个”预处理指令”，定义了一个名为 LENGTH 的”常量”，其值为 45。它是一个常量，意味着你不能（意外地）在你自己的代码中更改它。实际上，clang 会把你代码中所有提到 LENGTH 的地方都替换为字面上的 45。换句话说，它不是变量，只是一个查找替换的技巧。

最后，注意五个函数的原型：check、hash、load、size 和 unload。注意其中三个函数通过 * 接受一个指针作为参数：

bool check(const char *word);
unsigned int hash(const char *word);
bool load(const char *dictionary);

回想一下，char * 就是我们之前称之为 string 的东西。所以这三个原型本质上就是：

bool check(const string word);
unsigned int hash(const string word);
bool load(const string dictionary);

而 const 则表示这些字符串作为参数传入时必须保持不变；你不能意外地或以其他方式更改它们！

dictionary.c

现在打开 dictionary.c。注意在文件顶部，我们定义了一个名为 node 的 struct，它表示哈希表中的一个节点。我们还声明了一个全局指针数组 table，它将（很快）表示你将用来跟踪字典中单词的哈希表。该数组包含 N 个节点指针，我们目前将 N 设置为 26，以匹配下面描述的默认 hash 函数。你可能会想根据你自己的 hash 实现来增大这个值。

接下来，注意我们已经实现了 load、check、size 和 unload，但只是勉强实现，仅够编译通过。还要注意我们已经用基于单词首字母的示例算法实现了 hash。你的工作最终是尽可能巧妙地重新实现这些函数，使这个拼写检查器按预期工作。而且要快！

speller.c

好的，接下来打开 speller.c，花一些时间浏览其中的代码和注释。你不需要更改此文件中的任何内容，也不需要完全理解它，但一定要尝试了解它的功能。注意，通过一个名为 getrusage 的函数，我们将对 check、load、size 和 unload 的实现进行”基准测试”（即计时执行）。还要注意我们是如何逐个单词地将某个文件的目录传递给 check 进行拼写检查的。最终，我们会报告该文件中的每个拼写错误以及一系列统计信息。

顺便注意，我们已将 speller 的用法定义为

Usage: speller [dictionary] text

其中 dictionary 假定为一个包含小写单词列表的文件，每行一个，而 text 是要进行拼写检查的文件。如方括号所示，提供 dictionary 是可选的；如果省略此参数，speller 将默认使用 dictionaries/large。换句话说，运行

./speller text

将等同于运行

./speller dictionaries/large text

其中 text 是你想要进行拼写检查的文件。可以说，前者更容易输入！（当然，在你实现 dictionary.c 中的 load 之前，speller 将无法加载任何字典！在那之前，你会看到 Could not load。）

请注意，默认字典中有 143,091 个单词，所有这些单词都必须加载到内存中！实际上，看一下那个文件以了解其结构和大小。注意该文件中的每个单词都以小写形式出现（为简单起见，即使专有名词和首字母缩写词也是如此）。从上到下，文件按字典序排序，每行只有一个单词（每个单词以 \n 结尾）。没有单词超过 45 个字符，也没有单词出现超过一次。在开发过程中，你可能会发现向 speller 提供一个包含少得多的单词的自己的 dictionary 会很有帮助，以免你难以调试内存中巨大的结构。dictionaries/small 就是这样一个字典。要使用它，请执行

./speller dictionaries/small text

其中 text 是你想要进行拼写检查的文件。在确定你理解了 speller 本身如何工作之前，不要继续往下看！

很可能你没有花足够的时间浏览 speller.c。退回去再仔细过一遍！

texts/

为了让你能够测试你的 speller 实现，我们还为你提供了大量文本，其中包括 La La Land 的剧本、平价医保法案的文本、托尔斯泰的三百万字节、联邦党人文集和莎士比亚的一些摘录，以及更多。为了让你知道应该期待什么，打开并浏览每个文件，所有这些文件都位于你 pset5 目录下的 texts 目录中。

现在，正如你仔细阅读 speller.c 后应该知道的那样，如果使用例如以下命令执行 speller

./speller texts/lalaland.txt

，其输出最终将类似于以下内容。

以下是你将看到的部分输出。为了提供信息，我们摘录了一些示例”拼写错误”。为了避免破坏乐趣，我们暂时省略了我们自己的统计数据。

MISSPELLED WORDS

[...]
AHHHHHHHHHHHHHHHHHHHHHHHHHHHT
[...]
Shangri
[...]
fianc
[...]
Sebastian's
[...]

WORDS MISSPELLED:
WORDS IN DICTIONARY:
WORDS IN TEXT:
TIME IN load:
TIME IN check:
TIME IN size:
TIME IN unload:
TIME IN TOTAL:

TIME IN load 表示 speller 执行你的 load 实现所花费的秒数。TIME IN check 表示 speller 执行你的 check 实现所花费的总秒数。TIME IN size 表示 speller 执行你的 size 实现所花费的秒数。TIME IN unload 表示 speller 执行你的 unload 实现所花费的秒数。TIME IN TOTAL 是这四个测量值的总和。

请注意，这些时间在不同的 speller 执行中可能会有些变化，这取决于你的 codespace 还在做什么，即使你没有更改代码。

顺便说明一下，”拼写错误”的意思仅仅是某个单词不在所提供的 dictionary 中。

Makefile

最后，回想一下 make 会自动编译你的代码，这样你就不用手动执行 clang 以及一大堆开关。然而，随着你的程序规模增大，make 将无法再从上下文中推断如何编译你的代码；你需要开始告诉 make 如何编译你的程序，特别是当涉及多个源文件（即 .c 文件）时，就像这个问题的情况一样。因此我们将利用一个 Makefile，这是一个告诉 make 具体做什么的配置文件。打开 Makefile，你应该看到四行：

1. 第一行告诉 make 在你执行 make speller（或仅 make）时执行后续行。
2. 第二行告诉 make 如何将 speller.c 编译成机器代码（即 speller.o）。
3. 第三行告诉 make 如何将 dictionary.c 编译成机器代码（即 dictionary.o）。
4. 第四行告诉 make 将 speller.o 和 dictionary.o 链接为名为 speller 的文件。

请务必通过执行 make speller（或仅 make）来编译 speller。执行 make dictionary 是行不通的！

规格说明

好的，现在你面前的挑战是使用哈希表尽可能高效地依次实现 load、hash、size、check 和 unload，使 TIME IN load、TIME IN check、TIME IN size 和 TIME IN unload 都被最小化。当然，"最小化"到底意味着什么并不明显，因为这些基准测试会随着你向 speller 提供不同的 dictionary 和 text 值而必然变化。但这正是这个问题的挑战所在，也许是乐趣所在。这个问题是你设计的机会。虽然我们鼓励你最小化空间，但你最终的敌人是时间。但在你开始之前，我们有一些规范说明。

• 你不能修改 speller.c 或 Makefile。
• 你可以修改 dictionary.c（实际上，为了完成 load、hash、size、check 和 unload 的实现，你必须这样做），但你不能修改 load、hash、size、check 或 unload 的声明（即原型）。不过，你可以向 dictionary.c 添加新的函数和（局部或全局）变量。
• 你可以更改 dictionary.c 中 N 的值，以便你的哈希表拥有更多的存储桶。
• 你可以修改 dictionary.h，但不能修改 load、hash、size、check 或 unload 的声明。
• 你的 check 实现必须不区分大小写。换句话说，如果 foo 在字典中，那么对于它的任何大小写形式，check 都应该返回 true；foo、foO、fOo、fOO、Foo、FoO、FOo 和 FOO 都不应被视为拼写错误。
• 除了大小写，你的 check 实现应该只对确实在 dictionary 中的单词返回 true。注意不要硬编码常见单词（例如 the），以免我们给你的实现传入一个不含这些单词的 dictionary。此外，唯一允许的所有格形式是那些确实在 dictionary 中的。换句话说，即使 foo 在 dictionary 中，如果 foo's 不在 dictionary 中，check 也应该对 foo's 返回 false。
• 你可以假设任何传递给程序的 dictionary 都和我们的一样，从上到下按字母顺序排列，每行一个单词，每个单词以 \n 结尾。你还可以假设 dictionary 将包含至少一个单词，没有单词超过 LENGTH（在 dictionary.h 中定义的常量）个字符，没有单词出现超过一次，每个单词只包含小写字母字符和可能的撇号，并且没有单词以撇号开头。
• 你可以假设 check 只会被传入包含（大写或小写）字母字符和可能撇号的单词。
• 你的拼写检查器只能接受 text 和可选的 dictionary 作为输入。尽管你可能有倾向（特别是如果你属于比较有挑战精神的那类人）为了推导出一个”理想哈希函数”而”预处理”我们的默认字典，但你不能将任何此类预处理的输出保存到磁盘上，以便在后续运行拼写检查器时将其加载回内存中从而获得优势。
• 你的拼写检查器不得泄漏任何内存。请务必使用 valgrind 检查泄漏。
• 你编写的哈希函数最终应该是你自己原创的，而不是从网上搜索来的。

好的，准备好了吗？

• 实现 load。
• 实现 hash。
• 实现 size。
• 实现 check。
• 实现 unload。

提示

bool load(const char *dictionary)
{
    // Open the dictionary file

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
}

bool load(const char *dictionary)
{
    // Open the dictionary file
    FILE *source = fopen(dictionary, "r");

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
}

bool load(const char *dictionary)
{
    // Open the dictionary file
    FILE *source = fopen(dictionary, "r");

    // Read each word in the file

        // Add each word to the hash table

    // Close the dictionary file
    fclose(source);
}

valgrind ./speller texts/cat.txt

help50 valgrind ./speller texts/cat.txt

讲解视频

如何测试

如何检查你的程序是否输出了正确的拼写错误单词？你可以参考位于 speller 目录内的 keys 目录中的”答案密钥”。例如，keys/lalaland.txt 中包含了你程序应该认为是拼写错误的所有单词。

因此，你可以在一个窗口中用某个文本运行你的程序，如下所示。

./speller texts/lalaland.txt

然后你可以在另一个窗口中用相同的文本运行工作人员的解答，如下所示。

./speller50 texts/lalaland.txt

然后你可以并排目视比较这两个窗口。不过，这很快就变得繁琐。因此，你可能想要将程序的输出”重定向”到一个文件，如下所示。

./speller texts/lalaland.txt > student.txt
./speller50 texts/lalaland.txt > 工作人员.txt

然后你可以使用像 diff 这样的程序在同一窗口中并排比较两个文件，如下所示。

diff -y student.txt 工作人员.txt

或者，为了节省时间，你可以直接将程序的输出（假设你已将其重定向到例如 student.txt）与某个答案密钥进行比较，而无需运行工作人员的解答，如下所示。

diff -y student.txt keys/lalaland.txt

如果你的程序输出与工作人员的匹配，diff 将输出两列，除了底部的运行时间外，其他内容应该完全相同。但如果两列不同，你会在它们不同的地方看到一个 > 或 |。例如，如果你看到

MISSPELLED WORDS                                                MISSPELLED WORDS

TECHNO                                                          TECHNO
L                                                               L
                                                              > Thelonious
Prius                                                           Prius
                                                              > MIA
L                                                               L

这意味着你的程序（其输出在左边）不认为 Thelonious 或 MIA 是拼写错误的，而工作人员的输出（在右边）则认为它们拼写错误，这从左侧列中没有 Thelonious 而右侧列中存在 Thelonious 可以看出。

最后，请务必使用默认的大字典和小字典进行测试。注意不要假设你的解答在大字典上运行成功就意味着在小字典上也运行成功。以下是尝试小字典的方法：

./speller dictionaries/small texts/cat.txt 

正确性

check50 cs50/problems/2026/x/speller

代码风格

style50 dictionary.c

工作人员的解答

如何评估你的代码有多快（以及多正确）？一如既往，你可以随意试用工作人员的解答，如下所示，并将它的数字与你的进行比较。

./speller50 texts/lalaland.txt

如何提交

在终端中执行以下命令提交你的作业，并按提示完成操作。

submit50 cs50/problems/2026/x/speller