哈夫曼树

发表于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

Data Structures Experiment #9 - 完成哈夫曼树类的私有属性以及接口，实现哈夫曼树类。

在HuffmanTree类中给出了四个函数:

  • HuffmanTree(const char* str);
    将str构建为哈夫曼树，要求权值较小的节点放在左子，左子编号为0。例如"aaaabbc"的树生成如下。

    HufTree

  • char* getencode(char c);
    获取字符c的编码。将结果以char*的形式返回。上例中的 getencode(‘c’)返回结果为00。

  • int getWPL();
    返回哈夫曼树的WPL。

  • ~HuffmanTree();
    哈夫曼树的析构函数。

0x00 数据域封装

定义Huffman树结点类型HTNode，包括结点字符、权、父结点、左子、右子、编码等。
存储叶结点个数leaves和结点个数nodes。
存储结点转换后的编码。

最终将建成的Huffman树存储在HTNode型数组中，前leaves项存储叶结点，后nodes - leaves项存储根结点。

由于父结点、左子、右子可以用数组下标指向，故声明为int型。

为便于操作字符串，将结点编码声明为string型，需要包含<string>头文件。

1
2
3
4
5
6
7
8
9
10
11
private:
    struct HTNode {
        char data;
        int weight;
        std::string code;
        int lChild, rChild, parent;
    };
    HTNode* HufTree;
    int leaves;
    int nodes;
    char* encode;

0x01 构造函数

由于构造Huffman树的步骤较多，为便于理解，我将构造函数分为Reading->Initializing->Combining->Encoding->Freeing五个阶段。

Reading

此阶段读取char*型的str，并存储其中的字符和权。

应考虑str中字符未必连续，故算法进行了改进：先读取字符，再读取权。（此处感谢@刘宇婷同学的指正）

计算权之前，需要对权数组初始化，即全部赋0。若忽略此操作，虽然macOS与Linux均可正常运行，但Windows下会出现错误，因为未对数组初始化导致数组各项存放的值均为“垃圾值”，不可确定。这与其他变量的声明类似，声明后不初始化不是好的编程习惯。（此处感谢@刘宇婷同学的指正）

操作C字符串需要包含<cstring>头文件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int size;
char* ch = new char[strlen(str)];
int* weigh = new int[strlen(str)];
size = 0;
ch[0] = str[0];

for (int i = 1; i < strlen(str); i++) {
    bool exist = false;
    for (int j = 0; j < size + 1; j++) {
        if (str[i] == ch[j])
            exist = true;
    }
    if (!exist)
        ch[++size] = str[i];
}
leaves = size + 1;
nodes = 2 * leaves - 1;

for (int i = 0; i < leaves; i++) {
    weigh[i] = 0;
    for (int j = 0; j < strlen(str); j++) {
        if (ch[i] == str[j])
            weigh[i]++;
    }
}

Initializing

此阶段用上一阶段存储的字符数组和权数组来初始化Huffman数组的前部分（叶结点），其他赋值为-1便于进行判断。

char*型结点编码encode在此处定义，便于以后使用。

此处若encode未被定义，则会出现报错Segmentation fault: 11。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
HufTree = new HTNode[nodes];
encode = new char[nodes];

for (int i = 0; i < nodes; i++) {
    HufTree[i].weight = 0;
    HufTree[i].parent = -1;
    HufTree[i].lChild = -1;
    HufTree[i].rChild = -1;
    if (i < leaves) {
        HufTree[i].data = ch[i];
        HufTree[i].weight = weigh[i];
        HufTree[i].code = "";
    }
}

Combining

此阶段将上一阶段初始化的Huffman数组进行合并，构建Huffman树。

合并时需要寻找权最小的两个结点，故另构造Searching函数，此函数须写在构造函数外部。

Searching

由于需要找到权最小的两个结点，可以直接赋值给参数，使用引用传递。

此处应确保最小权为正，因为权为0即结点未初始化，权为负即结点被屏蔽。

初始化min和_min时应确保其为正，不可以直接取第0位，可能会导致判断出现错误。（此处感谢@刘宇婷同学的指正）

不要忘记初始化后break。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void HuffmanTree::mini(int& left, int& right) {
    int min, _min;
    for (int i = 0; i < nodes; i++) {
        if (HufTree[i].weight > 0) {
            min = _min = HufTree[i].weight;
            left = right = i;
            break;
        }
    }

    for (int i = 0; i < nodes; i++) {
        if (HufTree[i].weight < min && HufTree[i].weight > 0) {
            min = HufTree[i].weight;
            left = i;
        }
    }

    for (int i = 0; i < nodes; i++) {
        if (HufTree[i].weight < _min && HufTree[i].weight > min && HufTree[i].weight > 0) {
            _min = HufTree[i].weight;
            right = i;
        }
    }
}

Combining

寻找权最小的两个结点，进行合并。

将所得父结点存储在Huffman数组后部分（根结点），将后部分进行初始化。

合并之后需要将两个子结点屏蔽，不会出现在以后的Searching中。

此处若不处理已经合并的结点，则下次寻找时仍会返回此结点而出现错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = leaves; i < nodes; i++) {
    int min1, min2;
    mini(min1, min2);

    HufTree[min1].parent = HufTree[min2].parent = i;
    HufTree[i].lChild = min1;
    HufTree[i].rChild = min2;

    HufTree[i].weight = HufTree[min1].weight + HufTree[min2].weight;

    HufTree[min1].weight = -HufTree[min1].weight;
    HufTree[min2].weight = -HufTree[min2].weight;
}

Encoding

此阶段将上一阶段构建完成的Huffman树的叶结点进行编码，通过寻找每一个叶结点的父结点，再寻找该父结点的父结点……以此类推，每次追溯父结点时判断子结点是父结点的左子还是右子，编码字符串相应地添加0或1。最后将所得字符串反转，即为编码。

为实现字符串的反转，需要#include <algorithm>。

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < leaves; i++) {
    int parent_index = HufTree[i].parent;
    int child_index = i;
    while (parent_index != -1) {
        if (child_index == HufTree[parent_index].lChild)
            HufTree[i].code += "0";
        else if (child_index == HufTree[parent_index].rChild)
            HufTree[i].code += "1";
        child_index = parent_index;
        parent_index = HufTree[parent_index].parent;
    }
    reverse(HufTree[i].code.begin(), HufTree[i].code.end());
}

Freeing

释放字符数组和权数组内存。

1
2
delete[] ch;
delete[] weigh;

至此，构造函数已经完成。

0x02 Get Encode

遍历叶结点，找到c字符对应的结点，将其编码转换为char*型，存储于构造函数的encode中。

1
2
3
4
5
6
7
8
9
10
11
12
char* HuffmanTree::getcode(char c){
    for (int i = 0; i < leaves; i++) {
        if (HufTree[i].data == c) {
            for (int j = 0; j < HufTree[i].code.length(); j++)
                encode[j] = HufTree[i].code[j];
            encode[HufTree[i].code.length()] = '\0';

            return encode;
        }
    }
    return NULL;
}

0x03 Get WPL

WPL：Weighted Path Length（带权路径长度），计算公式如下。$$WPL =\sum_{k=1}^nw_kl_k$$

1
2
3
4
5
6
7
8
9
int HuffmanTree::getWPL() {
    int WPL;
    WPL = 0;

    for (int i = 0; i < leaves; i++)
        WPL += -HufTree[i].weight * HufTree[i].code.length();

    return WPL;
}

0x04 析构函数

释放内存。

1
2
3
4
HuffmanTree::~HuffmanTree() {
    delete[] HufTree;
    delete[] encode;
}