據(jù)結(jié)構(gòu)到查詢優(yōu)化的完整指南)
簡介這份資源圍繞C實現(xiàn)倒排索引與搜索功能展開面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、搜索引擎原理或準(zhǔn)備相關(guān)課程設(shè)計的學(xué)習(xí)者。包內(nèi)共13個文件以10個txt文檔作為待索引語料配合2個cpp源文件與1個頭文件構(gòu)成完整工程壓縮包約4KB體量輕巧便于快速上手。項目完整覆蓋從文件讀取、分詞解析到索引構(gòu)建與查詢的流程使用fstream讀取文本借助unordered_map建立單詞到文檔編號列表的映射并通過排序與雙指針求交集實現(xiàn)輸入兩個詞后返回共同出現(xiàn)的文檔。代碼中涉及字符串處理、哈希表、向量容器與異常處理等知識點適合作為理解倒排索引原理的實踐范例。目前已有998人學(xué)習(xí)下載讀者可借此掌握索引構(gòu)建思路、搜索算法實現(xiàn)及內(nèi)存與效率優(yōu)化的基本方法。1. 倒排索引到底解決什么問題為什么值得用 C 手寫一遍如果你手上有幾十萬篇文檔想做一個「輸入關(guān)鍵詞毫秒級返回相關(guān)文檔」的搜索功能第一反應(yīng)可能是上 Elasticsearch。但真到了嵌入式設(shè)備、離線工具、或者對延遲和內(nèi)存有硬要求的場景外部服務(wù)往往塞不進(jìn)去。這時候用 C 從零構(gòu)建一個倒排索引反而是最直接的路子。倒排索引的核心思路很樸素正排是「文檔 → 包含哪些詞」倒排把它翻過來變成「詞 → 出現(xiàn)在哪些文檔里」。查詢時不再逐篇掃描而是直接查詞典拿到文檔列表再做交集合并。這個結(jié)構(gòu)決定了它的查詢復(fù)雜度跟文檔總量關(guān)系不大主要取決于命中詞對應(yīng)的文檔數(shù)量。這篇文章面向兩類人一是想理解搜索引擎底層結(jié)構(gòu)、準(zhǔn)備自己動手寫一個的開發(fā)者二是已經(jīng)會用現(xiàn)成庫但遇到性能瓶頸想搞清楚內(nèi)部機(jī)制的工程師。我會從數(shù)據(jù)結(jié)構(gòu)選型講到可編譯運行的完整代碼再到參數(shù)調(diào)優(yōu)和踩坑記錄每一步都給出能直接抄的代碼塊。2. 倒排索引的數(shù)據(jù)結(jié)構(gòu)選型詞典、倒排表和文檔屬性怎么定2.1 詞典用什么容器哈希表還是有序數(shù)組詞典term dictionary負(fù)責(zé)把詞映射到倒排表。最常見的兩種選擇是std::unordered_map和std::map。前者查詢平均 O(1)后者 O(log n) 但天然有序。如果你的查詢只需要精確匹配單個詞unordered_map是首選。但如果要支持前綴查詢比如輸入「數(shù)據(jù)」能匹配「數(shù)據(jù)庫」「數(shù)據(jù)結(jié)構(gòu)」有序結(jié)構(gòu)配合二分查找會更方便。我一般會先用unordered_map把功能跑通確認(rèn)沒有前綴需求后再定下來。#include unordered_map #include string #include vector // 倒排表每個詞對應(yīng)一組文檔ID using PostingList std::vectorint; // 詞典詞 - 倒排表 std::unordered_mapstd::string, PostingList invertedIndex;這里PostingList用std::vectorint存文檔 ID。選vector而不是list的原因是查詢時要做交集合并vector內(nèi)存連續(xù)、緩存友好而且可以排序后歸并。文檔 ID 用int而非size_t是因為實際文檔量很少超過 21 億用int能省一半內(nèi)存。2.2 倒排表里存什么只存文檔 ID 夠不夠只存文檔 ID 能完成基本檢索但要做相關(guān)性排序就不夠了。實際工程里通常還會存詞頻term frequency和位置信息position。詞頻用于 TF-IDF 或 BM25 打分位置信息用于短語查詢。存儲方式有兩種并行數(shù)組文檔 ID 一個數(shù)組詞頻一個數(shù)組和結(jié)構(gòu)體數(shù)組。并行數(shù)組對緩存更友好結(jié)構(gòu)體可讀性更好。struct Posting { int docId; // 文檔編號 int termFreq; // 該詞在文檔中出現(xiàn)次數(shù) }; // 帶詞頻的倒排表 std::unordered_mapstd::string, std::vectorPosting indexWithFreq;如果暫時不需要排序先用純vectorint把檢索跑通等確實需要打分時再升級結(jié)構(gòu)。過早引入詞頻和位置會讓內(nèi)存翻好幾倍調(diào)試也麻煩。2.3 文檔屬性單獨存正排記錄的必要性倒排索引只告訴你「哪些文檔命中了」但用戶要看的是文檔標(biāo)題、摘要、URL。這些屬性必須單獨用一張正排表存鍵是文檔 ID。struct DocumentMeta { std::string title; std::string url; int length; // 文檔總詞數(shù)用于歸一化打分 }; std::vectorDocumentMeta docStore; // 下標(biāo)即文檔ID用vector而不是map因為文檔 ID 是連續(xù)分配的整數(shù)直接下標(biāo)訪問最快。每加入一篇新文檔就往docStore尾部 push 一條記錄同時把返回的索引作為該文檔的 ID。3. 從零構(gòu)建索引分詞、建表、持久化的完整代碼路徑3.1 分詞器的最小實現(xiàn)按非字母數(shù)字切分英文場景下最簡單的分詞就是按空格和標(biāo)點切分再統(tǒng)一轉(zhuǎn)小寫。中文需要額外接入分詞庫這里先用英文規(guī)則把流程跑通。#include cctype #include sstream // 將輸入文本切分為小寫詞項 std::vectorstd::string tokenize(const std::string text) { std::vectorstd::string tokens; std::string current; for (char ch : text) { if (std::isalnum(static_castunsigned char(ch))) { current std::tolower(static_castunsigned char(ch)); } else { if (!current.empty()) { tokens.push_back(current); current.clear(); } } } if (!current.empty()) tokens.push_back(current); return tokens; }std::isalnum的參數(shù)必須先轉(zhuǎn)unsigned char否則遇到負(fù)值字符是未定義行為這是很多人翻車的地方。分詞結(jié)果統(tǒng)一轉(zhuǎn)小寫保證「Data」和「data」能命中同一個倒排表。3.2 建索引主流程遍歷文檔、更新倒排表建索引的過程就是對每篇文檔分詞統(tǒng)計每個詞的出現(xiàn)次數(shù)然后把文檔 ID 追加到對應(yīng)詞的倒排表里。// 向索引中添加一篇文檔返回分配的文檔ID int addDocument(const std::string title, const std::string body) { int docId static_castint(docStore.size()); docStore.push_back({title, , static_castint(tokenize(body).size())}); auto tokens tokenize(body); std::unordered_mapstd::string, int freq; for (auto t : tokens) freq[t]; for (auto [term, count] : freq) { indexWithFreq[term].push_back({docId, count}); } return docId; }先用局部freq統(tǒng)計詞頻再一次性寫入倒排表避免同一個詞在同一篇文檔里被重復(fù)追加。docStore的size()在建表前取保證文檔 ID 從 0 開始連續(xù)分配。3.3 索引落盤與加載二進(jìn)制格式最省事內(nèi)存索引重啟就沒了必須持久化。文本格式可讀但體積大、解析慢二進(jìn)制格式是更實際的選擇。寫入時先寫詞項數(shù)量再逐個寫詞項長度、詞項內(nèi)容、倒排表大小和每條記錄。#include fstream void saveIndex(const std::string path) { std::ofstream out(path, std::ios::binary); size_t termCount indexWithFreq.size(); out.write(reinterpret_castconst char*(termCount), sizeof(termCount)); for (auto [term, postings] : indexWithFreq) { size_t len term.size(); out.write(reinterpret_castconst char*(len), sizeof(len)); out.write(term.data(), len); size_t psize postings.size(); out.write(reinterpret_castconst char*(psize), sizeof(psize)); out.write(reinterpret_castconst char*(postings.data()), psize * sizeof(Posting)); } }寫入順序必須和讀取順序嚴(yán)格一致否則解析全亂。Posting是 POD 類型可以直接按字節(jié)塊寫入。如果結(jié)構(gòu)體里有std::string成員就不能這么干必須逐字段序列化。4. 查詢與排序多詞交集、TF-IDF 打分和 Top-K 截斷4.1 單詞查詢與多詞交集歸并兩個有序數(shù)組單詞查詢直接查詞典返回倒排表。多詞查詢AND 語義需要對多個倒排表求交集。因為倒排表里的文檔 ID 是遞增的可以用雙指針歸并。// 求兩個有序倒排表的交集 PostingList intersect(const PostingList a, const PostingList b) { PostingList result; size_t i 0, j 0; while (i a.size() j b.size()) { if (a[i].docId b[j].docId) { result.push_back(a[i]); i; j; } else if (a[i].docId b[j].docId) { i; } else { j; } } return result; }雙指針歸并的復(fù)雜度是 O(mn)比用哈希集合求交集快得多因為不需要額外內(nèi)存分配。多個詞時從倒排表最短的那個詞開始依次求交能最快縮小候選集。4.2 TF-IDF 打分讓相關(guān)文檔排前面交集只給出「命中了哪些文檔」順序還是文檔 ID 順序。要按相關(guān)性排序需要打分。TF-IDF 是最經(jīng)典的方案詞頻越高、該詞越罕見得分越高。#include cmath // 計算某文檔對某詞的TF-IDF得分 double tfIdf(int termFreq, int docLength, int totalDocs, int docFreq) { double tf static_castdouble(termFreq) / docLength; double idf std::log(static_castdouble(totalDocs) / (docFreq 1)); return tf * idf; }docFreq是該詞出現(xiàn)在多少篇文檔里也就是倒排表的長度。1是平滑項防止某個詞在所有文檔都出現(xiàn)時 IDF 變成 0。docLength做歸一化避免長文檔因為詞多而占便宜。4.3 Top-K 截斷別把命中文檔全返回查詢「data」可能命中幾萬篇文檔全排序再返回前 10 條是浪費。用一個大小為 K 的最小堆遍歷過程中只保留得分最高的 K 條。#include queue // 返回得分最高的K篇文檔 std::vectorstd::pairint, double topK( const std::vectorstd::pairint, double scored, int k) { // 小頂堆堆頂是當(dāng)前K個里得分最低的 auto cmp [](auto a, auto b) { return a.second b.second; }; std::priority_queuestd::pairint, double, std::vectorstd::pairint, double, decltype(cmp) heap(cmp); for (auto item : scored) { if (heap.size() static_castsize_t(k)) { heap.push(item); } else if (item.second heap.top().second) { heap.pop(); heap.push(item); } } std::vectorstd::pairint, double result; while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); } return result; }堆的比較器用構(gòu)造小頂堆堆頂始終是當(dāng)前保留的 K 條里最差的。新元素比堆頂好就替換。最終結(jié)果是從小到大返回前反轉(zhuǎn)一下即可。K 一般取 10 到 100取決于前端一頁展示多少條。5. 避坑與排查倒排索引實現(xiàn)里最容易翻車的五個地方5.1 分詞后沒去重倒排表里同一文檔出現(xiàn)多次現(xiàn)象查詢結(jié)果里同一篇文檔出現(xiàn)好幾遍或者打分異常偏高。原因建索引時對每個 token 直接 push 文檔 ID沒有先按文檔聚合詞頻。同一篇文檔里「data」出現(xiàn) 5 次倒排表里就有 5 條相同 docId 的記錄。解決先用局部哈希表統(tǒng)計詞頻再一次性寫入。如果已經(jīng)寫壞了查詢時對倒排表按 docId 去重但更徹底的做法是重建索引。5.2 文檔 ID 用 size_t 導(dǎo)致二進(jìn)制文件跨平臺不兼容現(xiàn)象在 64 位機(jī)器上存的索引拿到 32 位環(huán)境加載后數(shù)據(jù)錯亂。原因size_t的寬度隨平臺變化直接按字節(jié)塊讀寫會導(dǎo)致字段寬度不一致。解決持久化時統(tǒng)一用固定寬度類型比如uint32_t存文檔 ID 和詞頻uint64_t存數(shù)量字段?？缙脚_場景下不要用size_t做序列化。5.3 倒排表未排序就做交集結(jié)果漏文檔現(xiàn)象多詞查詢返回的結(jié)果比預(yù)期少但單詞查詢正常。原因文檔不是按 ID 遞增順序加入的或者中途刪過文檔導(dǎo)致倒排表里 docId 亂序。雙指針歸并要求兩邊都有序亂序時比較邏輯失效。解決建索引時保證 docId 單調(diào)遞增如果有刪除操作用標(biāo)記刪除而不是物理刪除查詢時跳過標(biāo)記位。或者在求交集前對每個倒排表做一次排序。5.4 IDF 計算用了實時文檔總數(shù)導(dǎo)致打分不穩(wěn)定現(xiàn)象同樣的查詢加了幾篇文檔后排序結(jié)果大變。原因totalDocs每次查詢都取當(dāng)前文檔總數(shù)索引一變 IDF 就變。如果docFreq沒同步更新打分就失真。解決把totalDocs和每個詞的docFreq在索引構(gòu)建完成后固化下來查詢時直接讀快照。增量更新時同步維護(hù)這兩個值。5.5 內(nèi)存索引全量加載導(dǎo)致啟動慢現(xiàn)象索引文件幾百 MB程序啟動要等十幾秒。原因加載時逐個詞項解析并插入unordered_map每個詞項都觸發(fā)一次內(nèi)存分配。解決加載前用reserve預(yù)留哈希桶數(shù)量減少 rehash。更大的索引可以改造成內(nèi)存映射文件查詢時按需讀取但實現(xiàn)復(fù)雜度會上升一個量級。6. 進(jìn)階技巧用內(nèi)存映射和跳表把查詢再壓一檔索引大到幾百 MB 后全量加載進(jìn)內(nèi)存越來越不劃算。一個實用的進(jìn)階做法是把倒排表按詞項分塊存盤查詢時用內(nèi)存映射按需讀取。下面是一個最小示例展示如何用mmap把索引文件映射進(jìn)地址空間。#include sys/mman.h #include fcntl.h #include unistd.h // 將索引文件映射到內(nèi)存返回起始指針 const char* mapIndex(const std::string path, size_t fileSize) { int fd open(path.c_str(), O_RDONLY); if (fd 0) return nullptr; fileSize lseek(fd, 0, SEEK_END); const char* data static_castconst char*( mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0)); close(fd); return data; }映射后不需要把整個文件讀進(jìn)堆內(nèi)存操作系統(tǒng)按頁調(diào)度。查詢某個詞時先讀詞典區(qū)拿到偏移量再跳到對應(yīng)位置解析倒排表。詞典區(qū)可以常駐內(nèi)存倒排區(qū)按需換入。另一個值得做的優(yōu)化是給倒排表加跳表指針。在倒排表里每隔 128 個文檔插一個跳轉(zhuǎn)點求交集時先按跳轉(zhuǎn)點跳躍再在小區(qū)間內(nèi)線性比較。文檔量上萬后這個優(yōu)化能把交集耗時降一半左右。參數(shù)上跳表間隔取 64 到 256 之間比較合適。太小則跳轉(zhuǎn)點本身占內(nèi)存太大則跳躍收益不明顯。我一般先用 128 跑基準(zhǔn)測試再根據(jù)實際倒排表長度微調(diào)。驗證優(yōu)化效果的方法很直接構(gòu)造 10 萬篇模擬文檔分別測優(yōu)化前后的查詢 P99 延遲和常駐內(nèi)存。如果延遲降了但內(nèi)存漲了 30% 以上就要重新權(quán)衡。我自己的習(xí)慣是每次只改一個變量測完記錄數(shù)據(jù)再動下一個不然出了問題根本不知道是哪個改動引起的。希望幫到你。本文還有配套的精品資源點擊獲取 C++手寫倒排索引：從數(shù)據(jù)結(jié)構(gòu)到查詢優(yōu)化的完整指南
簡介這份資源圍繞C實現(xiàn)倒排索引與搜索功能展開面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、搜索引擎原理或準(zhǔn)備相關(guān)課程設(shè)計的學(xué)習(xí)者。包內(nèi)共13個文件以10個txt文檔作為待索引語料配合2個cpp源文件與1個頭文件構(gòu)成完整工程壓縮包約4KB體量輕巧便于快速上手。項目完整覆蓋從文件讀取、分詞解析到索引構(gòu)建與查詢的流程使用fstream讀取文本借助unordered_map建立單詞到文檔編號列表的映射并通過排序與雙指針求交集實現(xiàn)輸入兩個詞后返回共同出現(xiàn)的文檔。代碼中涉及字符串處理、哈希表、向量容器與異常處理等知識點適合作為理解倒排索引原理的實踐范例。目前已有998人學(xué)習(xí)下載讀者可借此掌握索引構(gòu)建思路、搜索算法實現(xiàn)及內(nèi)存與效率優(yōu)化的基本方法。1. 倒排索引到底解決什么問題為什么值得用 C 手寫一遍如果你手上有幾十萬篇文檔想做一個「輸入關(guān)鍵詞毫秒級返回相關(guān)文檔」的搜索功能第一反應(yīng)可能是上 Elasticsearch。但真到了嵌入式設(shè)備、離線工具、或者對延遲和內(nèi)存有硬要求的場景外部服務(wù)往往塞不進(jìn)去。這時候用 C 從零構(gòu)建一個倒排索引反而是最直接的路子。倒排索引的核心思路很樸素正排是「文檔 → 包含哪些詞」倒排把它翻過來變成「詞 → 出現(xiàn)在哪些文檔里」。查詢時不再逐篇掃描而是直接查詞典拿到文檔列表再做交集合并。這個結(jié)構(gòu)決定了它的查詢復(fù)雜度跟文檔總量關(guān)系不大主要取決于命中詞對應(yīng)的文檔數(shù)量。這篇文章面向兩類人一是想理解搜索引擎底層結(jié)構(gòu)、準(zhǔn)備自己動手寫一個的開發(fā)者二是已經(jīng)會用現(xiàn)成庫但遇到性能瓶頸想搞清楚內(nèi)部機(jī)制的工程師。我會從數(shù)據(jù)結(jié)構(gòu)選型講到可編譯運行的完整代碼再到參數(shù)調(diào)優(yōu)和踩坑記錄每一步都給出能直接抄的代碼塊。2. 倒排索引的數(shù)據(jù)結(jié)構(gòu)選型詞典、倒排表和文檔屬性怎么定2.1 詞典用什么容器哈希表還是有序數(shù)組詞典term dictionary負(fù)責(zé)把詞映射到倒排表。最常見的兩種選擇是std::unordered_map和std::map。前者查詢平均 O(1)后者 O(log n) 但天然有序。如果你的查詢只需要精確匹配單個詞unordered_map是首選。但如果要支持前綴查詢比如輸入「數(shù)據(jù)」能匹配「數(shù)據(jù)庫」「數(shù)據(jù)結(jié)構(gòu)」有序結(jié)構(gòu)配合二分查找會更方便。我一般會先用unordered_map把功能跑通確認(rèn)沒有前綴需求后再定下來。#include unordered_map #include string #include vector // 倒排表每個詞對應(yīng)一組文檔ID using PostingList std::vectorint; // 詞典詞 - 倒排表 std::unordered_mapstd::string, PostingList invertedIndex;這里PostingList用std::vectorint存文檔 ID。選vector而不是list的原因是查詢時要做交集合并vector內(nèi)存連續(xù)、緩存友好而且可以排序后歸并。文檔 ID 用int而非size_t是因為實際文檔量很少超過 21 億用int能省一半內(nèi)存。2.2 倒排表里存什么只存文檔 ID 夠不夠只存文檔 ID 能完成基本檢索但要做相關(guān)性排序就不夠了。實際工程里通常還會存詞頻term frequency和位置信息position。詞頻用于 TF-IDF 或 BM25 打分位置信息用于短語查詢。存儲方式有兩種并行數(shù)組文檔 ID 一個數(shù)組詞頻一個數(shù)組和結(jié)構(gòu)體數(shù)組。并行數(shù)組對緩存更友好結(jié)構(gòu)體可讀性更好。struct Posting { int docId; // 文檔編號 int termFreq; // 該詞在文檔中出現(xiàn)次數(shù) }; // 帶詞頻的倒排表 std::unordered_mapstd::string, std::vectorPosting indexWithFreq;如果暫時不需要排序先用純vectorint把檢索跑通等確實需要打分時再升級結(jié)構(gòu)。過早引入詞頻和位置會讓內(nèi)存翻好幾倍調(diào)試也麻煩。2.3 文檔屬性單獨存正排記錄的必要性倒排索引只告訴你「哪些文檔命中了」但用戶要看的是文檔標(biāo)題、摘要、URL。這些屬性必須單獨用一張正排表存鍵是文檔 ID。struct DocumentMeta { std::string title; std::string url; int length; // 文檔總詞數(shù)用于歸一化打分 }; std::vectorDocumentMeta docStore; // 下標(biāo)即文檔ID用vector而不是map因為文檔 ID 是連續(xù)分配的整數(shù)直接下標(biāo)訪問最快。每加入一篇新文檔就往docStore尾部 push 一條記錄同時把返回的索引作為該文檔的 ID。3. 從零構(gòu)建索引分詞、建表、持久化的完整代碼路徑3.1 分詞器的最小實現(xiàn)按非字母數(shù)字切分英文場景下最簡單的分詞就是按空格和標(biāo)點切分再統(tǒng)一轉(zhuǎn)小寫。中文需要額外接入分詞庫這里先用英文規(guī)則把流程跑通。#include cctype #include sstream // 將輸入文本切分為小寫詞項 std::vectorstd::string tokenize(const std::string text) { std::vectorstd::string tokens; std::string current; for (char ch : text) { if (std::isalnum(static_castunsigned char(ch))) { current std::tolower(static_castunsigned char(ch)); } else { if (!current.empty()) { tokens.push_back(current); current.clear(); } } } if (!current.empty()) tokens.push_back(current); return tokens; }std::isalnum的參數(shù)必須先轉(zhuǎn)unsigned char否則遇到負(fù)值字符是未定義行為這是很多人翻車的地方。分詞結(jié)果統(tǒng)一轉(zhuǎn)小寫保證「Data」和「data」能命中同一個倒排表。3.2 建索引主流程遍歷文檔、更新倒排表建索引的過程就是對每篇文檔分詞統(tǒng)計每個詞的出現(xiàn)次數(shù)然后把文檔 ID 追加到對應(yīng)詞的倒排表里。// 向索引中添加一篇文檔返回分配的文檔ID int addDocument(const std::string title, const std::string body) { int docId static_castint(docStore.size()); docStore.push_back({title, , static_castint(tokenize(body).size())}); auto tokens tokenize(body); std::unordered_mapstd::string, int freq; for (auto t : tokens) freq[t]; for (auto [term, count] : freq) { indexWithFreq[term].push_back({docId, count}); } return docId; }先用局部freq統(tǒng)計詞頻再一次性寫入倒排表避免同一個詞在同一篇文檔里被重復(fù)追加。docStore的size()在建表前取保證文檔 ID 從 0 開始連續(xù)分配。3.3 索引落盤與加載二進(jìn)制格式最省事內(nèi)存索引重啟就沒了必須持久化。文本格式可讀但體積大、解析慢二進(jìn)制格式是更實際的選擇。寫入時先寫詞項數(shù)量再逐個寫詞項長度、詞項內(nèi)容、倒排表大小和每條記錄。#include fstream void saveIndex(const std::string path) { std::ofstream out(path, std::ios::binary); size_t termCount indexWithFreq.size(); out.write(reinterpret_castconst char*(termCount), sizeof(termCount)); for (auto [term, postings] : indexWithFreq) { size_t len term.size(); out.write(reinterpret_castconst char*(len), sizeof(len)); out.write(term.data(), len); size_t psize postings.size(); out.write(reinterpret_castconst char*(psize), sizeof(psize)); out.write(reinterpret_castconst char*(postings.data()), psize * sizeof(Posting)); } }寫入順序必須和讀取順序嚴(yán)格一致否則解析全亂。Posting是 POD 類型可以直接按字節(jié)塊寫入。如果結(jié)構(gòu)體里有std::string成員就不能這么干必須逐字段序列化。4. 查詢與排序多詞交集、TF-IDF 打分和 Top-K 截斷4.1 單詞查詢與多詞交集歸并兩個有序數(shù)組單詞查詢直接查詞典返回倒排表。多詞查詢AND 語義需要對多個倒排表求交集。因為倒排表里的文檔 ID 是遞增的可以用雙指針歸并。// 求兩個有序倒排表的交集 PostingList intersect(const PostingList a, const PostingList b) { PostingList result; size_t i 0, j 0; while (i a.size() j b.size()) { if (a[i].docId b[j].docId) { result.push_back(a[i]); i; j; } else if (a[i].docId b[j].docId) { i; } else { j; } } return result; }雙指針歸并的復(fù)雜度是 O(mn)比用哈希集合求交集快得多因為不需要額外內(nèi)存分配。多個詞時從倒排表最短的那個詞開始依次求交能最快縮小候選集。4.2 TF-IDF 打分讓相關(guān)文檔排前面交集只給出「命中了哪些文檔」順序還是文檔 ID 順序。要按相關(guān)性排序需要打分。TF-IDF 是最經(jīng)典的方案詞頻越高、該詞越罕見得分越高。#include cmath // 計算某文檔對某詞的TF-IDF得分 double tfIdf(int termFreq, int docLength, int totalDocs, int docFreq) { double tf static_castdouble(termFreq) / docLength; double idf std::log(static_castdouble(totalDocs) / (docFreq 1)); return tf * idf; }docFreq是該詞出現(xiàn)在多少篇文檔里也就是倒排表的長度。1是平滑項防止某個詞在所有文檔都出現(xiàn)時 IDF 變成 0。docLength做歸一化避免長文檔因為詞多而占便宜。4.3 Top-K 截斷別把命中文檔全返回查詢「data」可能命中幾萬篇文檔全排序再返回前 10 條是浪費。用一個大小為 K 的最小堆遍歷過程中只保留得分最高的 K 條。#include queue // 返回得分最高的K篇文檔 std::vectorstd::pairint, double topK( const std::vectorstd::pairint, double scored, int k) { // 小頂堆堆頂是當(dāng)前K個里得分最低的 auto cmp [](auto a, auto b) { return a.second b.second; }; std::priority_queuestd::pairint, double, std::vectorstd::pairint, double, decltype(cmp) heap(cmp); for (auto item : scored) { if (heap.size() static_castsize_t(k)) { heap.push(item); } else if (item.second heap.top().second) { heap.pop(); heap.push(item); } } std::vectorstd::pairint, double result; while (!heap.empty()) { result.push_back(heap.top()); heap.pop(); } return result; }堆的比較器用構(gòu)造小頂堆堆頂始終是當(dāng)前保留的 K 條里最差的。新元素比堆頂好就替換。最終結(jié)果是從小到大返回前反轉(zhuǎn)一下即可。K 一般取 10 到 100取決于前端一頁展示多少條。5. 避坑與排查倒排索引實現(xiàn)里最容易翻車的五個地方5.1 分詞后沒去重倒排表里同一文檔出現(xiàn)多次現(xiàn)象查詢結(jié)果里同一篇文檔出現(xiàn)好幾遍或者打分異常偏高。原因建索引時對每個 token 直接 push 文檔 ID沒有先按文檔聚合詞頻。同一篇文檔里「data」出現(xiàn) 5 次倒排表里就有 5 條相同 docId 的記錄。解決先用局部哈希表統(tǒng)計詞頻再一次性寫入。如果已經(jīng)寫壞了查詢時對倒排表按 docId 去重但更徹底的做法是重建索引。5.2 文檔 ID 用 size_t 導(dǎo)致二進(jìn)制文件跨平臺不兼容現(xiàn)象在 64 位機(jī)器上存的索引拿到 32 位環(huán)境加載后數(shù)據(jù)錯亂。原因size_t的寬度隨平臺變化直接按字節(jié)塊讀寫會導(dǎo)致字段寬度不一致。解決持久化時統(tǒng)一用固定寬度類型比如uint32_t存文檔 ID 和詞頻uint64_t存數(shù)量字段?？缙脚_場景下不要用size_t做序列化。5.3 倒排表未排序就做交集結(jié)果漏文檔現(xiàn)象多詞查詢返回的結(jié)果比預(yù)期少但單詞查詢正常。原因文檔不是按 ID 遞增順序加入的或者中途刪過文檔導(dǎo)致倒排表里 docId 亂序。雙指針歸并要求兩邊都有序亂序時比較邏輯失效。解決建索引時保證 docId 單調(diào)遞增如果有刪除操作用標(biāo)記刪除而不是物理刪除查詢時跳過標(biāo)記位。或者在求交集前對每個倒排表做一次排序。5.4 IDF 計算用了實時文檔總數(shù)導(dǎo)致打分不穩(wěn)定現(xiàn)象同樣的查詢加了幾篇文檔后排序結(jié)果大變。原因totalDocs每次查詢都取當(dāng)前文檔總數(shù)索引一變 IDF 就變。如果docFreq沒同步更新打分就失真。解決把totalDocs和每個詞的docFreq在索引構(gòu)建完成后固化下來查詢時直接讀快照。增量更新時同步維護(hù)這兩個值。5.5 內(nèi)存索引全量加載導(dǎo)致啟動慢現(xiàn)象索引文件幾百 MB程序啟動要等十幾秒。原因加載時逐個詞項解析并插入unordered_map每個詞項都觸發(fā)一次內(nèi)存分配。解決加載前用reserve預(yù)留哈希桶數(shù)量減少 rehash。更大的索引可以改造成內(nèi)存映射文件查詢時按需讀取但實現(xiàn)復(fù)雜度會上升一個量級。6. 進(jìn)階技巧用內(nèi)存映射和跳表把查詢再壓一檔索引大到幾百 MB 后全量加載進(jìn)內(nèi)存越來越不劃算。一個實用的進(jìn)階做法是把倒排表按詞項分塊存盤查詢時用內(nèi)存映射按需讀取。下面是一個最小示例展示如何用mmap把索引文件映射進(jìn)地址空間。#include sys/mman.h #include fcntl.h #include unistd.h // 將索引文件映射到內(nèi)存返回起始指針 const char* mapIndex(const std::string path, size_t fileSize) { int fd open(path.c_str(), O_RDONLY); if (fd 0) return nullptr; fileSize lseek(fd, 0, SEEK_END); const char* data static_castconst char*( mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE, fd, 0)); close(fd); return data; }映射后不需要把整個文件讀進(jìn)堆內(nèi)存操作系統(tǒng)按頁調(diào)度。查詢某個詞時先讀詞典區(qū)拿到偏移量再跳到對應(yīng)位置解析倒排表。詞典區(qū)可以常駐內(nèi)存倒排區(qū)按需換入。另一個值得做的優(yōu)化是給倒排表加跳表指針。在倒排表里每隔 128 個文檔插一個跳轉(zhuǎn)點求交集時先按跳轉(zhuǎn)點跳躍再在小區(qū)間內(nèi)線性比較。文檔量上萬后這個優(yōu)化能把交集耗時降一半左右。參數(shù)上跳表間隔取 64 到 256 之間比較合適。太小則跳轉(zhuǎn)點本身占內(nèi)存太大則跳躍收益不明顯。我一般先用 128 跑基準(zhǔn)測試再根據(jù)實際倒排表長度微調(diào)。驗證優(yōu)化效果的方法很直接構(gòu)造 10 萬篇模擬文檔分別測優(yōu)化前后的查詢 P99 延遲和常駐內(nèi)存。如果延遲降了但內(nèi)存漲了 30% 以上就要重新權(quán)衡。我自己的習(xí)慣是每次只改一個變量測完記錄數(shù)據(jù)再動下一個不然出了問題根本不知道是哪個改動引起的。希望幫到你。本文還有配套的精品資源點擊獲取