★ FEATURED ARTICLE 上一篇【第15篇】读入索引文件怎么把磁盘数据读回来下一篇【第17篇】查询加速跳表与倒排链求交的艺术摘要前面五篇我们从读文档、分词、建倒排、设计格式、安全落盘到读回内存把索引这一头彻底打通了。现在轮到搜索引擎真正存在的意义查。用户敲一个词你怎么从倒排链里捞出相关文档再多词时怎么取交集结果凭什么排前排后。这一篇把查询的最小闭环跑通给你第一个能跑的查询 demo。看到结果按相关性排好队你会第一次有我真的写了个搜索引擎的实感。一、查询的本质从词找回文档建索引时我们干的是文档 → 词的正向活查询正好反过来“词 → 文档”。倒排索引就是为此而生的给一个词直接查它的倒排链链上每个 docId 就是命中文档。单词查询简单到有点无聊用户输入: 耳机 查词典: 耳机 → 倒排链 [1, 2, 4] 结果: 文档 1、2、4 都含耳机这一步的时间复杂度是 O(1) 查词典 O(k) 遍历倒排链k 是命中数。哪怕亿级文档只要耳机只命中几千篇查询也是毫秒级。这正是倒排索引快得不讲道理的原因它把全表扫描变成了按词查表。二、多词查询取交集做 AND真实搜索几乎都是多个词。比如无线 耳机用户想要的是既含无线又含耳机的文档。逻辑就是分别取两条倒排链求交集。用户查询: 无线 耳机 取链: 无线 → [1, 3] 耳机 → [1, 2, 4] 求交集: [1, 3] ∩ [1, 2, 4] [1] 结果: 只有文档 1 同时含两个词如果倒排链有序我们建索引时就是按 docId 递增加入的交集用双指针线性扫描就能做不用额外开 HashSet省内存又快。importjava.util.*;/** 对两条有序倒排链求交集AND */publicclassIntersect{publicstaticListIntegerand(ListIntegera,ListIntegerb){ListIntegerresultnewArrayList();inti0,j0;while(ia.size()jb.size()){intxa.get(i),yb.get(j);if(xy){result.add(x);i;j;}elseif(xy){i;}else{j;}}returnresult;}}重点倒排链必须有序交集才能用双指针 O(nm) 扫完。如果哪天你的倒排链没排序交集会退化成哈希集合内存和速度都吃亏。建索引时保持 docId 有序是这个优化免费的来源。三、打分结果凭什么排前排后交集只解决了要不要没解决谁靠前。搜索引擎的结果是排好序的靠的是打分。我们手写版先用最朴素的 TF词频加权把原理跑通BM25 后面再升级。想法很直白一个词在某文档里出现越多这文档越相关。多词查询时把每个命中词的 tf 加起来当总分。/** 极简打分累加每个命中词的 tf */publicclassSimpleScorer{publicMapInteger,Floatscore(String[]terms,MiniIndexReaderreader)throwsIOException{MapInteger,FloatscoresnewHashMap();for(Stringterm:terms){ListPostingpostingsreader.getPostings(term.toLowerCase());for(Postingp:postings){scores.merge(p.getDocId(),(float)p.getTf(),Float::sum);}}returnscores;}}查无线 耳机文档1在无线里 tf1、“耳机里 tf1总分 2文档3只含无线总分 1。排序后文档1 自然排前。打分越准用户越觉得这搜索懂我”。四、组装成查询 demo第一个能跑的 Searcher把读词典、求交、打分、排序串起来一个最小Searcher就成型了。importjava.util.*;publicclassMiniSearcher{privatefinalMiniIndexReaderreader;publicMiniSearcher(MiniIndexReaderreader){this.readerreader;}publicListSearchHitsearch(Stringquery)throwsIOException{// 1. 分词和建索引用同一套 analyzerSimpleAnalyzeranalyzernewSimpleAnalyzer();ListStringtermsanalyzer.analyze(query);// 2. 取每条倒排链, 逐个求交集(AND)ListIntegerdocIdsnull;MapInteger,FloatscoresnewHashMap();for(Stringterm:terms){ListIntegerchainnewArrayList();for(Postingp:reader.getPostings(term)){chain.add(p.getDocId());scores.merge(p.getDocId(),(float)p.getTf(),Float::sum);}if(docIdsnull){docIdschain;}else{docIdsIntersect.and(docIds,chain);// 与剩余结果求交}}if(docIdsnull)docIdsCollections.emptyList();// 3. 按分数降序排ListSearchHithitsnewArrayList();for(intid:docIds){hits.add(newSearchHit(id,scores.getOrDefault(id,0f)));}hits.sort((a,b)-Float.compare(b.score,a.score));returnhits;}publicstaticclassSearchHit{publicfinalintdocId;publicfinalfloatscore;publicSearchHit(intdocId,floatscore){this.docIddocId;this.scorescore;}publicStringtoString(){returndocdocId, scorescore;}}}跑一下我们的样例语料MiniIndexReaderreadernewMiniIndexReader(newFile(index/dictionary.dat));MiniSearchersearchernewMiniSearcher(reader);System.out.println(searcher.search(无线 耳机));System.out.println(searcher.search(降噪));预期[doc1, score2.0, doc3, score1.0] // 无线 耳机 文档1同时含两词排前 [doc1, score1.0, doc4, score1.0] // 降噪 命中 1 和 4从输入一串字到拿到排好序的命中列表这就是一个搜索引擎最核心的闭环。你刚刚亲手跑通了它。【一次查询的完整链路】 用户输入 无线 耳机 │ 分词 ▼ [无线, 耳机] │ 查倒排 ▼ 无线→[1,3] 耳机→[1,2,4] │ 求交集 ▼ [1] │ 打分排序 ▼ [doc1, score2.0]五、查询里最容易翻车的坑讲几个我见过的真实翻车建索引和查 query 用了不同分词器。建的时候中文按空格切查的时候按字切结果词对不上查啥都空。二者必须同一套规则前面反复强调不是没道理。倒排链没排序就求交。HashSet 一上内存和速度双双翻车语料稍大就卡。忘了处理空查询。用户敲个空格就回车terms 为空交集逻辑要兜底返回空别抛空指针。六、这一篇你跑通了什么到这索引的写和读加上查询的交和排四个环节全通了。你手里已经是一个能用的迷你搜索引擎建索引、落盘、读回、查词、求交、打分、排序一气呵成。但交集用的是朴素的双指针线性扫描。一旦某个词命中十万文档两条长链求交会扫得你怀疑人生。下一篇我们请出跳表SkipList教倒排链跳着比把长链求交的速度拉起来。七、为什么排序用分数而不是命中个数你可能会想一个词命中两次、另一个命中一次直接按命中次数排不就行了问题在长文档天然词多。一篇 5000 字的长文里耳机出现 5 次一篇 100 字的短文里出现 2 次你能说长文更相关吗未必可能只是因为它长。所以朴素 TF 累加已经是个粗略修正但还不够。工业界用 BM25 时还会做文档长度归一同样出现 2 次短文档里的 2 次比长文档里的 2 次更说明问题。我们手写版先用 TF 累加把链路跑通等你钻进 Lucene 再换成 BM25那时你会明白这几个归一项为什么必不可少。八、多词查询的两种打分策略多词查询打分有两种取向值得提前知道求和策略每个命中词贡献的 tf 相加我们上面就是这种。简单但会偏向包含很多词的文档。乘性/协调策略要求文档命中越多词越好漏掉一个词就大幅降分。BooleanQuery 里的 coord 因子就是这个意思能惩罚只命中部分词的结果。我们手写版用求和足够演示原理。真做业务时这两种取向配合词权重标题里的词比正文里的词重要才是相关性调优的主战场。九、查询层的边界感到这查询层已经是一个干净的小模块它只干三件事查倒排、求交、打分排序不关心索引怎么建、怎么存。这种只问倒排链、不问底层的边界让我们可以随时把底层从内存 HashMap 换成 Lucene查询逻辑几乎不动。好的搜索引擎架构就是这样一层层把复杂度隔离出来的。本篇小结查询的本质是词 → 文档的逆过程单词查倒排链即得命中多词用有序双指针求交集做 AND再按 TF 累加打分排序。本文把读索引、求交、打分、排序串成第一个能跑的 Searcher跑出了[doc1, score2.0]这种实打实的结果。但长倒排链线性求交会慢下一篇用跳表让倒排链跳着比提速明显。上一篇【第15篇】读入索引文件怎么把磁盘数据读回来下一篇【第17篇】查询加速跳表与倒排链求交的艺术
阅读完成 · 觉得有帮助？
