共 2 篇相关文章
这篇讲的是经典的数据压缩算法——Huffman编码。作者从探索数据压缩的动机出发，引出了由David Huffman提出的这一优雅算法。其核心思想是根据字符出现的频率，利用优先队列和带权重的二叉树（即Huffman树）来构建前缀编码，从而实现压缩。 文章特别指出，虽然Huffman算法本身并不新颖，但中文社区里能清晰讲透其构造过程，尤其是如何一步步构建Huffman树的资料并不多见。为此，作者分享并基于一篇优秀的英文教程进行了转述，其中用一个字符串为例，将构建编码树的步骤拆解得直观易懂，非常适合想要直观理解该算法细节的开发者。 Huffman编码的魅力在于它简单而高效地利用了信息熵的原理，是学习数据结构和算法思想的绝佳案例。
这篇讲的是倒排索引中一个关键但常被忽略的环节：Doclist的压缩。作者从搜索引擎如何高效存储和快速解压海量文档ID列表这个实际问题出发，详细拆解了主流的几种压缩算法。 文章对比了PForDelta、Simple-9、Simple-16以及基于位图的压缩方案。它不仅解释了每种方法的基本原理——比如Simple系列如何利用整数块内的比特位模式来编码变长整数，更重点分析了它们之间的核心权衡：是追求极致的压缩率（如PForDelta），还是更侧重解压速度（如Simple系列），以及字对齐方案如何用牺牲少量空间换取解压的简便性。 最实用的部分在于，作者结合具体数据，指出了不同算法在面对不同特征（如ID序列稀疏度、增长趋势）的Doclist时的表现差异。这直接回答了开发者在实际工程中的选型困惑：没有一种方法是万能的，选择取决于你的索引是更看重存储效率，还是更看重查询时的解压开销。整篇文章将算法细节与工程实践紧密结合，为理解底层优化提供了清晰的视角。
