[C++] 使用 Huffman Tree 哈夫曼树实现对 ASCII 字符串文本的压缩与解压（上）

[C++] 使用 Huffman Tree 哈夫曼树实现对 ASCII 字符串文本的压缩与解压（上） 前情

如果你对树和哈夫曼树的概念比较模糊，可以先看看这篇文章：
[枫铃树] 树和 Huffman Tree 哈夫曼树

用哈夫曼树实现对 ASCII 字符文本的压缩与解压 原理

考虑以下文本：

LarryYYDS

如果直接按照 ASCII 码存储这段文本，由于单个字符需要占据一字节（8 bits）空间，这段文本总共需要占用 9×8=72 (bit) 空间。

---

如果我们对出现的字符进行编号：

字符编号（10进制）编号（2进制）L0000a1001r2010y3011Y4100D5101S6110

靠上表中的二进制编码表示这段文本，即：

000 001 010 010 011 100 100 101 110
（空格只是为了看的清晰）

二进制形式存储，占空间为 27 bits.

---

下面，我们进行一个神奇的 *** 作。
首先，统计这段文本中各个字符出现的频率：

字符出现次数L1a1r2y1Y2D1S1

将这些字符视为一个个带权节点，权值为其在字符串中出现次数（点内为节点对应字符。权值参考上表）。

按照前一部分介绍的方法，构造哈夫曼树：

现在，小萌位于根节点，小汪在某个叶节点（假如是在 L 节点）处。小萌看不到整棵树的模样，但她知道前方的路走向的是当前节点的左孩子还是右孩子。现在，请你来指引她找到小汪。
你可以这样说：

先向右孩子走，再向右孩子走，再向左孩子走，再向右孩子走。

如果小汪位于点 Y 处，你可以这样指引：

先向左孩子走，再向右孩子走。

如果我们把向左孩子走用 0 表示，将向右孩子走用 1 表示，则上面两种走法可以分别描述为：

1101

和

01

假设每次找完，小萌都会传送回根节点，然后小汪会传送到另一个叶节点（也可以原地不动），让小萌再次寻找小汪。那么，如果小汪最初在 L 节点，后来传送到 Y 节点，我们在指引小萌寻找她时，会这样说：

先向右孩子走，再向右孩子走，再向左孩子走，再向右孩子走（此时，已经找到小汪，小萌位置回到根节点，小汪位置变到 Y 点）。先向左孩子走，再向右孩子走（此时，小萌再次找到小汪）。

用 0 和 1 表示，即为：

110101

那么，如果我们把字符串LarryYYDS看作小汪传送到的叶子的顺序（最初在 L 点，之后到 a 点，之后… 最终，小汪在 S 点），那么我们对小萌的指引，使用 0 和 1 表示，即为：

1100 000 10 10 111 01 01 1101 001
（空格只是为了看的清晰）

这段指令用另一种方式表示了LarryYYDS这个字符串。以二进制形式存储，占用空间为 25 bits, 比前面使用的存储方式节省了 27-25=2 (bit) 空间, 压缩率为 2 27 ⋅ 100 % = 7.407 % frac{2}{27}·100%=7.407% 272​⋅100%=7.407% . 如果文本长度更长，节省下来的空间会更多。

样例

现在，小徐和小魏都有一棵这样的树：

小徐写了一段话，借助这棵树进行压缩，得到二进制编码：

01001100011110111101110100011101101000011111101010101111011100111011111110000010100101110110101101101011001110101011010101111000110010010101101111110010001011101010101011000001101111011101100001101100001001001011100010110001001000011101011000101001100111111011001001100011111101000

按照小萌和小汪那个例子里的方式理解，解码这段指令，小魏可以轻松还原小徐写下的文本：

College_of_Electronic_and_Information_Engineering+Tongji_University

C++ 方式实现 我们希望实现的效果

---

如果你忘了哈夫曼树生成原理，快去看这个：
[枫铃树] 树和 Huffman Tree 哈夫曼树

---

接下来，我们开始设计程序。

节点结构体

对于每个节点，它需要存储左右孩子的位置。对于叶节点，还需要存储一个字符信息。计算过程中，每个节点需要存储自己的权重。因此，设计节点结构体如下：

struct Node {
	Node* lc = nullptr;
	Node* rc = nullptr;
	char c = '';
	int weight = 0;
};

其中，lc 是左孩子指针，rc 是右孩子指针。

哈夫曼树生成函数

设计一个函数，根据一段文本，统计字符频率，生成一棵哈夫曼树。
显然，这个函数需要接收文本字符串信息，并将构造完毕的哈夫曼树的根节点返回。于是，它的声明如下：

Node* genHuffmanTree(const char* oriStr);

先创建一个Node指针数组，用于存放字符串中每个字符的权值信息。

Node** nodeArray = new Node* [128];

由于 ASCII 码的范围在 [0, 127], 数组尺寸设为128即可。此处暂未对内存申请失败做处理。希望读者自行完成。
对数组元素初始化。

for (int i = 0; i < 128; i++) {
    nodeArray[i] = nullptr;
}

之后，统计输入文本中每个字符的频率。由于nodeArray中的元素只是指针，我们需要对没有创建的节点进行创建（即，申请内存）。

for (int i = 0; oriStr[i] != ''; i += 1) {
    if (nodeArray[oriStr[i]] == nullptr) {
        nodeArray[oriStr[i]] = new Node;
        nodeArray[oriStr[i]]->c = oriStr[i];
    }
    
    nodeArray[oriStr[i]]->weight += 1;
}

我们需要知道，现在森林里有多少棵树。

int treesCount = 0;
for (int i = 0; i < 128; i++) {
    if (nodeArray[i] != nullptr) {
        treesCount += 1;
    }
}

后续计算中，我们需要两个变量，分别指向两个权值最小的节点。

int idxMostMin;
int idxSecondMin;

为什么是int？ 我们让它表示对应节点在nodeArray中的下标即可。如果读者喜欢使用指针，也可以自行尝试。
对于单次寻找，肯定需要给两个最小值变量赋初值，表明最初没有找到任何满足条件的点。

idxMostMin = -1;
idxSecondMin = -1;

之后，对于每个点，若其下表为 i，只要它不是 nullptr （即：nodeArray[i] != nullptr），就进行以下 *** 作：

1. 如果 idxMostMin 处于默认状态（等于 -1），就直接将它的下标绑定到 idxMostMin （即：idxMostMin = i）。
2. 若不满足第1条，且 idxSecondMin 处于默认状态，就直接将它的下标绑定到 idxSecondMin. 之后，比较两个最小元素的权值。如果 idxMostMin 对应元素的权值比 idxSecondMin 对应的大，就将它们交换。
3. 若不满足1和2，则判断：(i) 如果该元素的权值比 idxMostMin 对应的还要小，就将 idxMostMin 赋值给 idxSecondMin, 然后将 i 赋值给 idxMostMin. (ii) 如果该元素权值不比 idxMostMin 对应的小，但比 idxSecondMin 对应的小，则令 idxSecondMin 等于 i. (iii) 否则，不管它。

由此，可以从现有根节点中找到权值最小的两个点。
具体代码如下：

for (int i = 0; i < 128; i++) {
    if (nodeArray[i] != nullptr) {
        if (idxMostMin == -1) {        
            idxMostMin = i;
        } else if (idxSecondMin == -1) {
            idxSecondMin = i;
            if (nodeArray[idxMostMin]->weight > nodeArray[idxSecondMin]->weight) {
                swap(idxSecondMin, idxMostMin); 
            }
        } else {
            // 两个最小值都已被赋值。
            if (nodeArray[i]->weight < nodeArray[idxMostMin]->weight) {
                idxSecondMin = idxMostMin;
                idxMostMin = i;
            } else if (nodeArray[i]->weight < nodeArray[idxSecondMin]->weight) {
                idxSecondMin = i;
            }
        }
    }
}
// 至此，找到了要绑定成一棵树的两个元素。

创建一个新的节点，其左右孩子为这两个节点，权值为左右孩子权值之和。之后，将两个子节点从nodeArray中移除（对应位置设为 nullptr 即可），将新节点添加到其中任意一个位置（本文选择添加到原来权值最小节点的位置）。

Node* tmpNode = new Node;
tmpNode->weight = nodeArray[idxMostMin]->weight + nodeArray[idxSecondMin]->weight;
tmpNode->lc = nodeArray[idxMostMin];
tmpNode->rc = nodeArray[idxSecondMin];

nodeArray[idxMostMin] = tmpNode;
nodeArray[idxSecondMin] = nullptr;

这时，森林中的树木个数比之前少一个。

treesCount -= 1;

只要森林中有多于一棵树存在，就要不断循环上述过程。因此，上述过程的循环控制条件是 treesCount > 1.

while (treesCount > 1) {
   ... // 上述过程
}

循环结束后，nodeArray中有且仅有一个元素不是 nullptr，它正是整棵哈夫曼树的根节点。找到它并返回即可。当然，不要忘了释放动态申请到的空间（nodeArray）。

Node* huffmanTreeEntry;
for (int i = 0; i < 128; i++) {
    if (nodeArray[i] != nullptr) {
        huffmanTreeEntry = nodeArray[i];
        break;
    }
}
delete[] nodeArray;
// 至此，哈夫曼树构造完毕。
return huffmanTreeEntry;

---

更多内容，请见下篇：
[枫铃树] [C++] 使用 Huffman Tree 哈夫曼树实现对 ASCII 字符串文本的压缩与解压（下）