北京
把一本25万词的词典塞进64KB内存，还得保证飞快查词。这听着像不可能的任务。即便用gzip -9这类现代压缩工具，这个词典文件也无法压到85KB以下。上世纪70年代，贝尔实验室的道格拉斯·麦克罗伊就撞上了这道墙。他要在PDP-11计算机上实现Unix拼写检查，系统留给整个词典的空间，只有64KB。
麦克罗伊没走通用压缩的老路。他从数据本身的特性入手，捣鼓出一套压缩算法，最终效率距离理论压缩极限只差0.03比特。这个记录保持到今天，仍未被打破。
Unix拼写命令的故事起点，是肯·汤普森和丹尼斯·里奇为了给AT&T的专利部门推销Unix，把它包装成一个文本处理系统。文本处理自然少不了拼写检查器。1975年，史蒂夫·约翰逊花了一个下午写出了第一版原型。后来麦克罗伊接手，从性能和准确度上彻底重写。
他的第一项创举是一个基于语言学的词干提取算法。这套算法直接把词典瘦身到了25000个词，准确率不降反升。当时看来，这个体积已经相当可控。
加速查词方面，麦克罗伊先是引入了布隆过滤器——这可能是该数据结构最早的生产应用之一。有意思的是，布隆过滤器的代码实现来自丹尼斯·里奇本人。他们把它调校得假阳性率极低，低到可以跳过实际的词典查表步骤。
好景不长，随着词典扩容到30000词，布隆过滤器的路子走不通了。麦克罗伊开始打哈希压缩的主意。他们算过，27比特的哈希码可以把碰撞概率压在可接受范围内，但这堆哈希码本身还是得压缩。
转折出现在他对数据分布的观察上。麦克罗伊发现，如果把哈希码排序后存差值，这些差值恰好服从几何分布。这就意味着，可以把针对几何分布设计的哥伦布编码请出来。应用这套方案后，平均每个单词的存储开销降到了13.60比特。
理论计算显示，无损压缩的绝对下限是每个单词13.57比特。麦克罗伊的方案已经逼到只差0.03比特的极限地带。为了再给查词加速，他又把压缩后的数据做了分区处理，最终实际存储开销稍有回弹，稳定在约14比特每词，换来的是性能的大幅跃升。
回头去看，Unix拼写检查这个故事远不止一段技术考古趣闻。它展现的是在严苛约束下进行工程设计的完整范式：如何从第一性原理出发拆解问题，如何借助数学洞察力寻找突破口，最终在资源极度受限的硬件上，交付一个优雅得近乎艺术品的解决方案。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
