上一篇【第09篇】工欲善其事开发环境与单元测试下一篇【第11篇】构建索引一倒排索引的第一块砖摘要前面九篇把认知和基本功铺好了。从下一篇起我们要真写一个能跑的迷你检索引擎。动手前最关键的一步是先把规格定清楚要支持哪些查询、模块怎么划、用什么语言和存储、分几步推进。想清楚这些才不至于写着写着就迷失在细节里。本文就是这份施工图纸。一、先想清楚我们要造什么、不造什么目标说人话就是一个能在本地对一批中文/英文文档建索引、并且能用关键词查出来的命令行小引擎。它不追求性能、不追求完备但核心零件一个不少。明确不造什么同样重要免得贪大不造分布式。单机内存版分布式留给后面的 Solr/ES 讲。不造复杂的检索模型。先上最朴素的 TF 打分BM25 后面再升级。不造花哨界面。命令行输入输出即可UI 单独成篇。不造实时更新。批量建一次索引反复查。【我们造的 vs 不造的】 造: 单机 / 倒排 / 中文分词 / 布尔查询 / TF打分 / 落盘 不造: 分布式 / 复杂模型 / 界面 / 实时更新 / 高并发把边界画出来心里就踏实了。工业引擎动辄几百万行我们这版估计几千行但骨架是相通的。二、功能边界支持哪些查询第一版引擎先支持这几类查询够用且能体现原理单词查询。给一个词返回包含它的所有文档按相关性排序。布尔 AND。多个词都要命中求交集这是倒排链求交的经典场景。短语查询进阶。多个词不仅都要命中还得连续相邻靠位置信息实现。模糊/纠错彩蛋。容忍拼写错误用编辑距离后面专门一篇做。排序先用 TF 加权简单有效。等我们钻进 Lucene 再换成 BM25。查询语言先用空格分词不做复杂的语法解析先让主干跑通。【支持的查询类型按里程碑】 里程碑1: 单词查询 布尔AND 里程碑2: 短语查询用位置信息 里程碑3: 模糊纠错编辑距离FSM三、架构草图模块怎么划按职责把引擎切成几块和前面讲的五脏六腑呼应analyze分词把文本切成词项。中文用空格模拟或简单分词英文按非字母切。index索引维护词典和倒排表负责构建和落盘、读取。search检索接收查询、查倒排、求交、打分、排序。model模型文档、词项、倒排项这些数据结构。【模块划分】 输入文档 │ ▼ analyze ──▶ 词项流 │ ▼ index ──▶ 词典 倒排(内存/落盘) │ ▼ search ──▶ 查询 → 查倒排 → 求交 → 打分排序 → 结果这四个模块边界清晰后面每篇就专攻其中一个代码也好测试。四、技术选型语言与存储语言用 Java理由前面说过生态契合、读者读源码顺手。存储上第一版倒排先放内存HashMap 存词典value 是文档 ID 列表。等讲生成索引文件那篇再把它序列化到磁盘用前面提过的变长编码省空间。正排文档详情也先用内存 Map 存。【存储演进路线】 阶段A: 全部内存(HashMap List) ← 最快跑通 阶段B: 倒排落盘(二进制 变长编码) ← 讲索引文件格式时做 阶段C: 按需读取(内存映射/流读) ← 讲读取时做之所以先内存后落盘是因为先让主干正确再优化存储。过早优化存储会让你淹没在字节细节里忘了真正要学的原理。五、里程碑分几步走把建造过程切成几个可验证的里程碑每到一个就跑一次测试【建造里程碑】 M1 能建内存倒排并查单词 → 验证词→文档打通 M2 支持布尔AND(多词求交) → 验证集合运算 M3 倒排落盘 读回一致 → 验证序列化 M4 短语查询(位置信息) → 验证位置字段 M5 模糊纠错(编辑距离) → 验证FSM M6 端到端跑通一个小语料 → 验证整体每一步都能独立验证出错了也容易定位。这也是为什么前面要先把单元测试环境搭好它们就是给这些里程碑把关的。六、先给引擎喂一份样数据光有架构图还是飘给一份具体的样例你就知道每段代码要处理什么。假设我们的文档长这样Doc(1, 无线耳机 降噪 蓝牙) Doc(2, 有线耳机 便宜) Doc(3, 无线鼠标 安静) Doc(4, 耳机 降噪 好玩)经过 analyze 分词、index 构建倒排表会变成无线 → [(1,pos0), (3,pos0)] 耳机 → [(1,pos1), (2,pos1), (4,pos1)] 降噪 → [(1,pos2), (4,pos2)] 蓝牙 → [(1,pos3)] 有线 → [(2,pos0)] 便宜 → [(2,pos2)] 鼠标 → [(3,pos1)] 安静 → [(3,pos2)] 好玩 → [(4,pos3)]现在你搜无线 耳机取两条倒排链求交集得到文档1既含无线又含耳机而文档3只含无线、文档2和4只含耳机都被排除。这就是倒排求交的第一现场。正排则存 Doc 的完整内容查询拿到文档1后从正排取标题和正文返回。位置信息pos暂时用不上等我们做短语查询无线耳机连续出现时它就要出场了。【里程碑 ↔ 测试用例 对应】 M1 建内存倒排查单词 测: 查耳机→[1,2,4] M2 布尔AND求交 测: 无线 耳机→[1] M3 倒排落盘读回 测: 写文件再读, 倒排一致 M4 短语查询 测: 无线耳机短语→只命中连续出现 M5 模糊纠错 测: 无限耳机→纠正为无线耳机 M6 端到端 测: 上面4篇语料跑通整条链路这份样数据我们后面会一直用每到一个里程碑就往里加刁钻用例。把测试数据和里程碑绑死进度看得见、正确性也兜得住。下一篇正式砌第一块砖构建倒排索引。七、技术选型再确认为什么不直接用现成库最后解释一个你可能有的疑问Java 生态里 Lucene 现成的倒排、分词、打分都有为什么我们还要从零写一套玩具版答案就一句用现成库你永远只是在配置不是在理解。Lucene 把倒排、段、FST、DocValues 全封装好了你调 API 能跑但那些设计为什么是这样你看不到、也改不动。我们手写一遍正是为了把这些封装背后的为什么亲手验证一遍。等第二段落幕你再回头用 Lucene就是站在理解之上使用而不是对着黑盒祈祷。当然真做业务肯定用 Lucene/Solr/ES没人会拿玩具引擎上线。本系列前半段的手写是学费后半段钻 Lucene、上 SolrCloud 和 ES才是生产力。手写的玩具和工业引擎骨架是相通的区别只在工程完备度和性能。【手写玩具 vs 工业引擎】 手写玩具: 懂原理、能改、跑得动小数据 ← 前半段目标 工业引擎: 高性能、高可用、功能全 ← 后半段目标 两者骨架: 倒排 / 求交 / 打分 / 分词 一模一样所以别嫌手写麻烦那是绕不过去的一课。下一篇正式砌第一块砖构建倒排索引。本篇小结动手前定规格我们要造一个单机、内存起步、支持单词查询和布尔 AND后续加短语和纠错的迷你检索引擎用 Java 写按 analyze/index/search/model 四模块划分存储先内存后落盘。建造分 M1 到 M6 六个里程碑每步可测可验证。这份图纸定了下一篇就正式砌第一块砖构建倒排索引。上一篇【第09篇】工欲善其事开发环境与单元测试下一篇【第11篇】构建索引一倒排索引的第一块砖
上一篇【第09篇】工欲善其事开发环境与单元测试下一篇【第11篇】构建索引一倒排索引的第一块砖摘要前面九篇把认知和基本功铺好了。从下一篇起我们要真写一个能跑的迷你检索引擎。动手前最关键的一步是先把规格定清楚要支持哪些查询、模块怎么划、用什么语言和存储、分几步推进。想清楚这些才不至于写着写着就迷失在细节里。本文就是这份施工图纸。一、先想清楚我们要造什么、不造什么目标说人话就是一个能在本地对一批中文/英文文档建索引、并且能用关键词查出来的命令行小引擎。它不追求性能、不追求完备但核心零件一个不少。明确不造什么同样重要免得贪大不造分布式。单机内存版分布式留给后面的 Solr/ES 讲。不造复杂的检索模型。先上最朴素的 TF 打分BM25 后面再升级。不造花哨界面。命令行输入输出即可UI 单独成篇。不造实时更新。批量建一次索引反复查。【我们造的 vs 不造的】 造: 单机 / 倒排 / 中文分词 / 布尔查询 / TF打分 / 落盘 不造: 分布式 / 复杂模型 / 界面 / 实时更新 / 高并发把边界画出来心里就踏实了。工业引擎动辄几百万行我们这版估计几千行但骨架是相通的。二、功能边界支持哪些查询第一版引擎先支持这几类查询够用且能体现原理单词查询。给一个词返回包含它的所有文档按相关性排序。布尔 AND。多个词都要命中求交集这是倒排链求交的经典场景。短语查询进阶。多个词不仅都要命中还得连续相邻靠位置信息实现。模糊/纠错彩蛋。容忍拼写错误用编辑距离后面专门一篇做。排序先用 TF 加权简单有效。等我们钻进 Lucene 再换成 BM25。查询语言先用空格分词不做复杂的语法解析先让主干跑通。【支持的查询类型按里程碑】 里程碑1: 单词查询 布尔AND 里程碑2: 短语查询用位置信息 里程碑3: 模糊纠错编辑距离FSM三、架构草图模块怎么划按职责把引擎切成几块和前面讲的五脏六腑呼应analyze分词把文本切成词项。中文用空格模拟或简单分词英文按非字母切。index索引维护词典和倒排表负责构建和落盘、读取。search检索接收查询、查倒排、求交、打分、排序。model模型文档、词项、倒排项这些数据结构。【模块划分】 输入文档 │ ▼ analyze ──▶ 词项流 │ ▼ index ──▶ 词典 倒排(内存/落盘) │ ▼ search ──▶ 查询 → 查倒排 → 求交 → 打分排序 → 结果这四个模块边界清晰后面每篇就专攻其中一个代码也好测试。四、技术选型语言与存储语言用 Java理由前面说过生态契合、读者读源码顺手。存储上第一版倒排先放内存HashMap 存词典value 是文档 ID 列表。等讲生成索引文件那篇再把它序列化到磁盘用前面提过的变长编码省空间。正排文档详情也先用内存 Map 存。【存储演进路线】 阶段A: 全部内存(HashMap List) ← 最快跑通 阶段B: 倒排落盘(二进制 变长编码) ← 讲索引文件格式时做 阶段C: 按需读取(内存映射/流读) ← 讲读取时做之所以先内存后落盘是因为先让主干正确再优化存储。过早优化存储会让你淹没在字节细节里忘了真正要学的原理。五、里程碑分几步走把建造过程切成几个可验证的里程碑每到一个就跑一次测试【建造里程碑】 M1 能建内存倒排并查单词 → 验证词→文档打通 M2 支持布尔AND(多词求交) → 验证集合运算 M3 倒排落盘 读回一致 → 验证序列化 M4 短语查询(位置信息) → 验证位置字段 M5 模糊纠错(编辑距离) → 验证FSM M6 端到端跑通一个小语料 → 验证整体每一步都能独立验证出错了也容易定位。这也是为什么前面要先把单元测试环境搭好它们就是给这些里程碑把关的。六、先给引擎喂一份样数据光有架构图还是飘给一份具体的样例你就知道每段代码要处理什么。假设我们的文档长这样Doc(1, 无线耳机 降噪 蓝牙) Doc(2, 有线耳机 便宜) Doc(3, 无线鼠标 安静) Doc(4, 耳机 降噪 好玩)经过 analyze 分词、index 构建倒排表会变成无线 → [(1,pos0), (3,pos0)] 耳机 → [(1,pos1), (2,pos1), (4,pos1)] 降噪 → [(1,pos2), (4,pos2)] 蓝牙 → [(1,pos3)] 有线 → [(2,pos0)] 便宜 → [(2,pos2)] 鼠标 → [(3,pos1)] 安静 → [(3,pos2)] 好玩 → [(4,pos3)]现在你搜无线 耳机取两条倒排链求交集得到文档1既含无线又含耳机而文档3只含无线、文档2和4只含耳机都被排除。这就是倒排求交的第一现场。正排则存 Doc 的完整内容查询拿到文档1后从正排取标题和正文返回。位置信息pos暂时用不上等我们做短语查询无线耳机连续出现时它就要出场了。【里程碑 ↔ 测试用例 对应】 M1 建内存倒排查单词 测: 查耳机→[1,2,4] M2 布尔AND求交 测: 无线 耳机→[1] M3 倒排落盘读回 测: 写文件再读, 倒排一致 M4 短语查询 测: 无线耳机短语→只命中连续出现 M5 模糊纠错 测: 无限耳机→纠正为无线耳机 M6 端到端 测: 上面4篇语料跑通整条链路这份样数据我们后面会一直用每到一个里程碑就往里加刁钻用例。把测试数据和里程碑绑死进度看得见、正确性也兜得住。下一篇正式砌第一块砖构建倒排索引。七、技术选型再确认为什么不直接用现成库最后解释一个你可能有的疑问Java 生态里 Lucene 现成的倒排、分词、打分都有为什么我们还要从零写一套玩具版答案就一句用现成库你永远只是在配置不是在理解。Lucene 把倒排、段、FST、DocValues 全封装好了你调 API 能跑但那些设计为什么是这样你看不到、也改不动。我们手写一遍正是为了把这些封装背后的为什么亲手验证一遍。等第二段落幕你再回头用 Lucene就是站在理解之上使用而不是对着黑盒祈祷。当然真做业务肯定用 Lucene/Solr/ES没人会拿玩具引擎上线。本系列前半段的手写是学费后半段钻 Lucene、上 SolrCloud 和 ES才是生产力。手写的玩具和工业引擎骨架是相通的区别只在工程完备度和性能。【手写玩具 vs 工业引擎】 手写玩具: 懂原理、能改、跑得动小数据 ← 前半段目标 工业引擎: 高性能、高可用、功能全 ← 后半段目标 两者骨架: 倒排 / 求交 / 打分 / 分词 一模一样所以别嫌手写麻烦那是绕不过去的一课。下一篇正式砌第一块砖构建倒排索引。本篇小结动手前定规格我们要造一个单机、内存起步、支持单词查询和布尔 AND后续加短语和纠错的迷你检索引擎用 Java 写按 analyze/index/search/model 四模块划分存储先内存后落盘。建造分 M1 到 M6 六个里程碑每步可测可验证。这份图纸定了下一篇就正式砌第一块砖构建倒排索引。上一篇【第09篇】工欲善其事开发环境与单元测试下一篇【第11篇】构建索引一倒排索引的第一块砖
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
