章节目录

完整压缩与解压流程

本节阅读量:

压缩函数完整实现

完整流程图

开始
  ↓
打开输入文件
  ↓
统计字符频率
  ↓
构建Huffman树
  ↓
生成编码表
  ↓
重新读取文件并编码
  ↓
计算Padding
  ↓
写入原始大小
  ↓
写入Huffman树
  ↓
写入Padding
  ↓
写入压缩数据
  ↓
关闭文件
  ↓
计算压缩率
  ↓
结束

代码详解

  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
104
105
106
107
108
109
110

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;
    }
    
    // 构建哈夫曼树并生成编码
    buildTree(freq);
    generateCodes(root, "");
    
    // 打印编码表
    std::cout << "哈夫曼编码表:" << std::endl;
    std::cout << std::left << std::setw(12) << "字符" << "编码" << std::endl;
    std::cout << std::string(30, '-') << std::endl;
    
    for (auto const& pair : huffmanCode) {
        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 << std::left << std::setw(12) << displayChar << pair.second << std::endl;
    }
    
    // 重新读取文件进行编码
    inFile.open(inputFile, std::ios::binary);
    std::string encodedString;
    while (inFile.get(ch)) {
        encodedString += huffmanCode[ch];
    }
    inFile.close();
    
    // 写入压缩文件
    std::ofstream outFile(outputFile, std::ios::binary);
    if (!outFile) {
        std::cerr << "无法创建输出文件: " << outputFile << std::endl;
        return false;
    }
    
    // 写入原始文件大小（字符数）
    size_t originalSize = encodedString.length();
    outFile.write(reinterpret_cast<const char*>(&originalSize), sizeof(size_t));
    
    // 写入哈夫曼树
    writeTree(outFile, root);
    
    // 计算padding
    int padding = (8 - (encodedString.length() % 8)) % 8;
    outFile.put(static_cast<char>(padding));
    
    // 转换编码字符串为字节
    std::vector<unsigned char> bytes;
    stringToBytes(encodedString, bytes);
    
    // 写入压缩数据
    outFile.write(reinterpret_cast<const char*>(bytes.data()), bytes.size());
    outFile.close();
    
    // 计算压缩率
    std::ifstream inCheck(inputFile, std::ios::binary | std::ios::ate);
    size_t inputSize = inCheck.tellg();
    inCheck.close();
    
    std::ifstream outCheck(outputFile, std::ios::binary | std::ios::ate);
    size_t outputSize = outCheck.tellg();
    outCheck.close();
    
    double ratio = (1.0 - static_cast<double>(outputSize) / inputSize) * 100.0;
    
    std::cout << "压缩完成!" << std::endl;
    std::cout << "原始大小: " << inputSize << " 字节" << std::endl;
    std::cout << "压缩后大小: " << outputSize << " 字节" << std::endl;
    std::cout << "压缩率: " << std::fixed << std::setprecision(2) << ratio << "%" << std::endl;
    
    return true;
}

关键步骤说明

步骤2：统计字符频率

为什么需要两次读取文件？

  • 第一次：统计字符频率，构建Huffman树
  • 第二次：根据编码表进行编码

优化思路：可以一次性读取整个文件到内存，但会占用更多内存。

步骤7：写入原始大小

1

size_t originalSize = encodedString.length();

这里保存的是编码后的二进制位数，不是原始字符数！

步骤9：Padding计算

1

int padding = (8 - (encodedString.length() % 8)) % 8;

示例：

  • 编码长度14位：14 % 8 = 6，padding = 8 - 6 = 2
  • 编码长度16位：16 % 8 = 0，padding = 0

解压函数完整实现

完整流程图

开始
  ↓
打开压缩文件
  ↓
读取原始大小（位数）
  ↓
读取Huffman树
  ↓
读取Padding
  ↓
读取压缩数据
  ↓
将字节转换为二进制字符串
  ↓
遍历树解码
  ↓
输出到文件
  ↓
关闭文件
  ↓
结束

代码详解

 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

bool HuffmanCoder::decompress(const std::string& inputFile, const std::string& outputFile) {
    // 读取压缩文件
    std::ifstream inFile(inputFile, std::ios::binary);
    if (!inFile) {
        std::cerr << "无法打开输入文件: " << inputFile << std::endl;
        return false;
    }
    
    // 读取原始文件大小
    size_t originalSize;
    inFile.read(reinterpret_cast<char*>(&originalSize), sizeof(size_t));
    
    // 读取哈夫曼树
    root = readTree(inFile);
    
    // 读取padding
    int padding = inFile.get();
    
    // 读取压缩数据
    std::vector<unsigned char> bytes((std::istreambuf_iterator<char>(inFile)), 
                                     std::istreambuf_iterator<char>());
    inFile.close();
    
    // 将字节转换为二进制字符串
    std::string binaryString;
    bytesToString(bytes, binaryString, padding);
    
    // 解码
    std::ofstream outFile(outputFile, std::ios::binary);
    if (!outFile) {
        std::cerr << "无法创建输出文件: " << outputFile << std::endl;
        return false;
    }
    
    HuffmanNode* current = root;
    int decodedCount = 0;
    
    for (char bit : binaryString) {
        if (bit == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        
        // 到达叶子节点
        if (!current->left && !current->right) {
            outFile.put(current->data);
            current = root;
            decodedCount++;
            
            // 如果已经解码了原始大小的字符，停止
            if (decodedCount >= originalSize) {
                break;
            }
        }
    }
    
    outFile.close();
    std::cout << "解压完成! 输出文件: " << outputFile << std::endl;
    
    return true;
}

关键算法：树遍历解码

这是解压的核心算法，也是最复杂的部分！

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

HuffmanNode* current = root;
int decodedCount = 0;

for (char bit : binaryString) {
    // 根据bit走向左或右子树
    if (bit == '0') {
        current = current->left;
    } else {
        current = current->right;
    }
    
    // 到达叶子节点，输出字符
    if (!current->left && !current->right) {
        outFile.put(current->data);
        current = root;  // 重新从根节点开始
        decodedCount++;
        
        // 防止解码padding的无效数据
        if (decodedCount >= originalSize) {
            break;
        }
    }
}

手动追踪解码过程

假设编码表：

a: 0
b: 10
c: 11

编码后的二进制串：01010011

解码过程：

初始化：current = root, decodedCount = 0

第1位 '0':
  current = current->left
  current 是叶子节点 → 输出 'a'
  current = root
  decodedCount = 1

第2位 '1':
  current = current->right
  current 不是叶子节点

第3位 '0':
  current = current->left
  current 是叶子节点 → 输出 'b'
  current = root
  decodedCount = 2

第4位 '1':
  current = current->right
  current 不是叶子节点

第5位 '0':
  current = current->left
  current 是叶子节点 → 输出 'b'
  current = root
  decodedCount = 3

第6位 '0':
  current = current->left
  current 是叶子节点 → 输出 'a'
  current = root
  decodedCount = 4

第7位 '1':
  current = current->right
  current 不是叶子节点

第8位 '1':
  current = current->right
  current 是叶子节点 → 输出 'c'
  current = root
  decodedCount = 5

解码完成，输出："abbac"

压缩率计算

压缩率定义

压缩率 = (1 - 压缩后大小 / 原始大小) × 100%

含义：

  • 正值：压缩后文件变小（压缩成功）
  • 负值：压缩后文件变大（压缩失败）
  • 零值：文件大小不变

代码实现

1
2
3
4
5
6
7
8
9

std::ifstream inCheck(inputFile, std::ios::binary | std::ios::ate);
size_t inputSize = inCheck.tellg();
inCheck.close();

std::ifstream outCheck(outputFile, std::ios::binary | std::ios::ate);
size_t outputSize = outCheck.tellg();
outCheck.close();

double ratio = (1.0 - static_cast<double>(outputSize) / inputSize) * 100.0;

说明：

  • std::ios::ate：打开文件时定位到文件末尾
  • tellg()：返回当前文件指针位置（即文件大小）

为什么小文件可能变大？

原因分析：

假设有一个100字节的文件，包含100个不同字符：

  • 原始大小：100字节
  • Huffman树大小：约767字节（256个节点）
  • 压缩数据：至少100字节
  • 总大小：约867字节
  • 压缩率：(1 - 867/100) × 100% = -767%

结论：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
27
28
29
30
31
32

int main(int argc, char* argv[]) {
    if (argc != 4) {
        printUsage(argv[0]);
        return 1;
    }
    
    std::string mode = argv[1];
    std::string inputFile = argv[2];
    std::string outputFile = argv[3];
    
    HuffmanCoder huffman;
    
    if (mode == "-c" || mode == "--compress") {
        std::cout << "正在压缩文件: " << inputFile << " -> " << outputFile << std::endl;
        if (!huffman.compress(inputFile, outputFile)) {
            std::cerr << "压缩失败!" << std::endl;
            return 1;
        }
    } else if (mode == "-d" || mode == "--decompress") {
        std::cout << "正在解压文件: " << inputFile << " -> " << outputFile << std::endl;
        if (!huffman.decompress(inputFile, outputFile)) {
            std::cerr << "解压失败!" << std::endl;
            return 1;
        }
    } else {
        std::cerr << "无效的模式: " << mode << std::endl;
        printUsage(argv[0]);
        return 1;
    }
    
    return 0;
}

帮助信息

1
2
3
4
5
6
7
8
9

void printUsage(const char* programName) {
    std::cout << "Huffman文件压缩工具\n";
    std::cout << "用法:\n";
    std::cout << "  压缩: " << programName << " -c <输入文件> <输出文件>\n";
    std::cout << "  解压: " << programName << " -d <输入文件> <输出文件>\n";
    std::cout << "\n示例:\n";
    std::cout << "  " << programName << " -c input.txt compressed.huf\n";
    std::cout << "  " << programName << " -d compressed.huf decompressed.txt\n";
}

完整测试

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

# 创建测试文件
echo "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" > test.txt
echo "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" >> test.txt
echo "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc" >> test.txt

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

# 解压
./huffman -d test.huf output.txt

# 验证
diff test.txt output.txt && echo "✓ 文件内容一致！" || echo "✗ 文件内容不一致！"

小结与练习

本章总结：

  1. 压缩流程：

    • 理解完整的压缩流程
    • 掌握每个步骤的作用
    • 能够独立实现压缩功能

  2. 解压流程：

    • 理解完整的解压流程
    • 掌握树遍历解码算法
    • 能够独立实现解压功能

  3. 压缩率：

    • 理解压缩率的计算
    • 知道为什么小文件可能变大
    • 理解Huffman编码的适用场景

练习1：手动解码

给定编码表：

a: 0
b: 10
c: 110
d: 111

手动解码二进制串：010100111110

练习2：压缩率计算

原始文件1000字节，压缩后800字节，计算压缩率。

练习3：优化思考

如何优化压缩流程，使其只需要读取一次文件？

练习4：错误处理

如果压缩文件损坏（如Huffman树部分缺失），解压时会发生什么？如何增加错误检测？

练习5：更近一步的优化

现在的算法，最好的情况下，用一个bit来表示一个字节，也就是说极限是7/8的压缩率。有没有办法进一步优化？

0.4 树的序列化与反序列化

上一节

练手项目

下一节
本节目录