从零构建关键词检索系统：倒排索引、BM25打分与中文分词实战

关键词检索这件事看起来简单真动手写起来坑不少。我最早接触这类需求是在一个内部文档管理模块里当时想的就是用户输入几个词把最相关的文档排前面听起来十分钟能搞定结果从分词、打分到排序策略调了一整周才勉强能用。这篇就把我从零搭一个基于关键词的文本排序检索系统的完整思路拆开讲包括倒排索引怎么建、TF-IDF和BM25怎么选、中文分词怎么处理、排序分数怎么归一化、性能怎么优化。代码用Java写但思路跟语言无关换成任何后端栈都能照搬。适合有一定Java基础、想自己动手做一个轻量级检索系统的朋友也适合想搞清楚搜索引擎排序背后到底在算什么的人。1. 先想清楚为什么不用数据库的LIKE就完事了很多人第一反应是我直接用SQL的LIKE查询不就行了。小数据量确实可以但一旦文档上了几万条LIKE的全表扫描会让你等到怀疑人生。更关键的是LIKE只能告诉你包含或不包含它没法告诉你哪条更相关。而检索系统的核心价值恰恰在于排序——把最相关的结果排在最前面。1.1 关键词检索要解决的三件事我把这个系统的核心需求拆成三块找到给定关键词快速定位到包含这些词的文档集合不能全表扫描。打分对每个候选文档计算一个相关性分数分数越高越相关。排序按分数从高到低返回同时处理分数相同、关键词命中位置不同等边界情况。这三件事对应三个技术点倒排索引、相关性打分模型、排序与归一化。下面逐个拆。1.2 一个生活化的类比把检索系统想象成一个图书馆。倒排索引就是图书馆的索引卡片柜——每张卡片写着一个词后面跟着所有包含这个词的书架编号。你查机器学习直接翻到那张卡片就知道哪几本书涉及这个主题不用一本本翻。打分模型则是图书管理员帮你判断哪本书讲机器学习讲得最深入——是整本书都在讲还是只在某一页提了一嘴。排序就是把管理员认为最值得看的书放在最上面。这个类比贯穿全文后面讲每个模块时我都会回到它。2. 倒排索引整个系统的地基倒排索引Inverted Index是检索系统的核心数据结构。正排索引是文档→包含的词倒排索引反过来是词→包含该词的文档列表。这个反转是性能的关键。2.1 倒排索引的基本结构最朴素的倒排索引就是一个Map// 词 - 文档ID列表 MapString, ListInteger invertedIndex new HashMap();但实际用起来光有文档ID不够。你还需要知道这个词在每个文档里出现了几次词频TF以及出现在哪些位置用于短语匹配和高亮。所以更实用的结构是// 词 - (文档ID - 词频) MapString, MapInteger, Integer invertedIndex new HashMap();如果要支持位置信息再嵌套一层// 词 - (文档ID - 位置列表) MapString, MapInteger, ListInteger invertedIndexWithPositions new HashMap();我建议一开始就把词频带上因为打分模型几乎一定会用到TF。位置信息可以后面按需加它占内存比较大。2.2 构建索引的完整流程构建索引分两步文档预处理和索引写入。第一步文档预处理。对每个文档做分词得到词列表。中文需要分词器英文按空格和标点切分即可。分词后通常还要做归一化转小写、去停用词、词干提取英文。中文一般不做词干提取但去停用词是必要的。第二步写入索引。遍历分词结果对每个词更新倒排索引public void addDocument(int docId, String content) { ListString tokens tokenizer.tokenize(content); MapString, Integer termFreq new HashMap(); for (String token : tokens) { termFreq.merge(token, 1, Integer::sum); } for (Map.EntryString, Integer entry : termFreq.entrySet()) { String term entry.getKey(); int freq entry.getValue(); invertedIndex .computeIfAbsent(term, k - new HashMap()) .put(docId, freq); // 同时记录文档长度BM25打分需要 docLengths.put(docId, tokens.size()); } }注意这里我先用termFreq统计了每个词在文档内的词频再一次性写入索引。这样做的好处是避免对同一个词反复操作Map性能更好。2.3 文档长度为什么要单独存你可能注意到上面存了docLengths。这是因为BM25打分模型需要知道每个文档的长度用来做长度归一化——长文档天然更容易命中更多词如果不做归一化长文档会不公平地占优。这个细节后面讲BM25时会展开。2.4 索引的内存与持久化权衡纯内存的倒排索引查询极快但重启就没了。生产环境一般会把索引持久化到磁盘。简单做法是序列化整个Map到文件启动时反序列化。但文档量大时序列化/反序列化会很慢。我的经验是如果文档在十万级以内直接Java序列化到磁盘完全够用启动加载几秒钟的事。如果上了百万级就得考虑分片存储或者用现成的检索引擎了。自己手写的话可以按词的首字母分文件存储加载时按需读取减少启动开销。提示倒排索引的value用MapInteger, Integer而不是ListInteger是因为查询时经常需要某个文档是否包含某个词以及词频是多少用Map的查找是O(1)比遍历List快得多。代价是内存占用略高但值得。3. 中文分词绕不过去的第一道坎英文检索相对简单按空格切词就行。中文没有天然分隔符必须分词。这一步做不好后面打分再精确也白搭。3.1 分词器的选择Java生态里常用的中文分词器有几个方向方案特点适用场景基于词典的最大匹配实现简单速度快依赖词典质量领域词汇固定的场景基于统计的分词准确率高需要训练语料通用文本开源分词库开箱即用维护成本低绝大多数项目我的建议是除非有特殊需求直接用成熟的开源分词库。自己写分词器是个无底洞尤其是处理歧义切分南京市长江大桥这种经典例子和新词识别。3.2 分词粒度对检索的影响分词粒度是个容易被忽略的坑。比如自然语言处理粗粒度切成一个词细粒度切成自然/语言/处理。如果用户搜语言处理粗粒度索引里没有这个词就搜不到细粒度索引里能匹配上。反过来如果用户搜自然语言处理这个完整短语细粒度索引需要做短语匹配才能保证准确性否则会把只包含语言的文档也排上来。我的做法是索引时用细粒度查询时也做细粒度切分然后通过短语匹配来提升精度。这样兼顾召回率和准确率。具体来说查询自然语言处理时切成自然/语言/处理三个词先召回包含任一词的文档再对同时包含这三个词且位置连续的文档加分。3.3 停用词处理的实际取舍停用词如的了在通常要去掉因为它们几乎出现在每个文档里没有区分度。但有个例外如果用户搜的就是包含停用词的短语去掉后可能匹配错。我的处理方式是索引时去掉停用词查询时也去掉但对原始查询做一次短语匹配校验。如果去掉停用词后召回的结果里有文档的原文包含完整查询短语给它额外加分。这样既保证了索引效率又不会因为去停用词而丢失精度。3.4 一个分词踩坑实例早期我用某个分词库时发现它对英文和数字的处理有问题——Java8被切成了Java和8导致搜Java8搜不到。后来我在分词前先做了一层预处理把字母数字的组合识别为整体再交给分词器。这个坑很隐蔽因为大部分测试用例都是纯中文不会暴露这个问题。注意分词器的词典要定期更新尤其是做垂直领域检索时。新词、网络用语、专业术语如果不在词典里会被切得乱七八糟。我一般会维护一个自定义词典把业务相关的词加进去。4. 打分模型TF-IDF还是BM25找到候选文档后下一步是给每个文档打分。分数决定了排序所以打分模型的选择直接决定了检索质量。4.1 TF-IDF的核心思想TF-IDF由两部分组成TF词频一个词在文档里出现越多说明文档越可能跟这个词相关。IDF逆文档频率一个词在越少的文档里出现说明它越有区分度权重越高。公式TF-IDF TF × IDF IDF log(总文档数 / 包含该词的文档数)直觉上很好理解如果的出现在所有文档里IDF接近0权重极低如果倒排索引只出现在3个文档里IDF很高命中它的文档应该排前面。4.2 TF-IDF的局限TF-IDF有个问题TF是线性增长的。一个词出现10次和出现20次TF翻倍分数也翻倍。但实际上出现10次已经说明文档很相关了出现20次并不会让相关性翻倍。这种线性增长会让某些堆砌关键词的文档获得不合理的高分。另外TF-IDF没有考虑文档长度。长文档的TF天然更高会不公平地占优。4.3 BM25的改进BM25在TF-IDF基础上做了两个关键改进第一TF饱和。BM25的TF部分用了饱和函数词频增加到一定程度后分数增长趋缓TF_component (tf × (k1 1)) / (tf k1 × (1 - b b × docLen / avgDocLen))其中k1控制饱和速度通常取1.2到2.0b控制长度归一化强度通常取0.75。第二文档长度归一化。公式里的docLen / avgDocLen就是长度归一化因子。文档越长分母越大TF贡献越小抵消了长文档的优势。4.4 两种模型的实测对比我在一个约5万篇文档的测试集上对比过两者指标TF-IDFBM25短查询准确率一般较好长文档公平性差好关键词堆砌抗性差好实现复杂度低中计算速度快略慢结论很明确只要不是极端追求性能直接用BM25。它的实现复杂度只比TF-IDF高一点点但效果提升明显。我现在的项目里默认都用BM25。4.5 BM25的Java实现要点public double bm25Score(int tf, int docLen, double avgDocLen, int totalDocs, int docFreq, double k1, double b) { double idf Math.log(1 (totalDocs - docFreq 0.5) / (docFreq 0.5)); double tfComponent (tf * (k1 1)) / (tf k1 * (1 - b b * docLen / avgDocLen)); return idf * tfComponent; }注意IDF的写法我用的是带平滑的版本log(1 (N - df 0.5)/(df 0.5))这样即使某个词出现在所有文档里IDF也不会是负数。标准BM25的IDF在某些情况下会算出负值导致分数异常平滑版本能避免这个问题。4.6 多关键词的分数合并用户查询通常有多个词每个词算出一个分数怎么合并最简单的是相加。但要注意不同词的IDF差异很大直接相加会让高IDF的词主导结果。我的做法是每个词的分数先做归一化再相加。归一化可以用该词在所有文档中的最大分数做分母。这样每个词的贡献被拉到同一量级合并更合理。另外如果查询里有短语连续多个词对短语匹配的文档额外加分。这个加分系数我一般设成1.5到2.0具体值靠测试调。5. 排序与结果处理分数算完了还没结束打分只是中间步骤最终要输出一个排好序的结果列表。这一步有不少细节。5.1 分数归一化到0-1区间原始BM25分数没有固定范围可能很大也可能很小。如果要在前端展示相关度90%就需要归一化。常用方法是用当前结果集里的最高分做分母double maxScore results.stream() .mapToDouble(SearchResult::getScore) .max().orElse(1.0); for (SearchResult r : results) { r.setNormalizedScore(r.getScore() / maxScore); }但这样有个问题如果结果集里只有一个文档它的归一化分数永远是1.0看起来完美匹配实际上可能只是矮子里拔将军。更稳妥的做法是维护一个全局的历史最高分或者用一个理论上的分数上限做分母。我一般用当前结果集最高分但在前端展示时加一句相对相关度避免误导。5.2 排序的稳定性处理当两个文档分数相同时排序结果应该稳定。Java的Collections.sort是稳定排序但如果你用parallelSort就不保证了。我的做法是在比较器里加一个次级排序键比如文档ID或者发布时间确保分数相同时顺序确定。results.sort(Comparator .comparingDouble(SearchResult::getScore).reversed() .thenComparingInt(SearchResult::getDocId));5.3 分页与截断检索系统通常不需要返回所有匹配文档用户只看前几页。所以可以在排序后直接截断int from (page - 1) * pageSize; int to Math.min(from pageSize, results.size()); ListSearchResult pageResults results.subList(from, to);但要注意截断前必须完成全部打分和排序不能边打分边截断否则可能漏掉高分文档。如果性能有压力可以用堆优先队列维护Top-K避免全排序。对于K远小于N的情况堆排序能把复杂度从O(N log N)降到O(N log K)。5.4 高亮关键词位置用户搜完通常希望看到关键词在文档里出现的位置被高亮。这需要位置信息。如果索引里存了位置列表直接取出来即可如果没存可以在返回结果前对原文做一次匹配定位。我的建议是如果文档不大几千字以内不存位置信息返回时现算。这样省内存而且现算的逻辑简单不容易出错。只有文档很大或者高亮要求很高时才值得在索引里存位置。6. 性能优化从能用变成好用功能跑通只是第一步真正上线还得过性能这关。6.1 查询词的处理顺序多关键词查询时先处理IDF高的词也就是区分度高的词。因为高IDF词命中的文档少能快速缩小候选集。比如查询的 倒排索引先查倒排索引可能只有几十个文档命中再在这几十个里过滤的比反过来快得多。// 按文档频率升序排列查询词先处理稀有的 ListString sortedTerms queryTerms.stream() .sorted(Comparator.comparingInt(t - invertedIndex.getOrDefault(t, Collections.emptyMap()).size())) .collect(Collectors.toList());6.2 候选集的交集运算如果查询有多个词理想情况是取所有词命中文档的交集AND语义。但如果交集为空就得退化成并集OR语义。我的做法是先尝试交集为空则退化为并集。这样既保证了精度又不会让用户搜不到东西。交集运算时从最小的集合开始逐个和其他集合求交能减少比较次数。6.3 缓存策略热门查询的重复率很高。可以加一层LRU缓存把查询词组合和对应的结果列表缓存起来。缓存key用排序后的查询词拼接避免AB和BA被当成两个查询。String cacheKey queryTerms.stream() .sorted().collect(Collectors.joining(|));缓存要注意失效文档增删改后相关缓存要清掉。简单做法是文档一变就清空整个缓存粗暴但有效。精细做法是维护词到缓存的映射只清受影响的。我一般先用粗暴做法等性能真的成瓶颈了再优化。6.4 索引构建的并行化如果文档量大构建索引可以并行。把文档分片每个线程处理一片最后合并倒排索引。合并时要注意线程安全用ConcurrentHashMap或者分段锁。但并行构建有个坑合并阶段可能成为瓶颈。如果每个线程都产出一个完整的倒排索引合并时要把所有词的所有文档列表合并开销很大。更好的做法是让每个线程处理不同的词范围或者用MapReduce的思路先局部聚合再全局合并。6.5 内存占用的控制倒排索引很吃内存。一个优化技巧是用int数组代替List存文档ID。List 每个元素都有对象开销int数组紧凑得多。代价是插入时不方便适合索引构建完成后不再变动的场景。另一个技巧是对文档ID做差值编码。如果文档ID是递增的存差值比存原值占空间小。查询时再还原。这个优化在文档量极大时才明显小规模没必要。7. 几个我踩过的坑和对应的解法理论讲完了说几个实际开发中遇到的坑都是文档里不会写的。7.1 空查询和单字查询的处理用户可能输入空字符串或者只输入一个停用词。这时候如果直接走检索流程要么报错要么返回一堆无意义结果。我的处理是空查询直接返回空列表单停用词查询返回提示请输入更有意义的词。别小看这个线上真的有人这么搜。7.2 特殊字符导致的查询异常用户输入里可能包含正则特殊字符、引号、括号等。如果查询解析没做好轻则匹配错误重则抛异常。我的做法是查询词先做转义和过滤只保留字母、数字和常见标点。中文标点也要处理全角和半角要统一。7.3 同义词和近义词的召回用户搜电脑文档里写的是计算机就搜不到。解决办法是维护一个同义词表查询时把同义词也加进去一起检索。同义词表可以手工维护也可以从业务数据里挖掘。我一般先手工维护核心词后面再考虑自动化。7.4 索引更新时的并发问题如果系统支持实时添加文档索引更新和查询会并发。用ConcurrentHashMap能保证单个操作的线程安全但读-改-写这种复合操作还是可能出问题。我的做法是索引用读写锁保护写的时候加写锁读的时候加读锁。虽然会降低一点并发度但保证了正确性。如果并发要求极高可以考虑双缓冲——维护两份索引写的时候写新的写完切换指针。7.5 打分结果的解释性有时候用户会问为什么这个文档排第一。如果打分过程是个黑盒很难解释。我的做法是在返回结果里附带每个查询词的命中次数和贡献分数。这样既能解释排序也方便调试。调试阶段这个信息特别有用能快速定位是哪个词的分数异常导致排序不对。8. 从单机到可扩展后续可以怎么演进这套系统在单机、十万级文档的场景下完全够用。如果数据量继续涨有几个演进方向。8.1 索引分片把文档按某种规则比如ID范围或哈希分成多个分片每个分片独立建索引。查询时并行查所有分片合并结果。这样单机内存不够的问题就解决了而且查询可以并行加速。8.2 引入向量检索做语义召回关键词检索的硬伤是字面匹配搜苹果手机搜不到只写iPhone的文档。解决办法是加一路向量检索把文档和查询都转成向量用余弦相似度做语义召回再和关键词检索的结果融合。这就是现在常说的混合检索。实现上可以用现成的向量库也可以自己算但自己算的话性能和效果都要打折扣。8.3 学习排序如果有点击日志可以用学习排序Learning to Rank的方法把BM25分数、文档质量、用户行为等特征喂给模型让模型学出最优排序。这比手工调BM25参数效果好得多但需要数据和模型训练的基础设施。小项目一般用不上知道有这条路就行。8.4 参数调优的经验值最后分享几个BM25参数的调优经验。k1控制词频饱和值越大词频的影响越持久。对于短文本标题、摘要k1取1.2左右对于长文本正文k1可以取1.5到2.0。b控制长度归一化0表示不归一化1表示完全归一化。一般取0.75但如果你的文档长度差异很大可以调高到0.8以上如果文档长度都差不多可以调低到0.5。这些值没有绝对标准最好的办法是准备一批标注数据用网格搜索找最优。没有标注数据的话就靠人工看Top-10结果凭感觉调。我一般会准备20到30个典型查询每次调参后看这些查询的结果有没有变好避免过拟合到个别查询上。整套系统写下来核心代码量其实不大倒排索引加BM25打分几百行就能跑起来。难的是各种边界情况的处理和参数调优这些只能靠实际跑数据、看结果、反复迭代。我建议你先用一个小数据集把流程跑通再逐步加文档量观察性能瓶颈出现在哪里有针对性地优化。别一上来就想着做分布式单机优化到位大部分场景都够用了。