Huffman 编码压缩器 (Rust 实现)

本项目是一个基于命令行的哈夫曼编码压缩/解压工具，使用 Rust 语言实现。它旨在演示数据结构（如优先队列、二叉树）和算法（如哈夫曼编码）在数据压缩领域的实际应用。

简介

哈夫曼编码是一种无损数据压缩算法。其核心思想是为出现频率高的字符分配较短的二进制编码，为出现频率低的字符分配较长的二进制编码，从而使得编码后的整个文件总长度最小，达到压缩的目的。

本项目实现了哈夫曼编码的核心流程，包括：构建哈夫曼树、生成编码、文件压缩、文件解压，并提供了与标准压缩工具 gzip 进行性能对比的功能。

项目结构

.
├── Cargo.toml      # 项目配置文件和依赖项
├── in/             # 存放待压缩的原始文本文件
    ├──test.txt     # 样例文件 size:3.5kb
├── out/            # 存放所有输出文件
│   ├── encoder_file/ # 存放编码后的二进制文件 (*_codeFile)
│   ├── decoder_file/ # 存放解码后的文本文件 (*_decoded.txt)
│   ├── gzip/         # 存放 Gzip 压缩后的文件
│   ├── hfmtree_file/ # 存放哈夫曼树相关文件 (*_hfmTree, *_codes.txt)
│   └── print_file/   # 存放打印输出文件 (*_CodePrint.txt, *_TreePrint.txt)
└── src/
    ├── main.rs       # 主程序入口，负责菜单驱动和用户交互
    ├── huffman.rs    # 哈夫曼算法核心逻辑（建树、编码、解码）
    └── io_utils.rs   # 文件读写和格式化打印的辅助函数

如何运行

1. 环境准备

确保您的系统上已安装以下工具：

• Rust 工具链: 通过 rustup 安装 rustc 和 cargo。
• Gzip: 一个标准的命令行压缩工具 (在 Linux 和 macOS 上通常已预装)。

2. 准备输入文件

将您想要压缩的文本文件（例如 test.txt）放入项目根目录下的 in/ 文件夹中。

3. 启动程序

在项目根目录下打开终端，执行以下命令：

cargo run

程序启动后，您将看到一个交互式菜单。按照菜单提示输入数字选择相应的功能。

---

功能详解与技术栈

下面详细介绍每个菜单选项的功能及其背后所使用的关键技术。

1. Initialize (初始化)

• 功能: 读取指定的文本文件，统计其中每个字符出现的频率，根据频率构建哈夫曼树，并将树（二进制格式）和编码表（文本格式）保存到 out/hfmtree_file/ 目录中。
• 技术栈:
  • 文件读取: std::fs::read_to_string 用于一次性读取整个源文件内容。
  • 频率统计: std::collections::HashMap<char, u32> 用于存储每个字符及其出现的次数。这是构建哈夫曼树的基础。
  • 优先队列 (最小堆): std::collections::BinaryHeap 是构建哈夫曼树的核心数据结构。通过为自定义的 HuffmanNode 实现 Ord trait 并翻转比较逻辑，我们将 Rust 默认的最大堆转变为最小堆，从而确保每次都能取出频率最小的两个节点进行合并。
  • 树形数据结构: 自定义的 enum HuffmanNode (包含 Leaf 和 Internal 两种变体) 用于表示哈夫曼树的节点。
  • 序列化: 使用 serde 和 bincode 这两个第三方库，将内存中的哈夫曼树对象转换成紧凑的二进制格式 (Vec<u8>)，以便高效地存入 _hfmTree 文件。
  • 文件写入: std::fs::File::create 和 writeln! 用于将可读的字符频率和编码报告写入 _codes.txt 文件。

2. Encode File (编码文件)

• 功能: 使用初始化阶段生成的哈夫曼树，将原始文本文件压缩成一个二进制文件 (_codeFile)。
• 技术栈:
  • 反序列化: 使用 bincode::deserialize 从 _hfmTree 文件中读取二进制数据，并将其重建为内存中的 HuffmanNode 树对象。
  • 树的遍历: 通过递归函数 generate_codes 深度优先遍历哈夫曼树，生成从字符到其对应二进制编码（String 类型）的 HashMap。
  • 位操作 (Bit Manipulation): 这是编码过程中最关键的一步。程序将整个文件的哈夫曼编码拼接成一个长长的 "01..." 字符串，然后逐个比特地将其打包成 u8 类型的字节。
    • 使用位移 (<<) 和位或 (|=) 操作将 8 个比特填满一个字节。
    • 处理末尾: 对于最后不足 8 位的比特，进行左移补零（Padding），并在编码文件的最开始处用一个字节记录填充的位数，以便解码时能精确地忽略这些填充位。

3. Decode File (解码文件)

• 功能: 读取编码后的二进制文件 (_codeFile) 和对应的哈夫曼树 (_hfmTree)，将其解码还原成原始文本。
• 技术栈:
  • 读取元数据: 首先读取 _codeFile 的第一个字节，以获知最后一个字节中填充了多少无效位。
  • 逐比特读取: 遍历编码文件的每个字节，并使用位移 (>>) 和位与 (&) 操作，从高位到低位逐一提取出每个比特 (0 或 1)。
  • 树的导航: 从哈夫曼树的根节点开始，根据读取到的每个比特 (0 代表向左子节点移动，1 代表向右子节点移动) 在树上进行导航。
  • 状态维持: 当导航到达一个叶子节点时，就成功解码出了一个字符。然后将导航指针重置回根节点，继续处理下一个比特，直到所有有效比特都被处理完毕。这个过程保证了变长编码可以被无歧义地正确切分。

4. Print Code File (打印编码文件)

• 功能: 将二进制的编码文件 (_codeFile) 以人类可读的 '0' 和 '1' 字符串形式显示在终端，并存入 _CodePrint.txt 文件，每行50个字符以便查看。
• 技术栈:
  • 二进制到文本的转换: 再次利用位操作，将每个字节转换成 8 个 '0' 或 '1' 字符。
  • 字符串处理: 将所有转换后的字符串拼接起来，并根据填充位信息截断末尾多余的 '0'。
  • 格式化输出: 遍历长字符串，通过计数和插入换行符 (\n) 实现每行50个字符的格式。

5. Print Huffman Tree (打印哈夫曼树)

• 功能: 以一种直观的、类似文件目录树的格式，将哈夫曼树的结构打印到终端和 _TreePrint.txt 文件中。
• 技术栈:
  • 递归遍历: 使用深度优先的递归函数遍历树的每个节点。
  • 格式化: 在递归的每一层，通过传递和增加前缀字符串（如 "| " 或 " "）来模拟出树的层级结构，使输出更具可读性。

6. Compare Huffman and Gzip (对比压缩率)

• 功能: 对同一个源文件，分别计算本项目实现的哈夫曼编码和标准的 gzip 工具的压缩后大小，并给出压缩率对比。
• 技术栈:
  • 与操作系统交互: std::process::Command 用于在 Rust 程序内部执行外部命令 gzip。
  • 标准流重定向: 使用 gzip -c 命令将压缩结果输出到标准输出（stdout），程序捕获这个输出流，然后将其写入 out/gzip/ 目录下的指定文件。这避免了在原始 in/ 目录中生成文件。
  • 文件元数据: std::fs::metadata 用于获取文件的大小（以字节为单位）。
  • 浮点数计算: 计算压缩率 (1 - 压缩后大小 / 原始大小) * 100%。