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