6 hours ago
- Douglas McIlroy通过压缩和哈希差异技术，将Unix拼写检查器的25万词字典装入64KB内存中。
- 通过词缀去除算法（去除前缀和后缀），字典被缩减至25,000个单词。
- 初始查找使用一个400,000位、11个哈希函数的布隆过滤器，实现了1/2000的假阳性率。
- 当字典增至30,000个单词时，布隆过滤器因内存限制变得不可行。
- 选择了27位哈希码以降低冲突概率，但需要压缩才能适应内存。
- McIlroy利用信息论计算出每个单词的理论最小压缩率为13.57比特。
- 哈希差异被建模为几何分布，从而能够使用哥伦布编码进行高效压缩。
- 哥伦布编码实现了每个单词13.60比特的压缩率，非常接近理论最小值。
- 将压缩数据分区存储到多个桶中，以最小内存开销（每个单词14比特）加快查找速度。
- Unix拼写检查器经历了三个发展阶段：词缀去除、布隆过滤器、以及基于哥伦布编码的压缩哈希。