https://github.com/nhaok169/huffman-compressor.git
一、设计思路
1、目标:
实现基于标准 ASCII (0–127) 的哈夫曼压缩、解压与在压缩文件中按原始字符串查找功能。
2、总体流程:
"encoder"：读取文本文件，统计字符频率，构建哈夫曼树，生成每个字符的变长码，写出自定义二进制格式（文件头 "HUFF" + 原始字节数 + 字符表 + 压缩数据），并输出压缩比信息。
"decoder"：读取二进制格式，重建哈夫曼解码树（从字符表），按位读取压缩数据，遍历树恢复原字节，写回解压后的文本文件。
"finder"：在压缩文件中读取字符表并用其生成目标字符串对应的比特序列，然后在压缩比特流上做位级搜索（使用滑动窗口与类似 BoyerMoore 的部分跳跃优化），并通过遍历哈夫曼树统计并报告匹配出现的位置（以原字符序号计）。
3、项目文件（快速索引）
main.cpp：程序入口与参数解析。
encoder.h / encoder.cpp：压缩器声明与实现。
decoder.h / decoder.cpp：解压器声明与实现（含树结点创建/销毁、按位拆分函数）。
finder.h / finder.cpp：在压缩文件中查找原始字符串功能。
common.h：通用声明（"split" 函数原型）。
哈夫曼压缩工具设计报告
4、文件格式设计
定义了专用的压缩文件格式，确保压缩数据的完整性和可识别性：
[4字节] 魔数: "HUFF" (0x48554646)
[4字节] 原始文件大小
[1字节] 字符种类数 N
[编码表] N个条目，每个包含：
[1字节] 字符
[1字节] 编码长度(bits)
[X字节] 编码数据((len+7)/8字节，高位对齐)
[压缩数据] 哈夫曼编码的bits流
二、代码说明
2.1 数据结构定义
2.1.1 哈夫曼树节点（encoder.h）
typedef struct htnode {
unsigned long weight; // 字符频次（权值）
int par; // 父节点索引
int lc, rc; // 左右孩子节点索引
} htnode;
2.1.2 编码信息结构（encoder.h）
typedef struct huffcode {
unsigned char src; // 源字符
unsigned char len; // 编码长度（位）
unsigned char bits[16]; // 编码数据（最大支持127位编码）
} huffcode;
2.1.3 解码树节点（decoder.h）
typedef struct denode {
unsigned char ch; // 叶子节点存储的字符
struct denode* left; // 左孩子指针（编码位0）
struct denode* right; // 右孩子指针（编码位1）
} denode, deptr;
2.1.4 查找模块编码节点（finder.h）
typedef struct {
unsigned char len; // 编码长度
unsigned char *code; // 编码位数组
}node, *codeptr;
2.2 核心函数说明
2.2.1 压缩模块（encoder.c）
主函数：encoder
int encoder(char *inputf, char *outputf);
功能：实现完整的哈夫曼编码压缩流程
流程：
- 统计字符频次
- 构建哈夫曼树
- 生成编码表
- 写入文件头
- 压缩数据写入
- 计算压缩率
辅助函数：tobyte
unsigned char tobyte(unsigned char* src, int len);
功能：将位数组转换为字节
参数：src-位数组指针，len-位数组长度
返回值：转换后的字节
说明函数：prompt2
void prompt2();
功能：显示压缩程序的使用说明和文件格式
2.2.2 解压模块（decoder.c）
主函数：decoder
int decoder(char *inputf, char *outputf);
功能：解压哈夫曼压缩文件
流程：
- 验证文件格式
- 读取编码表
- 重建哈夫曼解码树
- 解码数据
- 写入输出文件
树操作函数：
deptr createnode(); // 创建新节点
void destroy(deptr root); // 销毁解码树
void split(unsigned char ch, unsigned char *tem, int chlen);
// 字节拆分
说明函数：prompt
void prompt();
功能：显示解压程序的使用说明
2.2.3 查找模块（finder.c）
主函数：finder
int finder(char *inputf, char *seekword);
功能：在压缩文件中直接查找字符串
特点：
- 无需完全解压文件
- 使用滑动窗口技术
- 应用Sunday算法优化匹配
- 核心算法：
- 构建查找字符串的位模式
- 预计算跳转表（坏字符和好后缀规则）
- 滑动窗口匹配
- 实时解码定位
说明函数：prompt3
void prompt3();
功能：显示查找程序的使用说明
2.2.4 主程序（main.c）
主函数：main
int main(int argc, char *argv[]);
功能：命令行接口和功能分发
支持模式：
- -e：压缩模式
- -d：解压模式
- -f：查找模式
- 帮助函数：print_usage
- void print_usage(const char *prog_name);
- 功能：显示程序使用帮助
2.3 关键技术点
2.3.1 压缩优化
- 小文件处理：特殊处理单字符文件
- 内存管理：静态数组和动态分配结合
- 边界检查：严格检查字符范围(0-127)
2.3.2 查找优化
- 窗口技术：MAXR=100000定义滑动窗口大小
- 跳表预计算：减少不必要的匹配尝试
- 增量解码：仅解码必要部分
2.3.3 错误处理
- 文件打开失败检测
- 格式验证（魔数检查）
- 内存分配失败处理
- 无效字符范围检查
2.4 性能特点
- 时间复杂度：
- 压缩：O(n log m)，n为字符数，m为字符种类
- 解压：O(n)
- 查找：O(n + m)，n为文件大小，m为模式长度
- 空间复杂度：
- 压缩：O(1)额外空间（固定大小数组）
- 查找：O(k)窗口空间，k为窗口大小
- 压缩率：
- 对文本文件有较好的压缩效果
- 小文件可能因编码表开销导致负压缩
三、分析
1. 查询错误的可能性与效率关系分析
1.1 错误可能性分析
当查询字符串的哈夫曼编码较短时，可能存在"伪匹配"问题。
风险场景示例：
假设：
- 字符'A'的编码：01（2位）
- 字符'B'的编码：10（2位）
- 查询字符串："AB"的编码：0110
伪匹配风险：
原始文本是"XY"，其中：
- 'X'的编码末尾位为：...01
- 'Y'的编码开头位为：...10
- 实际比特流：...01 10...
虽然编码边界在01和10之间，但在比特流层面，连续的0110会被误识别为"AB"。
错误概率计算：
- 假设字符集大小：m
- 平均编码长度：L bits
- 查询字符串长度：k 字符
- 查询编码总长：K bits
伪匹配概率 ≈ P ≈ (1/2)^(K-1) × (字符边界对齐概率)
1.2 效率关系
- 查询字符串长度与效率的权衡：
查询长度 | 错误风险 | 匹配效率 | 内存开销 | 优化策略 |
过短（1-2字符） | 高风险（伪匹配多） | 高（候选多） | 低 | 增加验证步骤 |
中等（3-10字符） | 中等风险 | 中等 | 中等 | 平衡策略 |
较长（>10字符） | 低风险 | 低（候选少） | 高 | 预计算跳表 |
2. 压缩率优化分析
2.1 当前压缩率损失分析
主要损失点：编码表存储开销
// 每个字符存储：
// 1字节字符 + 1字节长度 + ceil(len/8)字节编码
// 对于短编码，存储开销可能大于压缩收益
小文件编码表占比过大
小文件压缩示例（50字符）：
- 编码表：假设20个字符 × 平均3字节 = 60字节
- 数据压缩后：50字符 × 平均3位 = 约19字节
- 总大小：79字节 > 原始50字节（负压缩）
2.2 提高压缩率的具体方法
方法1：编码表也按位紧密排列（如你所提）
压缩率提升估计：
- 减少填充位：每个文件末尾最多节省7位
- 对小文件更显著：相对占比更高
方法2：动态块压缩
思路：
- 将大文件分成块（如64KB）
- 每块独立统计频率、生成编码
- 编码表只需存储差异部分
优点：
- 适应局部统计特性
- 减少编码表存储
四、使用限制
- 字符范围：仅支持标准ASCII字符（0-127）
- 文件大小：支持最大4GB文件
- 编码长度：单个字符编码最长127位
- 内存要求：查找功能需要较大的窗口内存
五、扩展性
- 支持UTF-8编码
- 添加多线程压缩/解压
- 支持目录批量处理
- 添加进度显示
- 支持更多压缩参数调整
