A20 工业维护日志全文检索系统
项目概述
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
| 维度 | 内容 |
|---|---|
| 组合算法 | 哈希表（Hash Table） + 倒排索引（Inverted Index） |
| TAOCP出处 | 卷3 §6.4 (哈希表) + 卷3 §6.5 (倒排索引) |
| 难度 | ★★★ |
| 支撑目标 | 目标2（综合考虑）、目标3（工具开发） |
| 核心目标 | 将TAOCP中的纯粹数学与指针魔术，转化为工业级系统底盘 |
算法史故事
哈希表自1953年Luhn发明以来一直是无序数据 O(1) 查找的代名词。而Knuth在TAOCP卷3 §6.5中深入讨论了倒排索引技术——将"文档→词项"的正向关系反转，构建"词项→文档列表"的索引结构，这是现代搜索引擎的核心基石。
课程任务
为工厂设备维护部门设计一个日志检索系统。首先用链地址哈希表维护从词项到倒排列表的映射；然后构建完整的倒排索引，支持 AND/OR/NOT 布尔查询。在海量维护记录中实现毫秒级的故障关键词检索。
核心要求
- 实现链地址哈希表（词项 → posting list 的映射）
- 实现文档解析和词项提取（简单的分词/tokenization）
- 实现倒排索引的构建（词项 → 文档ID列表）
- 实现布尔查询处理（AND/OR/NOT 的合并与交集）
- 支持检索结果的相关性排序（词频统计）
工程哲学：可控可观（Controllability-Observability）
- 可控：对每一字节内存走向有绝对掌控力，不允许不可预知的系统崩溃
- 可观：通过打点、日志和统计，让不可见的算法瓶颈变得清晰可见
工程伦理
理解信息检索在设备维护知识管理中的价值，培养将复杂文本数据结构化处理的系统思维。
新手破冰指南：C语言视角的四步上手路径
如果把工业信息检索比作一座现代化图书馆的管理系统：
- 基础数据结构课：教你如何把书按顺序放在书架上，找书时一本本翻（线性查找 O(n)）。
- TAOCP 算法库：是存放着顶级图书管理系统的绝密蓝图。库里的 chained_hash_table.c 是一套"极速图书索引卡系统"（能在毫秒级找到某本书的位置）；而 inverted_index.c 则是一套"倒排目录册"（知道某个关键词出现在哪些书的哪几页）。
- A20 课程设计：要求你作为工厂信息中心的架构师，把"极速索引卡"和"倒排目录册"组合起来，打造一个工业级的日志检索引擎。它不仅要能瞬间定位包含特定故障关键词的维护记录，还要能处理复杂的组合查询（如"电机 AND 过热 NOT 冷却"）。
简而言之：算法库提供的是"查找与索引理论"，而A20项目要求你实现"海量工业文本的实时智能检索"。
第一步：建立词项的"绝对可控性"（打破线性扫描黑盒）
你的现状：习惯了用 strstr() 或 strcmp() 在数组里线性搜索字符串。
你要做的：理解哈希映射的魔力。
定义一个指针数组：PostingList* hash_table[TABLE_SIZE];。这就是你的"索引卡抽屉"。
实现一个简单的哈希函数（比如 djb2 或 FNV-1a）。它能把任何词项（如 “motor_overheat”）瞬间映射为一个整数下标。
核心挑战（拉链法）：如果有两个不同的词项算出了相同的下标怎么办？在每个抽屉里挂一条PostingList链表。每次新词项来，算好下标，直接去那条短链表里找有没有"同名兄弟"。
第二步：反转世界（构建倒排索引）
你的现状：只知道"文档包含哪些词"的正向思维。
你要做的：建立"词项出现在哪些文档中"的反向映射。
定义倒排列表结构体：
typedefstructPostingNode{intdoc_id;// 文档IDintfreq;// 在该文档中出现次数structPostingNode*next;// 下一个posting}PostingNode;解析文档时，对每个词项：
- 用哈希表找到该词项对应的倒排列表
- 如果该文档ID已存在，freq++；否则新增一个PostingNode
这就是 Google、百度背后最核心的技术之一。
第三步：布尔逻辑的组合艺术（实现查询引擎）
你的现状：只会简单的单关键词查找。
你要做的：实现 AND/OR/NOT 的集合运算。
- AND查询：取两个词项倒排列表的交集。遍历较短的列表，对每个doc_id在另一个列表中查找是否存在。
- OR查询：取两个词项倒排列表的并集。合并两个列表，去除重复doc_id。
- NOT查询：从基础集合中排除某词项的文档列表。
核心优化：总是先处理最短的列表。对于 AND 查询，从文档数最少的词项开始，逐步缩小结果集。
第四步：相关性排序与系统可观性（闭环）
你的现状：检索结果随意排列，不关心哪些更相关。
你要做的：实现 TF（词频）排序。
计算每个结果文档的得分：
score=Σ(查询词项在该文档中的freq/该文档总词数)按得分降序排列，最相关的维护记录排在最前面。
同时，建立系统仪表盘：
- 记录索引构建时间
- 记录平均查询响应时间
- 记录哈希表负载因子与冲突率
- 记录每次布尔查询涉及的文档扫描数量
给新手的避坑锦囊
在实现"工业日志检索系统"时，初学者极易踩中以下三个雷区：
1. 分词的陷阱（字符串处理噩梦）
C语言没有内置的字符串分割函数。在处理原始日志文本时：
- 必须小心处理标点符号（逗号、句号、冒号等）
- 必须统一大小写（建议全部转为小写，实现大小写不敏感检索）
- 必须过滤停用词（“的”、“了”、"是"等无意义词项）
建议先实现一个最简版 tokenizer：用 strtok() 按空格和标点分割，后续再优化。
2. 列表合并的指针灾难（AND/OR实现陷阱）
在实现布尔查询时，绝对不要试图"原地修改"原始倒排列表来求交集/并集。必须创建新的结果列表，否则会破坏索引结构，导致后续查询出错。
正确做法：每个查询都 malloc 新的结果列表，查询结束后 free。
3. 哈希表与倒排列表的内存失控
在工业环境中，日志数据可能极其庞大。如果没有监控机制，你的程序可能在不知不觉中耗尽内存。
建立可观性机制：
voidprint_memory_stats(){printf("哈希表条目数: %d\n",hash_entry_count);printf("总posting节点数: %d\n",total_posting_nodes);printf("索引内存占用: %zu bytes\n",hash_entry_count*sizeof(HashNode)+total_posting_nodes*sizeof(PostingNode));}目录结构
. ├── 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# 编译主程序maketest# 编译测试makeclean# 清理运行
./main ./unit_test里程碑
| 里程碑 | 截止时间 | 状态 |
|---|---|---|
| v0.1-方案确定 | 5月18日 | ⏳ 待开始 |
| v0.2-详细设计 | 6月21日 | ⏳ 待开始 |
| v0.3-编码完成 | 7月5日 | ⏳ 待开始 |
| v0.4-验收演示 | 7月10日 | ⏳ 待开始 |
| v1.0-最终提交 | 7月12日 | ⏳ 待开始 |
Git提交规范
[A-模块] 具体修改内容 示例： [A-哈希表] 实现链地址哈希表与词项映射 [A-分词] 实现日志文本的tokenization [A-倒排索引] 构建词项到文档列表的反向索引 [A-布尔查询] 实现AND/OR/NOT组合查询 [A-排序] 实现基于TF的相关性排序源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。
