如何在64kB RAM中容纳250kB字典并仍然进行快速查找？作为参考，即使使用现代压缩技术，如gzip -9，您也无法将此文件压缩到85kB以下。在1970年代，道格拉斯·麦基尔罗伊在AT&T为Unix实现拼写检查器时面临了这个确切的挑战。PDP-11计算机的限制意味着整个字典需要适应仅64kB的RAM。这似乎是一个不可能的任务。麦基尔罗伊没有依赖于通用的压缩技术，而是利用数据的特性开发了一种压缩算法，使其与理论上可能的压缩极限仅差0.03位。至今，这一成果仍然无人打破。Unix拼写的故事不仅仅是历史上的好奇，它是一堂在约束条件下的工程大师课：如何从基本原则分析问题，利用数学见解，设计在严格资源限制下有效的优雅解决方案。如果您时间有限，这里有一个关键的工程故事：Unix拼写最初是由史蒂夫·约翰逊在1970年代下午的原型，之后道格拉斯·麦基尔罗伊进行了重写，以提高其性能和准确性。麦基尔罗伊的第一个创新是一种聪明的基于语言学的词干提取算法，将字典减少到仅2.5万单词，同时提高了准确性。为了实现快速查找，他最初使用了布隆过滤器 — 也许是其首次投入生产的使用。有趣的是，丹尼斯·里奇负责了实施。他们调优使其具有如此低的误报率，以至于可以跳过实际的字典查找。当字典增长到3万单词时，布隆过滤器的方法变得不切实际，导致创新的哈希压缩技术。他们计算出27位哈希码将保持合适的碰撞概率，但需要压缩。麦基尔罗伊的解决方案是在发现这些差异遵循几何分布后，存储排序哈希码之间的差异。通过使用高伦布编码，一种为几何分布设计的压缩方案，他达到了每个单词13.60位的压缩效果 — 显著接近理论最小值13.57位。最后，他对压缩数据进行了分区，以加快查找速度，权衡了小幅内存增加（最终大小约14位每个单词）以换取显著更快的性能。文章的其余部分扩展了每一个观点，并详细解释了背后的所有数学和逻辑。为了为Unix争取资金，肯·汤普逊和丹尼斯·里奇向AT&T推销Unix作为一个用于专利部门的文本处理系统。自然地，文本处理系统也需要一个拼写检查器。Unix拼写的第一个版本是史蒂夫·约翰逊在1975年编写的原型。乔恩·本特利提到史蒂夫在一个下午写的，尽管它能够工作，但准确性并不高，而且实现相当简单。它会将输入文件拆分成一个单词流，进行一些简单的预处理，例如删除数字和特殊字符，将字母转换为小写，然后排序、去重，最后将列表传递给拼写程序，该程序仅检查这些单词是否存在于磁盘上的字典中。由于它的简单实现，它的准确性不高，同时由于在磁盘上的字典查找也很慢。在看到初版被采用后，道格拉斯·麦基尔罗伊接手这个项目，目标是改善工具的准确性和性能。他在两个独立的前线进行了一些非常聪明的工程工作：构建一个用于将单词减少到其词干的词缀去除算法，以及一个由词干词组成的紧凑字典。本文将重点介绍数据结构设计部分，但让我们花一点时间了解词缀去除算法以了解它是如何工作的。使用全功能字典进行查找是缓慢的，因为当时计算机的主内存仅有几千字节，而使用基于磁盘的查找就更慢。道格拉斯·麦基尔罗伊提出了一种算法的想法，该算法将迭代地从单词中删除常见的前缀和后缀，并查找字典检查减少后的单词是否存在。如果经过词缀去除后，字典中仍然没有该单词，就会将其标记为拼写错误。例如，该算法会将单词“misrepresented”减少为“present”，通过删除前缀“mis”、“re”，和后缀“ed”。由于“present”是字典中的有效单词，因此不会将其标记为拼写错误。这种词缀去除技术并不是100%准确，有时会让拼写错误的单词通过。但是，在当时这样的情况被认为是可以接受的。