[README] 更新项目概述、算法史故事、新手破冰指南、避坑锦囊等核心内容
学生：熊巧巧 (202521141332) 选题编号：A06 所属分队：红队 指导教师：朱宗晓
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
1952年，David Huffman在MIT攻读博士期间，受Fano的启发发明了哈夫曼编码。这是一种基于字符频率构建最优前缀码的贪心算法，被广泛应用于ZIP、JPEG、MP3等几乎所有现代压缩标准中。而Trie树自1960年由Fredkin发明以来，一直是字符串检索领域的基础数据结构，为快速前缀匹配提供了O(L)时间复杂度的优雅解决方案。
为工业传感器网络设计一套数据压缩与检索系统。利用哈夫曼编码对海量传感器读数进行无损压缩，节省传输带宽与存储空间；利用Trie树构建传感器ID与元数据的快速检索字典，支持在边缘网关设备上实现毫秒级数据定位。
理解在工业物联网（IIoT）环境中，传感器数据的压缩不仅是节省成本的技术手段，更是延长设备续航、降低网络负载的关键策略。培养对边缘计算资源受限环境的深刻认知，以及将经典算法适配于现代工业场景的迁移能力。
如果把工业传感器数据处理比作一座智能仓库的运作：
简而言之：算法库提供的是”压缩与检索理论”，而A06项目要求你实现”工业物联网中的数据瘦身与极速定位”。
你的现状：认为数据就是字节，每个字符都用8个bit表示。
你要做的：理解变长编码的魔力。
统计传感器数据中每个符号（如温度值、状态码）的出现频率。出现频率高的符号用短码（如3bit），出现频率低的符号用长码（如10bit）。
核心挑战：前缀码的唯一可解码性。任何一个编码都不能是另一个编码的前缀，否则解码时会产生歧义。
你的现状：会用结构体和指针，但还没构建过真正的树。
你要做的：理解贪心算法的优雅。
这就是传说中的”最优前缀码”——在所有前缀码中，哈夫曼编码的总编码长度最短。
你的现状：只会用 strcmp() 在数组里线性搜索。
你要做的：用树形结构实现O(L)的定位。
每个传感器ID（如 “SENSOR_001_TEMP”）被拆分为字符序列。从根节点开始，根据每个字符选择对应的分支。
核心优势：查找时间与传感器数量无关，只与ID长度有关！即使有100万个传感器，定位也只需十几步指针跳转。
你的现状：压缩和检索是两个独立的模块。
你要做的：让它们协同工作。
在实现”传感器数据压缩与检索系统”时，初学者极易踩中以下三个雷区：
哈夫曼编码产生的是变长比特序列，不是字节对齐的。在C语言中，你需要手动处理位的打包与解包：
// 打包：将编码的每一位写入输出缓冲区 void write_bit(uint8_t* buffer, int* bit_pos, int bit) { int byte_pos = *bit_pos / 8; int bit_offset = 7 - (*bit_pos % 8); // 大端位序 if (bit) buffer[byte_pos] |= (1 << bit_offset); (*bit_pos)++; }
建议先在纸上画出位布局图，确认每8位组成一个字节的顺序，再写代码。
哈夫曼树和Trie树都是动态分配的树形结构。在释放内存时：
如果传感器ID字典发生变化（新增/删除传感器），必须确保压缩编码表仍然有效。在工业环境中，建议：
. ├── README.md # 本文件（项目总览） ├── Makefile # GCC编译脚本 ├── .gitignore # Git忽略规则 ├── src/ # 源代码目录 │ ├── main.c # 主程序入口 │ ├── algorithm_a.c # 算法A实现 │ ├── algorithm_b.c # 算法B实现 │ ├── utils.c # 工具函数 │ └── include/ # 头文件目录 │ ├── algorithm_a.h │ ├── algorithm_b.h │ └── utils.h ├── docs/ # 文档目录 │ ├── 01-需求分析.md │ ├── 02-算法史故事.md │ ├── 03-功能框图.png │ ├── 04-详细设计.md │ └── 05-测试报告.md ├── report/ # 课程设计报告 │ └── 设计报告模板.md └── test/ # 测试代码 ├── unit_test.c # 单元测试 └── test_data/ # 测试数据集
make # 编译主程序 make test # 编译测试 make clean # 清理
./main ./unit_test
[A-模块] 具体修改内容 示例： [A-哈夫曼树] 实现基于频率统计的最优编码树构建 [A-编码] 实现传感器数据的哈夫曼编码与解码 [A-Trie树] 实现传感器ID字典的插入与查找 [A-前缀匹配] 实现传感器ID前缀匹配检索 [A-统计] 实现压缩率与检索性能对比
源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。
A06 传感器数据的无损压缩与快速检索字典 — 熊巧巧(202521141332) 课程设计仓库。组合算法：哈夫曼树 + Trie。TAOCP出处：卷1 §2.3.4 + §6.3。
版权所有：中国计算机学会技术支持：开源发展技术委员会 京ICP备13000930号-9 京公网安备 11010802032778号
A06 传感器数据的无损压缩与快速检索字典
学生：熊巧巧 (202521141332) 选题编号：A06 所属分队：红队 指导教师：朱宗晓
项目概述
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
算法史故事
1952年，David Huffman在MIT攻读博士期间，受Fano的启发发明了哈夫曼编码。这是一种基于字符频率构建最优前缀码的贪心算法，被广泛应用于ZIP、JPEG、MP3等几乎所有现代压缩标准中。而Trie树自1960年由Fredkin发明以来，一直是字符串检索领域的基础数据结构，为快速前缀匹配提供了O(L)时间复杂度的优雅解决方案。
课程任务
为工业传感器网络设计一套数据压缩与检索系统。利用哈夫曼编码对海量传感器读数进行无损压缩，节省传输带宽与存储空间；利用Trie树构建传感器ID与元数据的快速检索字典，支持在边缘网关设备上实现毫秒级数据定位。
核心要求
工程哲学：可控可观（Controllability-Observability）
工程伦理
理解在工业物联网（IIoT）环境中，传感器数据的压缩不仅是节省成本的技术手段，更是延长设备续航、降低网络负载的关键策略。培养对边缘计算资源受限环境的深刻认知，以及将经典算法适配于现代工业场景的迁移能力。
新手破冰指南：C语言视角的四步上手路径
如果把工业传感器数据处理比作一座智能仓库的运作：
简而言之：算法库提供的是”压缩与检索理论”，而A06项目要求你实现”工业物联网中的数据瘦身与极速定位”。
第一步：建立频率感知的”智能压缩”（打破等长编码黑盒）
你的现状：认为数据就是字节，每个字符都用8个bit表示。
你要做的：理解变长编码的魔力。
统计传感器数据中每个符号（如温度值、状态码）的出现频率。出现频率高的符号用短码（如3bit），出现频率低的符号用长码（如10bit）。
核心挑战：前缀码的唯一可解码性。任何一个编码都不能是另一个编码的前缀，否则解码时会产生歧义。
第二步：构建最优打包方案（实现哈夫曼树）
你的现状：会用结构体和指针，但还没构建过真正的树。
你要做的：理解贪心算法的优雅。
这就是传说中的”最优前缀码”——在所有前缀码中，哈夫曼编码的总编码长度最短。
第三步：打造极速定位字典（实现Trie树）
你的现状：只会用 strcmp() 在数组里线性搜索。
你要做的：用树形结构实现O(L)的定位。
每个传感器ID（如 “SENSOR_001_TEMP”）被拆分为字符序列。从根节点开始，根据每个字符选择对应的分支。
核心优势：查找时间与传感器数量无关，只与ID长度有关！即使有100万个传感器，定位也只需十几步指针跳转。
第四步：压缩与检索的协同优化（闭环）
你的现状：压缩和检索是两个独立的模块。
你要做的：让它们协同工作。
给新手的避坑锦囊
在实现”传感器数据压缩与检索系统”时，初学者极易踩中以下三个雷区：
1. 位操作的噩梦（压缩数据陷阱）
哈夫曼编码产生的是变长比特序列，不是字节对齐的。在C语言中，你需要手动处理位的打包与解包：
建议先在纸上画出位布局图，确认每8位组成一个字节的顺序，再写代码。
2. 树结构的双重释放（内存管理陷阱）
哈夫曼树和Trie树都是动态分配的树形结构。在释放内存时：
3. 字典与压缩表的同步灾难
如果传感器ID字典发生变化（新增/删除传感器），必须确保压缩编码表仍然有效。在工业环境中，建议：
目录结构
快速开始
编译
运行
里程碑
Git提交规范