C++搜索引擎核心：正倒排索引解析

好的我们来详细解析一个基于C的Boost搜索引擎项目中正排索引和倒排索引的核心部分代码及其逻辑。搜索引擎的核心是高效地存储和检索信息正倒排索引是实现这一目标的关键数据结构。核心概念回顾正排索引 (Forward Index)以文档为单位存储每个文档的唯一标识如文档ID及其包含的完整内容或关键信息。可以理解为给定文档ID查找该文档的内容。结构类似于文档ID 1 - 文档1的标题、内容、URL...文档ID 2 - 文档2的标题、内容、URL......倒排索引 (Inverted Index)以词项分词后的单词为单位存储每个词项出现在哪些文档中文档ID列表以及在该文档中的相关信息如频率、位置等。可以理解为给定一个词项查找包含这个词项的所有文档。结构类似于词项 apple - [文档ID 1, 文档ID 3, ...]词项 boost - [文档ID 2, 文档ID 5, ...]...代码结构与详解假设我们有一个简化版的搜索引擎项目结构核心部分可能包含以下文件doc_index.hpp(正排索引相关数据结构)inv_index.hpp(倒排索引相关数据结构)index_builder.hpp/index_builder.cpp(索引构建器)searcher.hpp/searcher.cpp(搜索器使用索引进行查询)(1) 正排索引 (doc_index.hpp)#pragma once #include string #include vector // 定义一个文档项的结构体代表正排索引中的一条记录 struct DocItem { size_t doc_id; // 文档的唯一标识符 std::string title; // 文档标题 std::string content; // 文档摘要或关键内容实际项目中可能存储处理后的内容 std::string url; // 文档的原始URL或其他定位信息 // ... 可能还有其他元数据如时间戳、权重等 }; // 正排索引表本质上是一个DocItem的数组。索引位置通常对应doc_id。 // 例如forward_index[0] 对应 doc_id 0 的文档信息。 using ForwardIndex std::vectorDocItem;DocItem:结构体代表一个文档在正排索引中的完整记录。核心字段是doc_id、title、content(可能是摘要或预处理后的正文)、url。ForwardIndex:使用std::vectorDocItem定义的正排索引表。通常vector的索引号i就直接对应文档IDi。这样可以通过doc_id在$O(1)$时间内直接访问到文档内容。(2) 倒排索引 (inv_index.hpp)#pragma once #include string #include vector #include unordered_map // 定义一个倒排列表项的结构体代表一个词项在某个文档中的出现信息 struct InvertedElem { size_t doc_id; // 文档ID int weight; // 权重可以是词频(TF)、或TF-IDF等计算值 // ... 可能还有其他信息如词项在文档中的位置用于短语查询 }; // 倒排列表包含某个词项的所有 InvertedElem文档ID 相关信息 using InvertedList std::vectorInvertedElem; // 倒排索引表一个哈希映射键是词项(std::string)值是该词项对应的倒排列表(InvertedList) using InvertedIndex std::unordered_mapstd::string, InvertedList;InvertedElem:结构体记录一个词项在特定文档中的信息。核心是doc_id和weight(权重用于后续排序)。InvertedList:std::vectorInvertedElem代表一个词项在所有相关文档中的出现情况列表。InvertedIndex:std::unordered_mapstd::string, InvertedList是整个倒排索引的核心数据结构。它建立了从词项 (key)到包含该词项的所有文档信息列表 (value)的映射。哈希表提供了接近$O(1)$的词项查找效率。(3) 索引构建 (index_builder.hpp/index_builder.cpp)索引构建过程通常包括文档解析 (Parser)读取原始数据文件如HTML、JSON、XML等提取出标题、内容、URL等信息生成DocItem。分词 (Tokenizer)对文档内容进行分词处理得到一系列词项。构建正排索引将DocItem按doc_id顺序或直接使用vector下标存入ForwardIndex。构建倒排索引对每个文档分出的每个词项在InvertedIndex中找到对应的InvertedList或新建然后将该文档的doc_id和计算出的weight等信息作为一个InvertedElem添加到该词项的倒排列表中。// index_builder.hpp #pragma once #include doc_index.hpp #include inv_index.hpp class IndexBuilder { public: // 构建索引的核心接口 void Build(const std::string input_path); // 输入原始数据路径 // 获取构建好的索引 const ForwardIndex GetForwardIndex() const { return forward_index_; } const InvertedIndex GetInvertedIndex() const { return inverted_index_; } private: // 内部辅助方法 bool ParseDoc(const std::string file_path, DocItem doc); // 解析单个文档文件 void CutWord(const std::string content, std::vectorstd::string words); // 分词 // 索引存储 ForwardIndex forward_index_; // 正排索引表 InvertedIndex inverted_index_; // 倒排索引表 };// index_builder.cpp (部分关键逻辑) #include index_builder.hpp #include fstream // ... 其他必要的头文件如分词库 void IndexBuilder::Build(const std::string input_path) { // 1. 遍历 input_path 下的所有待索引文档文件 std::vectorstd::string doc_files ...; // 获取所有文档文件路径列表 size_t next_doc_id 0; // 下一个可用的文档ID for (const auto file_path : doc_files) { DocItem doc; // 2. 解析文档读取文件填充doc (title, content, url...) if (!ParseDoc(file_path, doc)) { continue; // 解析失败跳过 } // 3. 添加到正排索引分配doc_id并存储 doc.doc_id next_doc_id; // 分配递增的doc_id forward_index_.push_back(doc); // 添加到正排索引表末尾 // 4. 对文档内容分词 std::vectorstd::string words; CutWord(doc.content, words); // 可能也需要对标题分词 // 5. 处理分词得到的词项构建倒排索引 for (const auto word : words) { // 5.1 在倒排索引中查找这个词项的倒排列表 auto inv_list inverted_index_[word]; // 如果不存在会自动创建 // 5.2 检查这个词项是否已在该文档的倒排列表中避免重复添加同一个词项在同一文档 // 这里简化处理假设每次出现都记录。实际可能需要合并或更新权重。 // 5.3 创建倒排项并添加到列表 InvertedElem elem; elem.doc_id doc.doc_id; elem.weight ...; // 计算权重例如简单计数weight或更复杂的TF计算 inv_list.push_back(elem); } } // 6. (可选) 对所有倒排列表排序例如按doc_id排序方便后续求交集等操作 for (auto kv : inverted_index_) { auto inv_list kv.second; std::sort(inv_list.begin(), inv_list.end(), [](const InvertedElem a, const InvertedElem b) { return a.doc_id b.doc_id; // 按doc_id升序排列 }); } }Build函数驱动整个索引构建流程。ParseDoc函数需要根据原始数据格式实现提取出标题、正文、URL等信息填充到DocItem。CutWord函数实现分词功能。可以使用第三方库如jieba(中文)boost::tokenizer或自定义规则。正排索引添加为每个成功解析的文档分配一个唯一的doc_id这里使用递增的整数并将其DocItem放入forward_index_。倒排索引添加对文档内容分词后遍历每个词项word。通过inverted_index_[word]访问或创建该词项的倒排列表。创建一个新的InvertedElem包含当前文档的doc_id和计算出的weight这里简化了权重的计算。将该InvertedElem添加到词项word对应的倒排列表inv_list中。倒排列表排序构建完成后通常会将每个倒排列表按doc_id排序。这对于后续进行多个词项查询时使用跳表指针或归并算法高效地求文档ID交集非常有帮助。(4) 搜索器 (searcher.hpp/searcher.cpp)搜索器使用构建好的正倒排索引来处理用户查询。// searcher.hpp #pragma once #include doc_index.hpp #include inv_index.hpp #include string #include vector // 定义一个搜索结果项 struct SearchItem { size_t doc_id; // 文档ID std::string title; // 文档标题 (方便展示) std::string desc; // 摘要 (从内容中提取的关键片段) std::string url; // 文档URL int weight; // 相关性权重 (用于排序) }; class Searcher { public: // 初始化传入构建好的正排和倒排索引 void Init(const ForwardIndex* forward_index, const InvertedIndex* inverted_index); // 执行搜索 void Search(const std::string query, std::vectorSearchItem results); private: // 内部辅助方法 void CutQueryWord(const std::string query, std::vectorstd::string words); // 对查询分词 void MergeInvertedLists(const std::vectorInvertedList* inv_lists, std::vectorSearchItem results); // 合并倒排列表并排序 const ForwardIndex* forward_index_; // 指向正排索引的指针 (避免拷贝) const InvertedIndex* inverted_index_; // 指向倒排索引的指针 };// searcher.cpp (关键逻辑) #include searcher.hpp #include algorithm // ... 其他必要的头文件 void Searcher::Search(const std::string query, std::vectorSearchItem results) { results.clear(); // 清空上次结果 // 1. 对用户查询进行分词 std::vectorstd::string query_words; CutQueryWord(query, query_words); if (query_words.empty()) { return; // 无有效查询词 } // 2. 从倒排索引中获取每个查询词对应的倒排列表 std::vectorInvertedList* all_inv_lists; for (const auto word : query_words) { auto it inverted_index_-find(word); if (it ! inverted_index_-end()) { // 如果索引中有这个词 all_inv_lists.push_back((it-second)); // 保存指向其倒排列表的指针 } // 注意如果没找到这个词被忽略。实际项目中可能涉及拼写纠错等。 } if (all_inv_lists.empty()) { return; // 所有查询词都不在索引中 } // 3. 合并倒排列表 (求交集) 并计算相关性 MergeInvertedLists(all_inv_lists, results); // 4. 生成摘要信息 (这里简化) for (auto item : results) { // 4.1 通过doc_id从正排索引获取文档信息 if (item.doc_id forward_index_-size()) { const DocItem doc (*forward_index_)[item.doc_id]; item.title doc.title; item.url doc.url; // 4.2 生成摘要: 这里简化直接截取部分内容作为描述 item.desc doc.content.substr(0, 100); // 取前100字符 } } } void Searcher::MergeInvertedLists(const std::vectorInvertedList* inv_lists, std::vectorSearchItem results) { // 简化版假设所有列表已经按doc_id排序 // 目标找到同时出现在所有倒排列表中的文档ID (交集) // 方法1: 取最短的列表作为基准遍历检查是否在其他列表中存在 (适合少量列表) // 方法2: 使用归并排序思想求多个有序列表的交集 (更高效) // 这里以两个列表为例展示归并思想 (扩展到多个需要循环处理) if (inv_lists.size() 1) { // 只有一个词项直接处理 for (const auto elem : *(inv_lists[0])) { SearchItem item; item.doc_id elem.doc_id; item.weight elem.weight; // 单个词项的权重 results.push_back(item); } } else if (inv_lists.size() 2) { // 简化仅处理前两个列表的交集 const auto listA *(inv_lists[0]); const auto listB *(inv_lists[1]); size_t i 0, j 0; while (i listA.size() j listB.size()) { if (listA[i].doc_id listB[j].doc_id) { i; } else if (listA[i].doc_id listB[j].doc_id) { j; } else { // 找到交集文档 SearchItem item; item.doc_id listA[i].doc_id; item.weight listA[i].weight listB[j].weight; // 简单权重相加 (实际可能用更复杂的公式) results.push_back(item); i; j; } } } // 5. 根据计算出的总权重对结果进行降序排序 std::sort(results.begin(), results.end(), [](const SearchItem a, const SearchItem b) { return a.weight b.weight; // 按权重降序排列 }); }Init函数接收外部构建好的正排和倒排索引的指针。Search函数处理用户查询。查询分词使用和索引构建时相同的分词器对查询字符串进行分词。查找倒排列表对每个查询词在倒排索引inverted_index_中查找对应的倒排列表。只处理存在于索引中的词。合并倒排列表 (求交集)核心步骤。目标是找出包含所有查询词的文档交集。示例中展示了两个列表的归并求交集方法。如果只有一个查询词则直接使用其倒排列表作为初始结果。对于多个查询词需要求它们的倒排列表的交集文档ID同时出现在所有列表中。高效的算法是利用倒排列表已按doc_id排序的特性使用多指针归并。计算相关性权重在合并过程中累加或用更复杂的公式计算文档在各个查询词倒排项中的weight作为该文档与查询的相关性分数。结果排序根据计算出的相关性权重对结果文档进行降序排序最相关的排在最前面。生成摘要信息遍历排序后的结果列表根据doc_id从正排索引forward_index_中取出文档的标题、URL等信息。并生成一个摘要示例中简单截取内容前N个字符。MergeInvertedLists函数实现了简化版的多个有序倒排列表求交集和权重合并的逻辑。实际项目需要实现能处理任意数量列表的高效求交集算法。总结这个代码框架展示了C实现搜索引擎正倒排索引的核心逻辑数据结构使用std::vector存储正排索引ForwardIndex和倒排列表InvertedList使用std::unordered_map存储倒排索引InvertedIndex。构建过程解析文档 - 分词 - 填充正排索引 - 为每个词项填充倒排索引记录文档ID和权重- 对倒排列表排序。查询过程查询分词 - 获取各词项的倒排列表 - 求列表交集找出共同包含所有查询词的文档- 计算相关性权重 - 排序 - 利用正排索引获取文档详细信息并生成摘要。注意这是一个简化版本。实际项目需要考虑大规模数据处理内存限制、磁盘存储、索引压缩。分词质量中文需要好的分词器英文可能需要词干提取(stemming)、停用词过滤。权重计算更复杂的TF-IDF、BM25等算法。查询处理AND/OR/NOT操作、短语查询、拼写纠错、同义词扩展。性能优化高效的求交集算法跳表指针、缓存机制。摘要生成高亮显示查询词、生成更准确的摘要片段。