哈夫曼压缩与关键字检索

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);

功能：实现完整的哈夫曼编码压缩流程

流程：

1. 统计字符频次
2. 构建哈夫曼树
3. 生成编码表
4. 写入文件头
5. 压缩数据写入
6. 计算压缩率

辅助函数：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);

功能：解压哈夫曼压缩文件

流程：

1. 验证文件格式
2. 读取编码表
3. 重建哈夫曼解码树
4. 解码数据
5. 写入输出文件

树操作函数：

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算法优化匹配
• 核心算法：

1. 构建查找字符串的位模式
2. 预计算跳转表（坏字符和好后缀规则）
3. 滑动窗口匹配
4. 实时解码定位

说明函数：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 性能特点

1. 时间复杂度：
   • 压缩：O(n log m)，n为字符数，m为字符种类
   • 解压：O(n)
   • 查找：O(n + m)，n为文件大小，m为模式长度
2. 空间复杂度：
   • 压缩：O(1)额外空间（固定大小数组）
   • 查找：O(k)窗口空间，k为窗口大小
3. 压缩率：
   • 对文本文件有较好的压缩效果
   • 小文件可能因编码表开销导致负压缩

三、分析

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 效率关系

• 查询字符串长度与效率的权衡：

2. 压缩率优化分析

2.1 当前压缩率损失分析

主要损失点：编码表存储开销

// 每个字符存储：

// 1字节字符 + 1字节长度 + ceil(len/8)字节编码

// 对于短编码，存储开销可能大于压缩收益

小文件编码表占比过大

小文件压缩示例（50字符）：

- 编码表：假设20个字符 × 平均3字节 = 60字节

- 数据压缩后：50字符 × 平均3位 = 约19字节

- 总大小：79字节 > 原始50字节（负压缩）

2.2 提高压缩率的具体方法

方法1：编码表也按位紧密排列（如你所提）

压缩率提升估计：

- 减少填充位：每个文件末尾最多节省7位

- 对小文件更显著：相对占比更高

方法2：动态块压缩

思路：

- 将大文件分成块（如64KB）

- 每块独立统计频率、生成编码

- 编码表只需存储差异部分

优点：

- 适应局部统计特性

- 减少编码表存储

四、使用限制

1. 字符范围：仅支持标准ASCII字符（0-127）
2. 文件大小：支持最大4GB文件
3. 编码长度：单个字符编码最长127位
4. 内存要求：查找功能需要较大的窗口内存

五、扩展性

1. 支持UTF-8编码
2. 添加多线程压缩/解压
3. 支持目录批量处理
4. 添加进度显示
5. 支持更多压缩参数调整