Boost库搜索引擎项目（版本1）

Boost库搜索引擎

项目开源地址

Github：https://github.com/H0308/BoostSearchingEngine
Gitee：https://gitee.com/EPSDA/BoostSearchingEngine

版本声明

当前为最初版本，后续会根据其他内容对当前项目进行修改，具体见后续版本。
后续版本待更新

前置知识

了解搜索引擎

搜索引擎是一种信息检索系统，它能够自动从互联网或特定数据集合中收集、分析和组织信息，并根据用户的查询需求快速定位和返回相关结果。搜索引擎通常由爬虫、索引器和检索系统三大核心组件构成，实现数据采集、处理和高效查询

一般情况下，搜索引擎分为两种：

1. 站内搜索引擎：只在当前网站的内容之上进行搜索，实现难度较为容易
2. 全网搜索引擎：在整个互联网的内容之上进行搜索，实现难度大且维护成本高

本次只实现站内搜索，了解站内搜索基本原理再推测全网搜索的原理

分词

分词是将文本切分成有意义的基本单元（词语或词元）的过程，是搜索引擎和自然语言处理的基础环节

一般分词可以分为两种模式：

1. 全模式：切分出文本中所有可能成词的单元，不考虑语义合理性，特点是同一个字可能出现在多个词中，产生词语重叠。这种模式适合模糊匹配的需求，但是会产生大量冗余结果
2. 精确模式：只切分出最符合语义的词语组合，特点是每个字只会出现在一个词中，无重叠现象。这种模式下分词结果符合人类语义理解，但是依赖高质量词典或训练语料

例如，将“我来到北京清华大学”这段话，通过分词可以分为：

1. 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学（全模式）
2. 我/ 来到/ 北京/ 清华大学（精确模式）

本次项目中会使用分词技术查找出满足条件的文档

正排索引和倒排索引

正排索引（Forward Index）

正排索引是以文档为中心的索引结构：

• 定义：以文档ID为索引，文档内容为值的数据结构
• 结构：文档ID → 文档内容/词项集合
• 示例：

  文档1 → {标题:"Boost库简介", 内容:"Boost是一个C++库集合..."}
  文档2 → {标题:"C\+\+编程", 内容:"C\+\+是一种面向对象编程语言..."}
  

• 特点：
  • 适合已知文档ID时获取文档内容
  • 类似于图书馆中按编号排列的书架
  • 不利于根据关键词查找文档
  • 构建简单，存储效率低

倒排索引（Inverted Index）

倒排索引是以词项为中心的索引结构：

• 定义：以词项为索引，包含该词项的文档列表为值
• 结构：词项 → 文档ID列表(可能包含位置、频率等信息)
• 示例：

  "Boost" → {文档1: [位置1, 位置4], 文档3: [位置2]}
  "C++" → {文档1: [位置10], 文档2: [位置1, 位置5]}
  

• 特点：
  • 适合根据关键词快速查找相关文档
  • 类似于图书馆中的关键词目录
  • 支持高效的全文检索
  • 构建复杂，查询高效

两者对比与应用

特性	正排索引	倒排索引
查询方向	文档→词项	词项→文档
适用场景	文档展示和获取	关键词搜索
构建复杂度	低	高
查询效率	特定文档高	关键词搜索高
存储需求	大	相对小

实际搜索引擎通常同时使用两种索引：

• 用倒排索引快速找到匹配查询的文档集合
• 用正排索引获取匹配文档的完整内容以展示给用户

倒排索引是现代搜索引擎的核心数据结构，使得快速全文检索成为可能

项目准备

本次项目会使用到下面的内容：

1. 后端：C++、cpp-httplib开源库、Jieba分词、Jsoncpp
2. 前端：HTML、CSS和JavaScript
3. 搜索内容：1.78版本的Boost库中的doc/html中的内容
4. 日志：在Linux下实现的日志系统
5. 操作系统：Ubuntu 24.04（Linux）

1. 注意，这里的Boost库不要使用最新的，最新的Boost库中的HTML文件并不存在。另外，官网下载有的时候可能比较慢，可以使用本链接作为替代，这个链接是官方认可的资源站
2. 本项目中会用到C++ 17的filesystem和string_view，如果不了解请先看C++ 17 filesystem和C++ 17 string_view

实现思路

根据常见搜素引擎的搜索结果可以看出，一条结果一般包含下面三个内容：

1. 内容标题
2. 描述内容或者部分主体内容
3. 内容网址

但是直接从下载到的Boost库资源中可以看到都是HTML文件，直接从该文件中获取到上面三个内容就需要做最重要的一步：去除HTML文件中的标签留下纯文本内容，这便是本次实现的第一步：数据清洗

完成数据清洗之后就需要对构建搜索引擎做准备，首先需要完成的就是索引的构建，在前面提到了两种索引方式：正排索引和倒排索引，本次实现中也会包含这两种索引，根据两种索引的特点完成索引的构建

构建完成索引后就需要根据用户的输入查找索引给用户返回查找到的内容

最后，编写前端代码，完善服务端模块，客户端请求即可完成搜索

数据清洗

介绍

根据前面提到的一条搜索结果的构成可以分析出需要创建一个结构体包含这三个字段：

// 结果基本内容结构
struct ResultData
{
    std::string title; // 结构标题
    std::string body; // 结果内容或描述
    std::string url; // 网址
};

接着就是将一个正常HTML文件中的内容依次读取到结构体对应的字段中，下面分三步走：

1. 读取到源文件目录下所有的HTML文件，将其拼接为一个字符串存储到vector中
2. 根据上一步得到的vector中的数据，取出每一个文件中的三个字段：文档标题、文档内容和文档在Boost官网的URL都存放到一个结构化对象中，再将该对象存储到一个vector中
3. 根据上一步结果的vector中每一个结构化数据读取并写入到一个文本文档raw，每一个结构化数据以一个\n分隔，而其中的成员以\3分隔

下面是本次项目的目录结构：

- 根路径
    - data
        - source
            - html // 所有的HTML文件位于这里
        - raw // 结构化数据存储到这里
    // 头文件和源文件文件与data目录平级

接着，创建一个DataParse类，用于进行数据清洗：

class DataParse
{
private:
    
};

读取所有HTML路径

本步骤的基本思路就是获取到HTML路径存储到vector中，所以需要使用C++ 17中的filesystem库，也可以使用Boost库中提供的filesystem，二者在使用方式上都是一样的。

首先定义出当前HTML文件所在路径：

// HTML文件路径
const fs::path g_datasource_path = "data/source/html";

接着，实现函数读取到所有的HTML文件，如果不是HTML文件就不统计。因为当前HTML文件路径中存在目录，目录中还存在更多的HTML文件，所以还需要用到递归遍历目录

基于上面的思路，首先需要添加一个vector成员sources和获取HTML文件函数getHtmlSourceFiles：

class DataParse
{
public:
    // 获取HTML文件路径函数
    bool getHtmlSourceFiles()
    {

    }
private:
    std::vector<fs::path> sources;
};

读取思路：从g_datasource_path开始遍历，遇到后缀为HTML的文件就添加到sources中，如果遇到的是目录就进入目录继续查找，实现代码如下：

// HTML文件后缀
const std::string g_html_extension = ".html";

// 获取HTML文件路径函数
bool getHtmlSourceFiles()
{
    // 如果路径不存在，直接返回false
    if (!fs::exists(g_datasource_path))
    {
        ls::LOG(ls::LogLevel::DEBUG) << "不存在指定路径";
        return false;
    }
    
    // 递归目录结束位置，相当于空指针nullptr
    for (const auto &entry : fs::recursive_directory_iterator(g_datasource_path))
    {
        // 1. 不是普通文件就是目录，继续遍历
        if (!fs::is_regular_file(entry))
            continue;

        // 2. 是普通文件，但是不是HTML文件，继续遍历
        if (entry.path().extension() != g_html_extension)
            continue;

        // 3. 是普通文件并且是HTML文件，插入结果
        sources_.push_back(std::move(entry.path()));
    }

    // 空结果返回false
    return !sources_.empty();
}

读取HTML文件内容到结构体字段中

基本逻辑介绍

本部分的思路就是根据HTML文件中的特点提取出对应的内容，因为HTML文件的内容都是由标签和普通文本构成，而需要的内容就是文本，对应的行为就是去标签。本次实现分四步：

1. 读取文件
2. 截取标题
3. 截取主体内容
4. 构建URL

对于每一个HTML文件都需要走这四步，所以需要使用一个循环，通过一个函数readInfoFromHtml包裹主体逻辑：

// 读取HTML文件内容
bool readInfoFromHtml()
{
    // 不存在路径返回false
    if (sources_.empty())
    {
        ls::LOG(ls::LogLevel::WARNING) << "文件路径不存在";
        return false;
    }

    // 每一个文件都执行四步
    for (const auto &path : sources_)
    {
        std::string out; // 存储HTML文件内容
        struct pd::ResultData rd;
        // 1. 读取文件
        if (!readHtmlFile(path, out))
        {
            ls::LOG(ls::LogLevel::WARNING) << "打开文件：" << path << "失败";
            // 读取当前文件失败时继续读取后面的文件
            continue;
        }

        // 2. 获取标题
        if (!getTitleFromHtml(out, &rd.title))
        {
            ls::LOG(ls::LogLevel::WARNING) << "获取文件标题失败";
            continue;
        }

        // 3. 读取文件内容
        if (!getContentFromHtml(out, &rd.body))
        {
            ls::LOG(ls::LogLevel::WARNING) << "获取文件内容失败";
            continue;
        }

        // 4. 构建URL
        if (!constructHtmlUrl(path, &rd.url))
        {
            ls::LOG(ls::LogLevel::WARNING) << "构建文件URL失败";
            continue;
        }
    }

    return true;
}

最后，四个逻辑全部正常执行完后需要将形成的结构体对象插入到一个vector对象results_，此处需要一个添加类成员results_：

class DataParse
{
public:
    // ...

    // 从HTML文件中读取信息
    bool readInfoFromHtml()
    {
        // 不存在路径返回false
        if (sources_.empty())
        {
            ls::LOG(ls::LogLevel::WARNING) << "文件路径不存在";
            return false;
        }

        for (const auto &path : sources)
        {
            // ...

            results_.push_back(std::move(rd));
        }

        return true;
    }

private:
    // ...
    std::vector<pd::ResultData> results_;
};

接着，根据上面的函数主体，依次实现其中的四个函数

实现读取文件内容readHtmlFile

读取HTML文件内容比较简单，就是简单的读取文件内容操作，参考代码如下：

// 读取HTML文件
bool readHtmlFile(const fs::path &p, std::string &out)
{
    if (p.empty())
        return false;

    std::fstream f(p);

    if (!f.is_open())
        return false;

    // 读取文件
    std::string buffer;
    while (getline(f, buffer))
        out += buffer;

    f.close();

    return true;
}

实现读取文件标题getTitleFromHtml

因为一个标准的HTML文件中存在且只存在一个语义化标签<title></title>，所以只需要在文件中找到这个标签，并提取出其中的普通文本即可：

// 读取标题
// &为输入型参数，*为输出型参数
bool getTitleFromHtml(std::string &in, std::string *title)
{
    if(in.empty())
        return false;

    // 找到开始标签<title>
    auto start = in.find("<title>");
    if(start == std::string::npos)
        return false;

    // 找到终止标签</title>
    auto end = in.find("</title>");
    if (end == std::string::npos || start > end)
        return false;

    // 截取出其中的内容，左闭右开
    *title = in.substr(start + std::string("<title>").size(), end - (start + std::string("<title>").size()));

    return true;
}

实现读取文件内容getContentFromHtml

前面提到一个HTML文件只有两种内容：标签和普通文本，所以可以创建一个简单的状态机：如果当前的内容是标签，状态为Label，否则为OrdinaryContent，所以首先需要一个枚举类型描述这两个状态：

// 内容状态
enum ContentStatus
{
    Label, // 标签状态
    OrdinaryContent // 普通文本状态
};

接下来考虑何时进行两种状态的切换，默认从文件开始，读取到的内容就是<，所以默认状态为Label，而读取到>有三种情况：

1. 单标签的结尾
2. 双标签开始标签的结尾
3. 双标签闭合标签的结尾

而对于这三种情况，第三种情况和第一种情况可以归类为一种情况，因为这两种情况下都是作为当前标签的最后一个>，所以现在就变成了两种情况：

1. 双标签起始标签的结尾>
2. 当前标签的最后一个>

根据这两个情况以一个HTML内容为例进行分析：

<div>内容1</div>
<img />
内容2
<div>内容3</div>

以双标签为例，起始时，状态为Label，读取到第一个>时，得到一个条件：Label且>，假设此时可以修改状态为OrdinaryContent，那么接下来读取的就是文本内容，接着读取第一个到<时，得到下一个条件：OrdinaryContent且<，假设此时可以修改状态为Label，那么在读取到最后一个>时，状态为Label，即回到默认值Label继续读取后续内容

接着读取到单标签，状态为Label，得到一个条件：Label且<，根据上面的逻辑，不进行状态改变，接着读取到第一个>，得到一个条件：Label且>，根据上面的思路此时修改状态为OrdinaryContent，接下来读取文本内容，当读取到<div>内容3</div>的第一个<时，得到下一个条件：OrdinaryContent且<，根据上面的逻辑可以修改状态为Label，即回到默认值Label继续读取后续内容

所以，综上所述，状态切换时机为：

1. 当前状态为Label且遇到的是>，切换为OrdinaryContent
2. 当前状态为OrdinaryContent且遇到的是<，切换为Label

根据上面的逻辑，在函数中判断出状态为OrdinaryContent就可以执行插入内容，需要注意的是，后面需要使用\n作为分隔符，所以为了防止源文件内容中的\n干扰，需要将该\n替换为一个空格字符：

// 读取HTML文件内容
bool getContentFromHtml(std::string &out, std::string *body)
{
    // 默认状态为标签
    ContentStatus cs = ContentStatus::Label;

    // 注意，因为文档没有中文，直接用char没有问题
    for (char ch : out)
    {
        switch (cs)
        {
        // 读取到右尖括号且状态为标签说明接下来为文本内容
        case ContentStatus::Label:
            if(ch == '>')
                cs = ContentStatus::OrdinaryContent; // 切换状态
            break;
        case ContentStatus::OrdinaryContent:
            // 去除\n
            if (ch == '<')
                cs = ContentStatus::Label; // 切换状态
            else
            {
                if (ch == '\n')
                    *body += ' ';
                else 
                    *body += ch;
            }
            break;
        default:
            break;
        }
    }

    return true;
}

实现URL构建constructHtmlUrl

要构建一个有效的URL，就必须要将本地文件的路径和官网的路径进行对比，找出一个固定的值和可以改变的部分，例如以accumulators.html，在本地的路径和官网URL路径分别如下：

本地路径：data/source/html/accumulators.html
官网路径：https://www.boost.org/doc/libs/1_78_0/doc/html/accumulators.html

从上面的路径可以看出，只需要获取到本地路径中的最后一个文件内容/accumulators.html拼接到https://www.boost.org/doc/libs/1_78_0/doc/html后方即可

基于这个思路，实现下面的函数：

// 构建URL
bool constructHtmlUrl(const fs::path& p, std::string *url)
{
    // 在本地路径中找到"/文件"
    std::string t_path = p.string();
    auto pos = t_path.rfind("/");

    if(pos == std::string::npos)
        return false;
    
    // 从/开始截取一直到结尾
    std::string source_path = t_path.substr(pos);
    *url = g_url_to_concat + source_path;

    return true;
}

写入结构体对象数据到文本文件中

首先指定好文本文件的位置和分隔符：

// 文本文件路径
const fs::path g_rawfile_path = "data/raw";
// 结构体字段间的分隔符
const std::string g_rd_sep = "\3";
// 不同HTML文件的分隔符
const std::string g_html_sep = "\n";

接着就是基本的文件写入操作，但是为了保证不可打印字符可以正常显示，建议使用二进制写入的方式，函数实现如下：

// 将结构体字段写入文本文件中
bool writeToRawFile()
{
    // 以二进制形式打开文件
    std::fstream f(g_rawfile_path);

    if (!f.is_open())
    {
        ls::LOG(ls::LogLevel::WARNING) << "文本文件不存在";
        return false;
    }

    // 写入结构化数据
    for (auto &rd : results_)
    {
        std::string temp;
        temp += rd.title;
        temp += g_rd_sep;
        temp += rd.body;
        temp += g_rd_sep;
        temp += rd.url;
        temp += g_html_sep;

        f.write(temp.c_str(), temp.size());
    }

    f.close();

    return true;
}

构建正排索引和构建倒排索引

基本思路和结构介绍

因为正排索引和倒排索引最后都会筛选出一组数据，这个数据肯定包括前面封装的结构体ResultData；另外，因为不论是正排索引和倒排索引，最后都需要知道当前的文档ID，所以此处需要创建一个结构体，包含这里提到的两个字段：

struct SelectedDocInfo
{
    struct pd::ResultData rd;
    uint64_t id;
};

接着，为了创建一个类用于构建正排索引和倒排索引。在这个类中需要有两个成员，一个成员存储正排索引的结果，另外一个成员存储倒排索引的结果

首先考虑正排索引，正排索引只需要根据文档ID查询到文档的信息即可，而因为数组可以通过下标访问元素，这就可以保证文档ID与数组下标进行对应，将来查询时直接使用文档ID即可获取到指定的文章信息，所以存储正排索引的结构可以是一个动态数组，而每一个元素就是SelectedDocInfo结构体对象

接着是倒排索引，倒排索引是根据关键字进行构建的结果，而一个关键字可能对应着多个文章信息，所以这里首先需要一个有关当前关键字和相关文章的对应关系，也就是说，并不是直接通过关键字找出某一个文章信息，而是通过关键字对应的相关属性查询到具体的文章，这个属性包含文档ID、当前关键字和权重信息，通过权重信息筛选出结果后再根据其中的文档ID通过正排索引查询出对应的文章。根据这个思路，首先就需要一个用于保存关键字相关属性的结构：

// 倒排索引时当前关键字的信息
struct BackwardIndexElement
{
    uint64_t id; // 文档ID
    std::string word; // 关键字
    int weight; // 权重信息
};

接着，因为在查询时肯定需要用到获取方法，可能是获取正排索引，也可能是获取倒排索引，所以在类中需要提供两个函数用于获取当前正排索引的SelectedDocInfo对象和倒排索引中存储BackwardIndexElement对象数组，为了避免结构体对象的频繁拷贝，考虑返回对应节点的指针

考虑如何获取，对于正排索引来说，在前面介绍时已经提到是通过文档ID进行查询，所以获取时需要的参数就是文档ID；对于倒排索引来说，因为一个关键字可能对应着多个关键字信息节点BackwardIndexElement，对应的就需要用一个数组存储所有的信息节点，所以就需要建立一个哈希表用于关键字和关键字信息节点数组之间的映射关系，对应的获取时通过关键字获取到的就是关键字信息节点数组

=== “getForwardIndexDocInfo函数”

SelectedDocInfo *getForwardIndexDocInfo()
{
}

=== “getBackwardIndexElement函数”

// 获取倒排索引结果
std::vector<BackwardIndexElement> *getBackwardIndexElement()
{
}

接着，既然是建立索引，那么少不了的就是构建索引的函数。这个函数并不是只进行正排索引或者倒排索引，而是二者都进行，即当前函数包含着正排索引和倒排索引的主逻辑：

// 构建索引
bool buildIndex()
{

}

所以，当前用于构建索引的类的结构如下：

class SearchIndex
{
public:
    // 获取正排索引结果
    SelectedDocInfo *getForwardIndexDocInfo()
    {
    }

    // 获取倒排索引结果
    std::vector<BackwardIndexElement> *getBackwardIndexElement()
    {
    }

    // 构建索引
    bool buildIndex()
    {

    }

private:
    std::vector<SelectedDocInfo> forward_index_; // 正排索引结果
    std::unordered_map<std::string, std::vector<BackwardIndexElement>> backward_index_; // 倒排索引结果
};

实现构建索引函数

既然要构建索引，那么少不了的就是获取到用于构建索引的内容，而在上一步：数据清洗中已经将清洗后的数据存储到了一个文本文件中，所以当前构建索引函数只需要从该文件中读取数据即可。读取数据时需要根据写入时的格式和方式进行读取，因为当时是使用二进制的方式进行写入，那么读取时就需要使用二进制的方式读取；另外，在构建内容时，每一个ResultData对象之间都是以\n进行的分隔，所以在读取一个ResultData对象数据时就可以直接使用getline函数（该函数不会读取到用于分隔的\n）

接着，根据读取到的数据进行正排索引的构建和倒排索引的构建。这里的设计就涉及到前面提到的思路。首先，构建正排索引需要根据当前读取到的信息构建，所以参数需要传递一个当前读取到的信息，另外当前函数考虑返回一个SelectedDocInfo对象地址，只要这个对象地址不为空，就说明是成功构建一个了SelectedDocInfo对象，否则就不是。接着就是构建倒排索引，根据前面的思路，构建倒排索引需要使用到SelectedDocInfo对象中的文档ID值，所以构建倒排索引的函数需要传递一个SelectedDocInfo对象，而这个函数可以考虑返回一个布尔值

基于上面的思路，所以构建索引函数的基本逻辑如下：

// 构建索引
bool buildIndex()
{
    // 以二进制方式读取文本文件中的内容
    std::fstream in(pd::g_rawfile_path, std::ios::in | std::ios::binary);

    if(!in.is_open())
    {
        ls::LOG(ls::LogLevel::WARNING) << "打开文本文件失败";
        return false;
    }

    // 读取每一个ResultData对象
    std::string line;
    while(getline(in, line))
    {
        // 构建正排索引
        struct SelectedDocInfo* s = buildForwardIndex(line);
        if(s == nullptr)
        {
            ls::LOG(ls::LogLevel::WARNING) << "构建正排索引失败";
            continue;
        }

        // 构建倒排索引
        bool flag = buildBackwardIndex(*s);

        if(!flag)
        {
            ls::LOG