频率统计与Huffman树构建

本节阅读量:

文件读取

std::ifstream 是C++标准库提供的输入文件流，用于从文件读取数据。

基本用法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <fstream>

// 打开文件
std::ifstream inFile("input.txt");

// 检查文件是否成功打开
if (!inFile) {
    std::cerr << "无法打开文件" << std::endl;
    return false;
}

// 读取文件内容
char ch;
while (inFile.get(ch)) {  // 逐字符读取
    std::cout << ch;
}

// 关闭文件
inFile.close();

二进制模式 vs 文本模式

文本模式（默认）：

1

std::ifstream inFile("input.txt");  // 文本模式

Windows系统会将 \r\n 转换为 \n
Unix系统不做转换
适合读取文本文件

二进制模式：

1

std::ifstream inFile("input.txt", std::ios::binary);

不会做任何字符转换
原样读取文件内容
适合压缩文件、图片等二进制文件

本项目使用二进制模式，因为：

需要精确读取每个字节
不能让系统做字符转换
支持任意类型的文件

逐字符读取

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


std::ifstream inFile("input.txt", std::ios::binary);
if (!inFile) {
    std::cerr << "无法打开输入文件" << std::endl;
    return false;
}

char ch;
while (inFile.get(ch)) {
    // 处理字符 ch
    std::cout << ch;
}

inFile.close();

get() 方法的几种用法：

1
2
3
4
5
6
7
8


char ch;
inFile.get(ch);  // 读取一个字符

std::string line;
std::getline(inFile, line);  // 读取一行

char buffer[100];
inFile.getline(buffer, 100);  // 读取一行到C风格字符串

错误处理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


std::ifstream inFile("input.txt", std::ios::binary);

// 检查文件是否成功打开
if (!inFile) {
    std::cerr << "无法打开文件: " << "input.txt" << std::endl;
    return false;
}

// 检查读取是否成功
char ch;
inFile.get(ch);
if (inFile.eof()) {
    std::cout << "到达文件末尾" << std::endl;
} else if (inFile.fail()) {
    std::cout << "读取失败" << std::endl;
}

// 重置错误状态
inFile.clear();

频率统计实现

std::unordered_map 详解

std::unordered_map 是基于哈希表实现的关联容器，提供平均 O(1) 的查找、插入和删除操作。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


#include <unordered_map>

std::unordered_map<char, int> freq;

// 插入元素
freq['a'] = 5;
freq.insert({'b', 3});

// 访问元素
int count = freq['a'];  // 5

// 检查元素是否存在
if (freq.count('c') > 0) {
    std::cout << "字符 c 存在" << std::endl;
}

// 遍历
for (auto const& pair : freq) {
    std::cout << "字符: " << pair.first 
              << ", 频率: " << pair.second << std::endl;
}

实现频率统计

1
2
3
4
5
6


std::unordered_map<char, int> freq;
char ch;

while (inFile.get(ch)) {
    freq[ch]++;  // 统计每个字符出现的次数
}

等价写法：

1
2
3


freq[ch] = freq[ch] + 1;  // 方式1
freq[ch] += 1;           // 方式2
++freq[ch];              // 方式3

特殊字符处理

以下字符在文件中会出现，需要正确处理：

字符	转义表示	含义
`\n`	`0x0A`	换行符
`\r`	`0x0D`	回车符
`\t`	`0x09`	制表符
	`0x20`	空格
`\0`	`0x00`	空字符

好消息：std::unordered_map 的键是 char 类型，可以存储任意字节值（0-255），所以特殊字符会自动正确处理！

边界情况

情况1：空文件

1
2
3
4


if (freq.empty()) {
    std::cerr << "输入文件为空" << std::endl;
    return false;
}

情况2：只有一个字符

1
2
3
4


if (freq.size() == 1) {
    // 只有一个字符，编码就是 "0"
    std::cout << "警告：文件只有一个不同的字符" << std::endl;
}

情况3：所有字符都相同

1
2
3


// 例如：文件内容是 "aaaaa"
// freq = {'a': 5}
// 仍然可以正常处理

完整的频率统计代码

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


bool HuffmanCoder::compress(const std::string& inputFile, const std::string& outputFile) {
    // 读取输入文件
    std::ifstream inFile(inputFile, std::ios::binary);
    if (!inFile) {
        std::cerr << "无法打开输入文件: " << inputFile << std::endl;
        return false;
    }
    
    // 统计字符频率
    std::unordered_map<char, int> freq;
    char ch;
    while (inFile.get(ch)) {
        freq[ch]++;
    }
    inFile.close();
    
    // 检查文件是否为空
    if (freq.empty()) {
        std::cerr << "输入文件为空" << std::endl;
        return false;
    }
    
    // 打印频率统计
    std::cout << "字符频率统计:" << std::endl;
    for (auto const& pair : freq) {
        unsigned char c = static_cast<unsigned char>(pair.first);
        std::string displayChar;
        
        // 1. 先判断常见的特殊字符（不可见）
        if (pair.first == '\n') {
            displayChar = "\\n (换行)";
        } else if (pair.first == '\t') {
            displayChar = "\\t (制表)";
        } else if (pair.first == '\r') {
            displayChar = "\\r (回车)";
        } else if (pair.first == ' ') {
            displayChar = "space";
        }
        // 2. 再判断是否是可打印字符（包括数字、字母、标点等）
        else if (std::isprint(c)) {
            displayChar = std::string(1, pair.first);
        }
        // 3. 其他情况统一显示为十六进制
        else {
            char hex[10];
            snprintf(hex, sizeof(hex), "0x%02X", c);
            displayChar = hex;
        }
        
        std::cout << "  '" << displayChar << "' 出现 "
                  << pair.second << " 次" << std::endl;
    }
    
    return true;
}

构建Huffman树

详细算法步骤

 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
26


void HuffmanCoder::buildTree(const std::unordered_map<char, int>& freq) {
    // 步骤1：创建优先队列
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    
    // 步骤2：为每个字符创建叶子节点
    for (auto const& pair : freq) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
    
    // 步骤3：构建Huffman树
    while (pq.size() != 1) {
        // 取出频率最小的两个节点
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        
        // 创建内部节点，频率为子节点之和
        int sum = left->frequency + right->frequency;
        HuffmanNode* newNode = new HuffmanNode(sum, left, right);
        
        // 将新节点放回优先队列
        pq.push(newNode);
    }
    
    // 步骤4：根节点就是队列中剩下的唯一节点
    root = pq.top();
}

图解构建过程

假设频率统计结果为：

a: 5
b: 3
c: 2
d: 7

步骤1：创建叶子节点和优先队列

优先队列（最小堆）：
  (2)   ← c
  (3)   ← b
  (5)   ← a
  (7)   ← d

步骤2：取出最小的两个节点（c和b）

取出：c(2), b(3)
合并：newNode(5)

优先队列：
  (5)   ← a
  (5)   ← newNode (内部节点)
  (7)   ← d

树结构：
      (5)
     /   \
   (2)   (3)
    c     b

步骤3：取出最小的两个节点（a和newNode）

取出：a(5), newNode(5)
合并：newNode2(10)

优先队列：
  (7)   ← d
  (10)  ← newNode2 (内部节点)

树结构（newNode2）：
       (10)
      /    \
    (5)    (5)
     a     /  \
         (2)  (3)
          c    b

步骤4：取出最后的两个节点

取出：d(7), newNode2(10)
合并：root(17)

优先队列：
  (17)  ← root

最终树结构：
          (17)
         /    \
       (7)   (10)
       d     /  \
          (5)   (5)
           a   /  \
              (2)  (3)
               c    b

手动追踪算法执行

让我们用代码追踪字符串 "aabbbccddd" 的树构建过程：

1
2
3
4
5
6
7
8
9


std::unordered_map<char, int> freq = {
    {'a', 2},
    {'b', 3},
    {'c', 2},
    {'d', 3}
};

// 调用 buildTree
coder.buildTree(freq);

执行过程：

初始状态：
pq = [a(2), c(2), b(3), d(3)]

第1轮：
- pop a(2), pop c(2)
- push node1(4)
pq = [b(3), d(3), node1(4)]
树：
  node1(4)
    /  \
  a(2) c(2)

第2轮：
- pop b(3), pop d(3)
- push node2(6)
pq = [node1(4), node2(6)]
树：
  node1(4)  node2(6)
    /  \      /  \
  a(2) c(2) b(3) d(3)

第3轮：
- pop node1(4), pop node2(6)
- push root(10)
pq = [root(10)]
树：root(10) = [node1(4), node2(6)]

最终树：
        root(10)
       /      \
  node1(4)  node2(6)
    /  \      /  \
  a(2) c(2) b(3) d(3)

算法复杂度分析

时间复杂度

创建叶子节点：O(n)，n是不同字符的数量
每次插入和删除优先队列：O(log n)
合并循环执行 n-1 次：O(n log n)
总时间复杂度：O(n log n)

空间复杂度

存储所有节点：O(n)
优先队列存储：O(n)
总空间复杂度：O(n)

树的递归删除

为什么要手动删除内存？

在C++中，动态分配的内存需要手动释放，否则会导致内存泄漏。

内存泄漏示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void buildBadTree() {
    HuffmanNode* root = new HuffmanNode('a', 5);
    // 构建树...
    // 忘记删除 root！
}  // 函数结束，root 指针销毁，但分配的内存没有被释放

int main() {
    for (int i = 0; i < 1000000; i++) {
        buildBadTree();  // 每次调用都泄漏内存
    }
    // 程序可能因为内存耗尽而崩溃
}

deleteTree 函数实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void HuffmanCoder::deleteTree(HuffmanNode* node) {
    if (node == nullptr) {
        return;  // 空节点，直接返回
    }
    
    // 后序遍历：先删除子树，再删除自己
    deleteTree(node->left);   // 删除左子树
    deleteTree(node->right);  // 删除右子树
    delete node;              // 删除当前节点
}

为什么使用后序遍历？

错误示例：前序遍历

1
2
3
4
5
6
7


void deleteTreeWrong(HuffmanNode* node) {
    if (node == nullptr) return;
    
    delete node;              // ❌ 先删除自己
    deleteTree(node->left);   // ❌ 访问已释放的内存！
    deleteTree(node->right);  // ❌ 未定义行为
}

正确示例：后序遍历

1
2
3
4
5
6
7


void deleteTreeCorrect(HuffmanNode* node) {
    if (node == nullptr) return;
    
    deleteTree(node->left);   // ✓ 先删除左子树
    deleteTree(node->right);  // ✓ 再删除右子树
    delete node;              // ✓ 最后删除自己
}

图示后序遍历删除过程：

删除前：
        A
       / \
      B   C
     / \
    D   E

第1步：删除 D（叶子节点）
        A
       / \
      B   C
       \
        E

第2步：删除 E（叶子节点）
        A
       / \
      B   C

第3步：删除 B（现在是叶子节点）
        A
         \
          C

第4步：删除 C（现在是叶子节点）
        A

第5步：删除 A（根节点）
        （空）

RAII资源管理思想

RAII (Resource Acquisition Is Initialization) 是一种C++的资源管理技术：资源的获取与释放与对象的生命周期绑定。

在本项目中的应用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class HuffmanCoder {
private:
    HuffmanNode* root;
    
public:
    HuffmanCoder() : root(nullptr) {
        // 构造函数：资源获取
    }
    
    ~HuffmanCoder() {
        deleteTree(root);  // 析构函数：资源自动释放
        // 不需要手动调用 deleteTree！
    }
};

// 使用示例
{
    HuffmanCoder coder;  // 创建对象，root = nullptr
    coder.buildTree(freq);  // 构建树
    // 使用 coder 进行压缩...
}  // 离开作用域，析构函数自动调用，清理树内存

RAII的好处：

自动清理：不会忘记释放资源
异常安全：即使发生异常，析构函数也会被调用
代码简洁：不需要到处调用清理函数

完整代码实现

更新 huffman.cpp

  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
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103


#include "huffman.h"
#include <iostream>
#include <iomanip>

HuffmanCoder::HuffmanCoder() : root(nullptr) {}

HuffmanCoder::~HuffmanCoder() {
    deleteTree(root);
}

void HuffmanCoder::deleteTree(HuffmanNode* node) {
    if (node == nullptr) return;
    
    // 后序遍历删除树
    deleteTree(node->left);
    deleteTree(node->right);
    delete node;
}

void HuffmanCoder::buildTree(const std::unordered_map<char, int>& freq) {
    std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, Compare> pq;
    
    // 为每个字符创建叶子节点
    for (auto const& pair : freq) {
        pq.push(new HuffmanNode(pair.first, pair.second));
    }
    
    // 构建Huffman树
    while (pq.size() != 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        
        int sum = left->frequency + right->frequency;
        pq.push(new HuffmanNode(sum, left, right));
    }
    
    root = pq.top();
}

bool HuffmanCoder::compress(const std::string& inputFile, const std::string& outputFile) {
    // 读取输入文件
    std::ifstream inFile(inputFile, std::ios::binary);
    if (!inFile) {
        std::cerr << "无法打开输入文件: " << inputFile << std::endl;
        return false;
    }
    
    // 统计字符频率
    std::unordered_map<char, int> freq;
    char ch;
    while (inFile.get(ch)) {
        freq[ch]++;
    }
    inFile.close();
    
    // 检查文件是否为空
    if (freq.empty()) {
        std::cerr << "输入文件为空" << std::endl;
        return false;
    }
    
    // 打印频率统计
    std::cout << "字符频率统计:" << std::endl;
    for (auto const& pair : freq) {
        unsigned char c = static_cast<unsigned char>(pair.first);
        std::string displayChar;
        
        // 1. 先判断常见的特殊字符（不可见）
        if (pair.first == '\n') {
            displayChar = "\\n (换行)";
        } else if (pair.first == '\t') {
            displayChar = "\\t (制表)";
        } else if (pair.first == '\r') {
            displayChar = "\\r (回车)";
        } else if (pair.first == ' ') {
            displayChar = "space";
        }
        // 2. 再判断是否是可打印字符（包括数字、字母、标点等）
        else if (std::isprint(c)) {
            displayChar = std::string(1, pair.first);
        }
        // 3. 其他情况统一显示为十六进制
        else {
            char hex[10];
            snprintf(hex, sizeof(hex), "0x%02X", c);
            displayChar = hex;
        }
        
        std::cout << "  '" << displayChar << "' 出现 "
                  << pair.second << " 次" << std::endl;
    }
    
    // 构建Huffman树
    buildTree(freq);
    std::cout << "✓ Huffman树构建成功" << std::endl;
    
    return true;
}

bool HuffmanCoder::decompress(const std::string& inputFile, const std::string& outputFile) {
    std::cout << "解压功能将在后续章节实现！" << std::endl;
    return true;
}

更新 main.cpp

 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
26
27
28
29
30
31
32
33
34
35
36
37


#include "huffman.h"
#include <iostream>

int main(int argc, char* argv[]) {
    std::cout << "=== Huffman编码压缩工具测试 ===" << std::endl;
    
    if (argc != 4) {
        std::cout << "用法: " << argv[0] << " -c <输入文件> <输出文件>" << std::endl;
        std::cout << "      " << argv[0] << " -d <输入文件> <输出文件>" << std::endl;
        return 1;
    }
    
    std::string mode = argv[1];
    std::string inputFile = argv[2];
    std::string outputFile = argv[3];
    
    HuffmanCoder huffman;
    
    if (mode == "-c") {
        std::cout << "正在压缩文件: " << inputFile << " -> " << outputFile << std::endl;
        if (!huffman.compress(inputFile, outputFile)) {
            std::cerr << "压缩失败！" << std::endl;
            return 1;
        }
    } else if (mode == "-d") {
        std::cout << "正在解压文件: " << inputFile << " -> " << outputFile << std::endl;
        if (!huffman.decompress(inputFile, outputFile)) {
            std::cerr << "解压失败！" << std::endl;
            return 1;
        }
    } else {
        std::cerr << "无效的模式: " << mode << std::endl;
        return 1;
    }
    
    return 0;
}

测试

1
2
3
4
5


# 创建测试文件
echo -n "aabbbccddd" > test.txt

# 测试压缩
./huffman -c test.txt test.huf

预期输出：

=== Huffman编码压缩工具测试 ===
正在压缩文件: test.txt -> test.huf
字符频率统计:
  'a' 出现    2 次
  'b' 出现    3 次
  'c' 出现    2 次
  'd' 出现    3 次
✓ Huffman树构建成功

小结与练习

本章内容：

文件读取：
- 掌握 std::ifstream 的使用
- 理解二进制模式的重要性
- 学会错误处理
频率统计：
- 使用 std::unordered_map 统计字符频率
- 正确处理特殊字符
- 处理边界情况
Huffman树构建：
- 理解优先队列的应用
- 掌握树构建算法
- 理解时间复杂度 O(n log n)
内存管理：
- 理解内存泄漏的危害
- 掌握后序遍历删除树
- 理解RAII资源管理思想

练习题

练习1：文件读取

编写程序，读取一个文件，统计其中：

总字符数
不同字符数
出现频率最高的字符

练习2：手动构建树

对于频率统计 {a:4, b:2, c:1, d:5, e:3}，手动构建Huffman树，并画出树结构。

练习3：验证编码

根据练习2构建的树，写出每个字符的Huffman编码，并验证：

编码是前缀码
高频字符的编码更短

练习4：内存管理

解释为什么在析构函数中调用 deleteTree 是必要的？如果忘记调用会发生什么？

0.1 Huffman树的数据结构设计

0.3 编码生成与位运算

本节目录