霍夫曼树和霍夫曼编码

一、定义

霍夫曼树

又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为 WPL =（W1*L1 + W2*L2 + W3*L3 +...+ Wn*Ln），N个权值 Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为 Li（i=1,2,...n）。可以证明霍夫曼树的 WPL 是最小的。

霍夫曼编码

是一种基于霍夫曼树的用于无损数据压缩的熵编码（权编码）算法。

由于霍夫曼树具有 WPL 最小的特性，可认为霍夫曼树中权值越大的叶子结点路径越短，可用霍夫曼树所有叶子结点的路径生成编码方案，其特点是权重越大的结点路径编码越短，反之则越长。

用途

按照 Wikipedia 的说法：

霍夫曼树常处理符号编写工作。根据整组资料中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。

显然，这种编码适用于对高频出现的数据进行编码上的无损压缩，只要知道如何构造一颗霍夫曼树，就能对生成的编码进行解码。

二、实现

霍夫曼树的结点

结点包含如下要素：

data: 存储的数据（本例中为单个字符）
weight: 权重
leftChild/rightChild: 下接的左右子树（形成一个递归的二叉树结构）
IsLeaf(): 判断本结点是否为叶子结点
构造函数

/**
 * Huffman 树的结点，递归数据结构
 */
class HuffmanTreeNode {
public:
    char data;
    float weight;
    HuffmanTreeNode *leftChild{};
    HuffmanTreeNode *rightChild{};
    bool IsLeaf();
    HuffmanTreeNode(float weight, char data);
};

/**

* Huffman 树的结点，递归数据结构

class HuffmanTreeNode {

public:

char data;

float weight;

HuffmanTreeNode *leftChild{};

HuffmanTreeNode *rightChild{};

bool IsLeaf();

HuffmanTreeNode(float weight, char data);

};

结点的实现：

HuffmanTreeNode::HuffmanTreeNode(float weight, char data) {
    this->weight = weight;
    this->data = data;
}

bool HuffmanTreeNode::IsLeaf() {
    return this->leftChild == nullptr && this->rightChild == nullptr;
};

HuffmanTreeNode::HuffmanTreeNode(float weight, char data) {

this->weight = weight;

this->data = data;

}

bool HuffmanTreeNode::IsLeaf() {

return this->leftChild == nullptr && this->rightChild == nullptr;

};

霍夫曼树的概念结构

树本身是一个概念结构，包含如下要素：

nodesTree: 结点数据（用于生成霍夫曼树）
codingMap: 字符和它的编码映射关系
huffmanTree: 运行时生成的最优二叉树（霍夫曼树)
PickMinWeightNode(): 从结点数据中选择一个 weight 最小的结点
CalcWPL(): 生成某个结点的 WPL
GenerateCodingMap(): 生成字符和它的编码映射关系
WPL: 加权路径长度
GetHuffmanCode(): 获取字符的编码
Encode(): 编码（tuple 元素分别为编码的字符串和布尔串形式）
Decode(): 解码
构造函数

#include <vector>
#include <tuple>
#include <map>
using namespace std;

/**
 * 由 Huffman 树结点构成的树的整体概念，及围绕它的一系列功能
 */
class HuffmanTree {
private:
    vector<HuffmanTreeNode*> nodesTree;
    map<char, string> codingMap;
    HuffmanTreeNode* huffmanTree;
    HuffmanTreeNode* PickMinWeightNode();
    void CalcWPL(HuffmanTreeNode *root, int depth);
    void GenerateCodingMap(HuffmanTreeNode *root, string codePath);
    float WPL = 0.0;
public:
    explicit HuffmanTree(vector<tuple<float, char>> nodes);
    float GetWPL();
    string GetHuffmanCode(char ch);
    tuple<string, vector<bool>> Encode(string content);
    string Decode(vector<bool> code);
};

#include <vector>

#include <tuple>

#include <map>

using namespace std;

/**

* 由 Huffman 树结点构成的树的整体概念，及围绕它的一系列功能

class HuffmanTree {

private:

vector<HuffmanTreeNode*> nodesTree;

map<char, string> codingMap;

HuffmanTreeNode* huffmanTree;

HuffmanTreeNode* PickMinWeightNode();

void CalcWPL(HuffmanTreeNode *root, int depth);

void GenerateCodingMap(HuffmanTreeNode *root, string codePath);

float WPL = 0.0;

public:

explicit HuffmanTree(vector<tuple<float, char>> nodes);

float GetWPL();

string GetHuffmanCode(char ch);

tuple<string, vector<bool>> Encode(string content);

string Decode(vector<bool> code);

};

树的构造

不断地查找结点数据 nodesTree 中 weight 最小的结点，并将其从nodesTree 中删除，每两个最小结点以组成一颗新的结点，其 weight 为两结点 weight 之和，两结点成为新结点的左右子结点，将新结点再次回入到 nodesTree 中
重复以上过程，直至清空 nodesTree
生成的 huffmanTree 即为最优二叉树
使用 huffmanTree 生成编码表
使用 huffmanTree 算出 WPL

HuffmanTree::HuffmanTree(vector<tuple<float, char>> nodes) {
    if (nodes.empty()) {
        cout << "[HuffmanTree] nodes are empty" << endl;
        return;
    }

    this->nodesTree.resize(nodes.size());

    for(int i = 0; i < this->nodesTree.size(); i++) {
        auto node = nodes[i];
        this->nodesTree[i] = new HuffmanTreeNode(get<0>(node), get<1>(node));
    }

    // 生成最优二叉树的过程
    while(!this->nodesTree.empty()) {
        auto minNode1 = this->PickMinWeightNode();
        if (this->nodesTree.empty()) {
            this->huffmanTree = minNode1;
            break;
        }
        auto minNode2 = this->PickMinWeightNode();

        this->huffmanTree = new HuffmanTreeNode(
                minNode1->weight + minNode2->weight, ' ');
        this->huffmanTree->leftChild = minNode1;
        this->huffmanTree->rightChild = minNode2;
        this->nodesTree.push_back(this->huffmanTree);
    }

    this->GenerateCodingMap(this->huffmanTree, "");

    this->CalcWPL(this->huffmanTree, 0);
}

HuffmanTree::HuffmanTree(vector<tuple<float, char>> nodes) {

if (nodes.empty()) {

cout << "[HuffmanTree] nodes are empty" << endl;

return;

}

this->nodesTree.resize(nodes.size());

for(int i = 0; i < this->nodesTree.size(); i++) {

auto node = nodes[i];

this->nodesTree[i] = new HuffmanTreeNode(get<0>(node), get<1>(node));

}

// 生成最优二叉树的过程

while(!this->nodesTree.empty()) {

auto minNode1 = this->PickMinWeightNode();

if (this->nodesTree.empty()) {

this->huffmanTree = minNode1;

break;

}

auto minNode2 = this->PickMinWeightNode();

this->huffmanTree = new HuffmanTreeNode(

minNode1->weight + minNode2->weight, ' ');

this->huffmanTree->leftChild = minNode1;

this->huffmanTree->rightChild = minNode2;

this->nodesTree.push_back(this->huffmanTree);

}

this->GenerateCodingMap(this->huffmanTree, "");

this->CalcWPL(this->huffmanTree, 0);

}

查找权重最小的结点

HuffmanTreeNode* HuffmanTree::PickMinWeightNode() {
    if (this->nodesTree.empty()) return nullptr;

    int min_index;
    float min = INT_MAX;
    for (int i = 0; i < this->nodesTree.size(); i++) {
        if (this->nodesTree[i]->weight < min) {
            min = this->nodesTree[i]->weight;
            min_index = i;
        }
    }

    auto node = this->nodesTree[min_index];
    this->nodesTree.erase(this->nodesTree.begin() + min_index);

    return node;
}

HuffmanTreeNode* HuffmanTree::PickMinWeightNode() {

if (this->nodesTree.empty()) return nullptr;

int min_index;

float min = INT_MAX;

for (int i = 0; i < this->nodesTree.size(); i++) {

if (this->nodesTree[i]->weight < min) {

min = this->nodesTree[i]->weight;

min_index = i;

}

auto node = this->nodesTree[min_index];

this->nodesTree.erase(this->nodesTree.begin() + min_index);

return node;

}

生成编码表

路径编码方法：

任一结点到其左子结点编码为 “0”
任一结点到其右子结点编码为”1″

任一叶结点的编码，就是由根到叶结点的路径编码串

void HuffmanTree::GenerateCodingMap(HuffmanTreeNode *root, string codePath) {
    if (root != nullptr) {
        if (root->IsLeaf()) {
            this->codingMap[root->data] = codePath;
        } else {
            this->GenerateCodingMap(root->leftChild, codePath + "0");
            this->GenerateCodingMap(root->rightChild, codePath + "1");
        }
    }
};

void HuffmanTree::GenerateCodingMap(HuffmanTreeNode *root, string codePath) {

if (root != nullptr) {

if (root->IsLeaf()) {

this->codingMap[root->data] = codePath;

} else {

this->GenerateCodingMap(root->leftChild, codePath + "0");

this->GenerateCodingMap(root->rightChild, codePath + "1");

}

};

树的 WPL

void HuffmanTree::CalcWPL(HuffmanTreeNode *root, int depth) {
    if (root != nullptr) {
        if (root->IsLeaf()) this->WPL += depth * root->weight;
        this->CalcWPL(root->leftChild, depth + 1);
        this->CalcWPL(root->rightChild, depth + 1);
    }
}

float HuffmanTree::GetWPL() {
    return this->WPL;
}

void HuffmanTree::CalcWPL(HuffmanTreeNode *root, int depth) {

if (root != nullptr) {

if (root->IsLeaf()) this->WPL += depth * root->weight;

this->CalcWPL(root->leftChild, depth + 1);

this->CalcWPL(root->rightChild, depth + 1);

}

float HuffmanTree::GetWPL() {

return this->WPL;

}

编码

/**
 * 将明文编码成 Huffman 码
 * @param content 明文
 * @return Huffman码 <编码的字符串形式, 编码的 vector<bool>>
 */
tuple<string, vector<bool>> HuffmanTree::Encode(string content) {
    tuple<string, vector<bool>> result;

    if (this->codingMap.empty()) {
        cout << "please generate the map at first!" << endl;
        return result;
    }

    stringstream buffer;
    for (int i = 0; i < content.size(); i++) {
        buffer << this->GetHuffmanCode(content[i]);
    }

    get<0>(result)  = buffer.str();
    get<1>(result).resize(get<0>(result).size());
    for (int i = 0; i < get<0>(result).size(); i++)
        get<1>(result)[i] = get<0>(result)[i] == '1';
    return result;
};

/**

* 将明文编码成 Huffman 码

* @param content 明文

* @return Huffman码 <编码的字符串形式, 编码的 vector<bool>>

tuple<string, vector<bool>> HuffmanTree::Encode(string content) {

tuple<string, vector<bool>> result;

if (this->codingMap.empty()) {

cout << "please generate the map at first!" << endl;

return result;

}

stringstream buffer;

for (int i = 0; i < content.size(); i++) {

buffer << this->GetHuffmanCode(content[i]);

}

get<0>(result) = buffer.str();

get<1>(result).resize(get<0>(result).size());

for (int i = 0; i < get<0>(result).size(); i++)

get<1>(result)[i] = get<0>(result)[i] == '1';

return result;

};

解码

/**
 * 将 Huffman 码解码成明文
 * @param code 表示 Huffman 码的 vector<bool>
 * @return code 对应的明文
 */
string HuffmanTree::Decode(vector<bool> code) {
    if (this->codingMap.empty()) {
        cout << "please generate the coding map at first!" << endl;
        return "";
    }

    stringstream buffer, temp;
    HuffmanTreeNode *current = this->huffmanTree;
    for (int i = 0; i < code.size(); i++) {
        if (current->IsLeaf()) {
            buffer << current->data;;
            temp.str("");
            temp.clear();
            current = this->huffmanTree;
        }

        auto c = code[i];
        temp << c;
        if (!c) current = current->leftChild;
        else current = current->rightChild;
    }
    if (!temp.str().empty()) {
        buffer << current->data;
    }

    return buffer.str();
};

/**

* 将 Huffman 码解码成明文

* @param code 表示 Huffman 码的 vector<bool>

* @return code 对应的明文

string HuffmanTree::Decode(vector<bool> code) {

if (this->codingMap.empty()) {

cout << "please generate the coding map at first!" << endl;

return "";

}

stringstream buffer, temp;

HuffmanTreeNode *current = this->huffmanTree;

for (int i = 0; i < code.size(); i++) {

if (current->IsLeaf()) {

buffer << current->data;;

temp.str("");

temp.clear();

current = this->huffmanTree;

}

auto c = code[i];

temp << c;

if (!c) current = current->leftChild;

else current = current->rightChild;

}

if (!temp.str().empty()) {

buffer << current->data;

}

return buffer.str();

};

三、小结

要利用好霍夫曼编码，需在生成树结构前，提炼出大部分应用场景中数据结点（字符或是词组之类元数据）的使用频率，以此做为结点的权重，方能最大化使用编码的收益。

打赏作者

您的支持将激励我继续创作！

去打赏

Mo Ye

A Conservative

Published

March 3, 2023

Mo Ye in Algorithm | March 3, 2023