Huffman编码

1 原理

HuffmanCoding根据符号的频率决定编码。符号频率越高则符号编码越短，相反则符号越长。

考虑FORGET五个字母的编码，假定其出现频率如下：

Symbol	F	O	R	G	E	T
Frequency	2	3	4	4	5	7

HuffmanCoding是一种贪心算法，是一种前缀码。Huffman设计了一个贪心算法构造最优前缀码。按照如下方式迭代操作生成HuffmanCoding Tree：

按照出现频率大小对符号排序；
频率最小的两个字母相加形成一个新的节点（内部节点）；
用新的内部节点替换这两个相加的字母，继续比较频率；

上述过程可以使用一个最小二叉堆实现，时间复杂度为\(O(n \log n)\)

最终生成如下图：

         25
      __/   \__
     /         \
    10          15
   /  \        /  \
  5    \      8    \
 / \    \    / \    \
2   3    5  4   4    7
F   O    E  R   G    T

FORGET的编码结果则是：

Symbol	F	O	R	G	E	T
Frequency	2	3	4	4	5	7
Code	000	001	100	101	01	11

2 实现

HuffmanCoding最主要的工作是实现一个HuffmanTree，HuffmanTree是一个二叉树，包含两种节点：

叶子节点包括：Symbol、Frequency、指向父节点的链接；
内部节点包括：左右子节点的链接、Frequencey(左右子节点Frequency之和)、指向父节点的链接；

用0与1分别表示指向左子节点与右子节点，最后完成的树共有n个终端节点与n-1个非终端节点。

2.1 需求描述

元数据一般用做映射。例如，对象 object 2MB-4MB 数据保存在 file3 offset 100MB处，就是一条元数据（KV里也称为一行/row）。

编码之后的数据，需要支持相对快速的查询。这可以通过构建一个稀疏Key索引实现。即一批key 插入一条索引，检索时，可以先用二分快速确定范围。编码时，按照key的有序进行数据编码，可简化稀疏key的生成。

2.2 代码片段

void HuffmanCoder::AddSymbol(uint32_t symbol, uint32_t freq)
{
    mHashMap[symbol] += freq;
}

void HuffmanCoder::GenerateCode()
{
    // Use sort and greedy to generate huffman, see
    // Introduction to Algorithms, Chapter 16.
}

// Encode @code to @buf and @bit offset.
void HuffmanCoder::Encode(const uint32_t code, uint8_t **buf, uint8_t *bit);

// Decode @code from @buf and @bit offset.
void HuffmanCoder::Decode(const uint8_t **buf, uint8_t *bit, uint32_t *code);

Huffman编码

目录

1 原理

2 实现

2.1 需求描述

2.2 代码片段