1970年代，在64 kb的RAM上实施拼写检查器，导致了一种在技术上不败的压缩算法，并且其中一部分仍在使用

拼写检查是当今软件的无处不在功能
，我们希望在浏览器和基本文本编辑器以及几乎所有计算设备上看到它。但是，由于缺乏记忆力 ，即使影响了该时代的超级计算机
，因此50年前的实施是一个重大挑战 。该解决方案是如此有效，以至于核心技术开发了一种无损的压缩算法
。

好的 ，所以一个五十年的计算故事并不是“新闻”
，但是由于及时提醒了Hackaday的工作，我们认为这是值得分享的 ，为此
，我们必须求助于Abhinav Upadhyay关于该主题的博客。

这一切始于1975年，当时AT＆T的程序员希望实施UNIX作为公司专利部门的文本处理器 。操作系统不是文字处理器的正常选择 ，但是嘿
，当时情况有所不同
。在这样的角色中使用UNIX的一个障碍是，它需要具有功能齐全的拼写检查系统。

这样做的最简单方法是将整个字典倾倒到系统内存中 ，然后让计算机查找单词 。但是，这不仅要慢
，而且当时的计算机根本没有足够的内存来存储字典
。随着Upadhyay在他的博客中开始：如何将250 KB的文件拟合到仅64 kb的RAM中？

当然，您会压缩它 ，但这并不像看起来那么容易。例如
，我可以制作一个256 kb的文本文件，包含超过260,000个相同的字符 ，并使用文件压缩工具和Lempel＆ndash; Ziv; Markov链链算法（LMZA）将其压缩到只有257 字节
，但这是一台现代计算机上，带有超快速的 ，多层处理器和大量快速的Ram＆Mdash;这是一本无用的词典 。

AT＆T使用的是PDP-111机器
，这些机器在处理能力和内存方面已经光明了
。在该年龄的计算机上搜索这样的压缩文件将是真实的，而我的压缩文本文件仅适用于一个单词。

Unix的咒语检查器的第一个原型将计算机科学家史蒂夫·约翰逊（Steve Johnson）带到了一个下午的大部分时间 ，而在工作时
，它是缓慢的（因为它是基于磁盘的），并且容易犯错 。贝尔实验室的Unix先驱道格拉斯·麦克罗伊（Douglas McIlroy）随后拿起手套 ，并在两个方面解决了问题：一种用于减少字典中单词大小的算法和词典的数据结构，以便适合几个系统记忆。

Updadhyay仔细阅读了这两种机制背后的所有数学
，尽管它确实需要在数学和计算机科学方面进行彻底的基础，以便有任何理解的机会
。

重要的是最终结果。麦克罗伊（McIlroy）的工作最终导致了一种算法 ，每个单词都需要一个惊人的14位记忆 。一本具有30,000个条目的词典将占52 KB以下的分数
。与系统的理论最小尺寸为13.57位（更高的内存使用是使查找单词更快的速度）
，因此可以公平地说McIlroy做得不可思议。就其距离其理论限制的距离而言，这种可用压缩的水平仍然无与伦比 。

他的一部分解决方案涉及使用Golomb编码 ，这是一种如今仍在使用的无损压缩形式
，以稻米编码的形式，如FLAC ，Apple无损和无损JPEG所用
。当然
，现代咒语调查器的工作方式非常不同，例如 ，它们的处理方式与约翰逊和Mcilory的限制并不像记事本一样
，例如“记事本 ”，仅需要32 MB的记忆才能为自己而言 ，并且只能在1970年代梦dream以求。

可以证明，如果有的话
，最具创造性的编程解决方案是在硬件约束的胁迫下出生的 。当今的计算机非常有能力，拥有大量资源 ，以至于许多解决方案都是“它的工作起作用
”的形式
。