# Lab 4 Huffman file compression

**Repository Path**: liang-qiaowei/lab-4-huffman-file-compression

## Basic Information

- **Project Name**: Lab 4 Huffman file compression
- **Description**: Lab 4: Huffman file compression
- **Primary Language**: Java
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-10-12
- **Last Updated**: 2025-05-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Lab 4 Huffman file compression
# 基于哈夫曼编码的文件压缩工具

#### 介绍
Lab 4: Huffman file compression
本项目实现了一个基于哈夫曼编码(Huffman Coding)的文件压缩程序，包含完整的压缩/解压缩功能模块,
支持任意类型文件（文本、图像、二进制等）的压缩和解压,
通过统计字符频率构建最优二叉树，实现对文本文件的高效无损压缩。

---

## 功能特性
- **统计文件字节频率**，构建 Huffman 树
- **生成 Huffman 编码表**，将原始数据映射为可变长二进制码
- **压缩**：按位写入压缩文件，并在文件头保存编码表
- **解压**：读取文件头中的编码表，按位解码还原原始字节

## 核心功能  
- **无损压缩**：基于哈夫曼编码算法，确保压缩后文件可完整还原。  
- **跨文件类型支持**：支持文本、图像、HTML、TAR 等任意文件格式。  
- **严格格式规范**：  
  - 压缩文件扩展名为 `.hu`（如 `file.txt` → `file.txt.hu`）。  
  - 文件头包含 Magic number `123456789`，用于校验压缩格式。  
  - 哈夫曼树按规范线性化（`0` 标记叶子节点，`1` 标记内部节点）。  
- **错误处理**：支持检测以下异常：  
  - 非哈夫曼格式文件（魔数错误）。  
  - 哈夫曼树序列化错误。  
  - 文件损坏（比特数不足或截断）。  

---

## 环境依赖  
- **JDK 版本**：Java 8 或更高版本。  
- **依赖项**：仅需标准 Java 库，无第三方依赖。  

---

## 项目结构
### 关键文件说明
#### 用户实现类：
- CompressFile.java：压缩逻辑实现
- UncompressFile.java：解压逻辑实现
- 自定义比特读写类（如 BitInputStream.java, BitOutputStream.java）
#### 提供框架类：
- HuffmanModel.java：模型类（MVC 架构）
- HuffmanView.java：视图类（GUI 界面）
- HuffmanController.java：控制器类（逻辑连接）
- Static.java：常量定义（如Magic number、文件扩展名）
- BitHandling.java：比特操作示例

--- 

### 测试文件
#### 正确性测试：
- words.txt ↔ words.txt.hu
- image.png ↔ image.png.hu

#### 错误测试：
- error-not-in-huffman-format.hu：魔数错误
- error-bad-huffman-tree.hu：哈夫曼树序列化错误
- error-file-corrupted.hu：文件截断错误

### 实现细节
#### 压缩流程
统计频率：遍历文件，统计每个字节的出现次数。
构建哈夫曼树：使用 PriorityQueue 按频率合并节点，生成最优前缀编码树。
序列化树：按 0（叶子）和 1（内部节点）标记线性化哈夫曼树。

#### 写入压缩文件：
魔数 + 序列化树 + 有效比特数 + 编码后的比特流。
末尾补齐 0 至整字节。

#### 解压流程
校验魔数：验证文件是否为合法哈夫曼压缩格式。

#### 反序列化树：根据标记重建哈夫曼树。
解码比特流：逐比特遍历，沿哈夫曼树定位叶子节点还原原始字节。