Unix 拼写检查器：如何在 64kB RAM 中运行

在 70 年代，Unix 的拼写检查器如何在只有 64kB RAM 的 PDP-11 计算机上运行？这篇文章讲述了 Douglas McIlroy 如何通过巧妙的数据结构和压缩技术解决这一难题。他首先使用布隆过滤器进行快速查找，但随着字典大小的增加，他转向了一种创新的哈希压缩方案。通过分析哈希值的差值符合几何分布，并利用 Golomb 编码，他实现了接近理论极限的压缩率，最终在内存和速度之间取得了平衡。这是一个关于如何在资源受限环境下进行巧妙工程设计的经典案例。