C++ 基于正倒排索引的 Boost 搜索引擎核心模块实现与详解

1. 正倒排索引的结构

1.1 正排索引

正排索引存储文档内容及其 ID。

// 定义文档信息结构体
typedef struct DocInfo {
    std::string title;   // 文档标题
    std::string content; // 文档内容
    std::string url;     // 文档 URL
    int doc_id;          // 文档 ID
} DocInfo;

1.2 倒排索引

倒排索引存储文档 ID、对应关键字及权重。InvertedList 通常称为倒排拉链，一个关键字可能对应多个文档。

// 定义倒排元素结构体
struct InvertedElem {
    int doc_id;      // 文档 ID
    std::string word;// 关键词
    int weight;      // 权重
};
typedef std::vector<InvertedElem> InvertedList;

2. 正倒排序部分 Class 的 Private 部分

2.1 准备工作

正向索引使用 Vector，下标即为文档 ID，便于访问。反向索引使用哈希表（unordered_map），将关键字映射到倒排文档列表。

private:
    // 正排索引使用 Vector，下标对应文档 ID
    std::vector<DocInfo> forward_index;
    // 使用哈希表进行映射
    std::unordered_map<std::string, InvertedList> inverted_index;

2.2 单例模式

本代码采用单例模式，主要优势包括：

1. 减少资源浪费：避免反复创建或销毁实例导致的内存占用过高和 IO 开销增加。
2. 确保全局逻辑统一：强制所有搜索请求复用同一套逻辑，避免结果混乱。
3. 简化资源管理与调用：降低模块间耦合度，减少代码冗余。

因此需禁用拷贝构造函数和赋值运算符，并添加互斥锁以防止多线程并发创建实例。双重检查锁定机制用于确保线程安全。

private:
    Index() {};
    Index(const Index&) = delete;
    Index& operator=(const Index&) = delete;
    static Index* instance;
    static std::mutex log;

public:
    ~Index();

    static Index* Getinstance() {
        if (instance == nullptr) {
            log.lock();
            if (instance == nullptr) {
                instance = new Index();
            }
            log.unlock();
        }
        return instance;
    }

3. 基于清洗后文档构建索引

3.1 构建正排索引

通过 Split 函数进行分词，将切分后的内容赋值给临时变量 doc，再存入 forward_index。

DocInfo* BuildForwardIndex(const std::string& line) {
    std::vector<std::string> results;
    ns_util::StringUtil::Split(line, &results, "\3"); // 字符串切割，分离 title, content, url
    if (results.size() != 3) return nullptr;

    DocInfo doc;
    doc.title = results[0];
    doc.content = results[1];
    doc.url = results[2];
    doc.doc_id = forward_index.size(); // 文档 ID 为当前下标

    forward_index.push_back(doc);
    return &forward_index.back();
}

3.2 构建倒排索引

构建过程包含四个步骤：分词、词频统计、权重计算、填充倒排索引。

bool BuildInvertedIndex(const DocInfo& doc) {
    struct word_cnt {
        int title_cnt;
        int content_cnt;
        word_cnt() : title_cnt(0), content_cnt(0) {}
    };

    std::unordered_map<std::string, word_cnt> word_map;
    std::vector<std::string> title_words;
    ns_util::JiebaUsutl::CutString(doc.title, &title_words);
    for (auto& tw : title_words) {
        boost::to_lower(tw);
        word_map[tw].title_cnt++;
    }

    std::vector<std::string> content_words;
    ns_util::JiebaUsutl::CutString(doc.content, &content_words);
    for (auto& cw : content_words) {
        boost::to_lower(cw);
        word_map[cw].content_cnt++;
    }

    #define X 10
    #define Y 1
    for (auto& word_pair : word_map) {
        InvertedElem item;
        item.doc_id = doc.doc_id;
        item.word = word_pair.first;
        item.weight = X * word_pair.second.title_cnt + Y * word_pair.second.content_cnt;
        inverted_index[word_pair.first].push_back(item);
    }
    return true;
}

3.3 批量构建索引

以二进制方式读取输入文件，逐行处理并调用上述函数。

bool BuildIndex(const std::string& input) {
    std::ifstream in(input, std::ios::in | std::ios::binary);
    if (!in.is_open()) {
        std::cout << input << "open error" << std::endl;
        return false;
    }

    int count = 0;
    std::string line;
    while (std::getline(in, line)) {
        DocInfo* doc = BuildForwardIndex(line);
        if (doc == nullptr) {
            std::cout << "BuildIndex error" << std::endl;
            continue;
        }
        BuildInvertedIndex(*doc);
        count++;
        if (count % 50 == 0) LOG1(NORMAL, "索引建立到：" + std::to_string(count));
    }
    return true;
}

4. 获取索引数据

4.1 获取正排索引

增加边界检查以确保安全性。

DocInfo* GetForwardIndex(uint64_t doc_id) {
    if (doc_id >= forward_index.size()) {
        std::cout << "doc_id out range, error!" << std::endl;
        return nullptr;
    }
    return &forward_index[doc_id];
}

4.2 获取倒排索引

倒排索引查找涉及哈希表遍历，返回关键词对应的文档 ID 列表。

InvertedList* GetInvertedList(const std::string& word) {
    auto iter = inverted_index.find(word);
    if (iter == inverted_index.end()) {
        std::cout << word << "get error" << std::endl;
        return nullptr;
    }
    return &(iter->second);
}

5. 总结

本文档系统梳理了搜索引擎正倒排索引模块的设计思路、数据结构、实现流程及核心接口。完整代码如下：

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <fstream>
#include <mutex>
#include "usuallytool.hpp"
#include <boost/algorithm/string.hpp>
#include "log.hpp"

namespace ns_index {
    typedef struct DocInfo {
        std::string title;
        std::string content;
        std::string url;
        int doc_id;
    } DocInfo;

    struct InvertedElem {
        int doc_id;
        std::string word;
        int weight;
    };
    typedef std::vector<InvertedElem> InvertedList;

    class Index {
    private:
        std::vector<DocInfo> forward_index;
        std::unordered_map<std::string, InvertedList> inverted_index;

        Index() {};
        Index(const Index&) = delete;
        Index& operator=(const Index&) = delete;
        static Index* instance;
        static std::mutex log;

    public:
        ~Index();

        static Index* Getinstance() {
            if (instance == nullptr) {
                log.lock();
                if (instance == nullptr) {
                    instance = new Index();
                }
                log.unlock();
            }
            return instance;
        }

        DocInfo* GetForwardIndex(uint64_t doc_id) {
            if (doc_id >= forward_index.size()) {
                std::cout << "doc_id out range, error!" << std::endl;
                return nullptr;
            }
            return &forward_index[doc_id];
        }

        InvertedList* GetInvertedList(const std::string& word) {
            auto iter = inverted_index.find(word);
            if (iter == inverted_index.end()) {
                std::cout << word << "get error" << std::endl;
                return nullptr;
            }
            return &(iter->second);
        }

        bool BuildIndex(const std::string& input) {
            std::ifstream in(input, std::ios::in | std::ios::binary);
            if (!in.is_open()) {
                std::cout << input << "open error" << std::endl;
                return false;
            }
            int count = 0;
            std::string line;
            while (std::getline(in, line)) {
                DocInfo* doc = BuildForwardIndex(line);
                if (doc == nullptr) {
                    std::cout << "BuildIndex error" << std::endl;
                    continue;
                }
                BuildInvertedIndex(*doc);
                count++;
                if (count % 50 == 0) LOG1(NORMAL, "索引建立到：" + std::to_string(count));
            }
            return true;
        }

    private:
        DocInfo* BuildForwardIndex(const std::string& line) {
            std::vector<std::string> results;
            ns_util::StringUtil::Split(line, &results, "\3");
            if (results.size() != 3) return nullptr;
            DocInfo doc;
            doc.title = results[0];
            doc.content = results[1];
            doc.url = results[2];
            doc.doc_id = forward_index.size();
            forward_index.push_back(doc);
            return &forward_index.back();
        }

        bool BuildInvertedIndex(const DocInfo& doc) {
            struct word_cnt {
                int title_cnt;
                int content_cnt;
                word_cnt() : title_cnt(0), content_cnt(0) {}
            };
            std::unordered_map<std::string, word_cnt> word_map;
            std::vector<std::string> title_words;
            ns_util::JiebaUsutl::CutString(doc.title, &title_words);
            for (auto& tw : title_words) {
                boost::to_lower(tw);
                word_map[tw].title_cnt++;
            }
            std::vector<std::string> content_words;
            ns_util::JiebaUsutl::CutString(doc.content, &content_words);
            for (auto& cw : content_words) {
                boost::to_lower(cw);
                word_map[cw].content_cnt++;
            }
            #define X 10
            #define Y 1
            for (auto& word_pair : word_map) {
                InvertedElem item;
                item.doc_id = doc.doc_id;
                item.word = word_pair.first;
                item.weight = X * word_pair.second.title_cnt + Y * word_pair.second.content_cnt;
                inverted_index[word_pair.first].push_back(item);
            }
            return true;
        }
    };
    Index* Index::instance = nullptr;
    std::mutex Index::log;
}