1970年代，AT&T的Douglas McIlroy重写了Unix spell检查器，面临着在PDP-11计算机有限内存中存储大规模词典的挑战。1他将字典从25,000个词扩展到30,000个词，同时需要将其压缩到64KB的内存空间内。1
McIlroy采用了多种压缩技术来实现这一目标。1最初实现使用Bloom过滤器，由Dennis Ritchie提供实现代码，配置为400,000比特、11个哈希函数，误报率为1/2000。1随后他转向哈希压缩方案，通过计算得出最优哈希码宽度为27比特。1最终采用Golomb编码实现几何分布压缩，达到了13.60比特每词的压缩率。1
这一压缩率接近理论极限13.57比特每词。1为了进一步提升查询速度，McIlroy加入了分区方案，虽然存储开销增至约14比特每词，但换取了显著的性能提升。1
In the 1970s, Douglas McIlroy redesigned the spell checker for Unix at AT&T, undertaking a remarkable engineering challenge to fit an expanded dictionary into the severely constrained memory of a PDP-11 computer.1 The project involved scaling the dictionary from 25,000 words to 30,000 words while keeping the entire system within 64 kilobytes of RAM—a feat that required innovative compression techniques and careful algorithmic optimization.1
McIlroy's initial approach employed a Bloom filter, with implementation code provided by Dennis Ritchie.1 This filter was configured with 400,000 bits, 11 hash functions, and a false positive rate of 1 in 2,000.1 However, to achieve even greater space efficiency, McIlroy later shifted to a hash compression scheme, calculating an optimal hash code width of 27 bits per word.1 Using Golomb encoding to compress geometric distributions, he reached a compression rate of 13.60 bits per word—remarkably close to the theoretical minimum of 13.57 bits per word.1 In a final refinement, McIlroy introduced a partitioning scheme that increased storage overhead to approximately 14 bits per word, a trade-off that delivered significant improvements in query speed.1
评论
还没有评论，欢迎留下第一条。