【Boost搜索引擎】上

1. 为什么要做这个项目

目前我们熟知的搜索引擎有：百度，360，搜狗等，它们所作的都是全网搜索 。而我们接下来做的是站内搜索，搜索数据更垂直，数据量其实更小。以前Boost库是没有搜索的，不过现在是有了，但没关系，重要的是虽然我们做的是Boost搜索引擎，但如果掌握了，可以改成任何一个搜索引擎。

我们可以先看看一个搜索引擎给它关键字给我们显现出来的东西。

可以看到主要呈现的东西有标题、摘要、网址。后面我们实现的搜索引擎也要呈现这样的效果。

2. 搜索引擎相关宏观原理

在一个服务器集群/服务器里磁盘某个路径下放着从全网爬下来的资源。有个searcher进程再跑。

第一步：对这个路径下的文件进行去标签+数据清理
第二步：建立索引（方便快速查找）

当用户发起一个http请求，通过GET方法提交搜索关键字，发起搜索任务

第三步：检索索引得到相关html

拼接多个网页的title+desc+url，构建一个新的网页，返回给用户

目前我们大致了解一下流程即可。

3. 搜索引擎技术栈和项目环境

• 技术栈: C/C++ C++11, STL, 准标准库Boost，Jsoncpp，cppjieba，cpp-httplib
• 选学： html5，css，js、jQuery、Ajax
• 项目环境：ubentu20.04 云服务器，gcc(g++)/Makefile , vs code

4. 正排索引 vs 倒排索引 - 搜索引擎具体原理

比如说目前我们有两个文档：

• 文档1：雷军发布了小米汽车
• 文档2：雷军买了四斤小米

所谓正排索引：就是根据文档ID找到文档内容(文档内的关键字)

建立倒排索引，之前我们要先对文档进行分词，（目的：方便建立倒排索引和查找）

• 文档1：[雷军发布了小米汽车]： 雷军/发布/小米/汽车/小米汽车
• 文档2：[雷军买了四斤小米]： 雷军/买/四斤/小米/四斤小米

停止词：了，的，吗，a，the，⼀般我们在分词的时候可以不考虑。

倒排索引：根据文档内容，分词，整理不重复的各个关键字，对应联系到文档ID的方案

关于权值也是有必要的，我们搜索一个关键字，就会从上到下给我们很多条搜索结果，那谁在前谁在后呢？这里我们简单一点，就以权值来衡量搜索谁在前谁在后。当前真实情况就是动用钞能力了。。。

模拟一次搜索引擎查找的过程：

用户输入：小米 -> 先倒排索引中查找 -> 提取出文档ID(1,2) -> 在去正排索引中查找 -> 找到对应文档的内容 -> title+conent（desc）+url 文档结果进行摘要 -> 构建响应结果

接下来我们正式编写我们的代码，我们一模块一模块的进行编写。

5. 编写数据去标签与数据清洗的模块 Parser

首先你得要有boost库数据才行。boost库

我们可以下载最新的版本，然后拉到你得linux中，

解压压缩包，会得到这个东西

大部分 .html都在 doc/html目录下，目前只需要boost_1_87_0/doc/html目录下的html文件，用它来进行建立索引

这里我把它拷贝到自己项目下的boost_search/data/input路径下

然后你刚才下载的boost库你就可以删了。

5.1 去标签

html的标签，这个标签对我们进行搜索是没有价值的，需要去掉这些标签，一般标签都是成对出现的！

我们要去标签，主要是为了得到里面有效内容，它们是我们建立索引需要的东西。

我们把去标签之后的干净内容放raw.txt文档中

这里要注意我们把内容写进文档，未来也要建立索引也要进行读取。为了方便读取，文档内的内容以\3进行分割，文档和文档直接用\n进行分割。

类似：title\3content\3url \n title\3content\3url \n title\3content\3url \n …

这样的话未来我们使用getline(ifsream, line)，直接一行一行获取文档的全部内容 title\3content\3url

5.2 编写parser

未来公用类的都放在Conmon.h头文件里。

//Common.h
#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<fstream>

using std::cout;
using std::cerr;
using std::endl;

//Parser.cc
#inclide"Common.h"

//源数据所有html文件的路径
static const std::string src_path = "data/input";
//源数据去标签+数据清理之后的路径
static const std::string output = "data/raw_html/raw.txt";


typedef struct DocInfo
{
    std::string title;   //文档的标题
    std::string content; //文档的摘要
    std::string url;     //该文档在官网的url
}DocInfo_t;


//const &: 输入
//*: 输出
//&：输入输出
bool EnumFile(const std::string &src_path, std::vector<std::string> *files_list);
bool ParserHtml(const std::vector<std::string> &files_list, std::vector<DocInfo_t> *results);
bool SaveHtml(const std::vector<DocInfo_t> &results, const std::string &output);


int main()
{
    std::vector<std::string> files_list;
    // 第一步: 递归式的把每个html文件名带路径,保存到files_list,方便后期进行一个个的文件读取
    if (!EnumFile(src_path, &files_list))
    {
        cerr << "enum file name fail" << endl;
        return 1;
    }

    std::vector<DocInfo_t> results;
    // 第二步: 根据files_list读取每个文件的内容,并进行解析
    if (!ParserHtml(files_list, &results))
    {
        cerr << "parser html fail" << endl;
        return 2;
    }

    // 第三步: 把解析完的各个文件内容,写入到output,按照\3作为每个文档内部分割符,\n作为每个文档的分割符
    if (!SaveHtml(results, output))
    {
        cerr << "save html fail" << endl;
        return 3;
    }
    return 0;
}

如何递归式的把每个html文件名带路径都拿到呢？这里我们可以使用boost库的方法。

通过apt-get命令安装libboost-all-dev包

sudo apt-get update
sudo apt-get install libboost-all-dev

安转好之后，默认安装目录为/usr，
默认头文件安装目录在 /usr/include/boost
默认so库文件安装目录在/usr/lib/x86_64-linux-gnu

安装之后我们就可以写了

bool EnumFile(const std::string &src_path, std::vector<std::string> *files_list)
{
    namespace fs = boost::filesystem;
    fs::path root_path(src_path);

    // 判断路径是否存在,如果不存储就没有必要往后走了
    if (!fs::exists(root_path))
    {
        //cout << root_path << "not exists" << endl;
        LOGMESSAGE(FATAL,src_path + "not exists");
        return false;
    }

    // 定义一个空的迭代器,用来判断递归结束
    fs::recursive_directory_iterator end;
    for (fs::recursive_directory_iterator start(root_path); start != end; ++start)
    {
        // 判断文件是否是普通文件,.html结尾是普通文件
        if (!fs::is_regular_file(*start))
        {
            continue;
        }

        // 判断文件路径的后缀是否符合要求
        if (start->path().extension() != ".html")
        {
            continue;
        }

        // cout << "debug: " << start->path().string() << endl;

        // 当前的路径一定是一个合法的，以.html结束的普通网页文件
        // 将所有带路径的html保存在files_list,方便后续进行文本分析
        files_list->push_back(start->path().string());
    }

    return true;
}

当前已经把所有.html文件名带路径都放到files_list中，然后我们就可以依次读每条路径把每个文档的内容拿出来，进行分割。

//Common.h

class Util
{
public:
    //从文件中读取内容
    static bool ReadFile(const std::string& file_path, std::string* out)
    {
        std::ifstream ifs(file_path);

        if(!ifs.is_open())
        {
            cerr << "open file" << file_path << "fail" <<endl;
            return false;
        }

        std::string line;
        while(getline(ifs,line))
        {
            *out += line;
        }

        ifs.close();
        return true;
    }

};

//Parser.cc

bool ParserHtml(const std::vector<std::string> &files_list, std::vector<DocInfo_t> *results)
{
    for (const auto &path : files_list)
    {
        // 1. 读取文件
        std::string result;
        if (!Util::ReadFile(path, &result))
        {
            continue;
        }

        DocInfo_t doc;
        // 2.解析指定文件,提取title
        if (!ParserTitle(result, &doc.title))
        {
            continue;
        }

        // 3.解析指定文件,提取content,就是去标签
        if (!ParserContent(result, &doc.content))
        {
            continue;
        }

        // 4.解析指定文件路径,构建url
        if (!ParserUrl(path, &doc.url))
        {
            continue;
        }

        // done,一定是完成了解析任务，当前文档的相关结果都保存在了doc里面
        // results->push_back(std::move(doc))//bug:todo;细节，本质会发生拷贝，效率可能会比较低
        results->push_back(std::move(doc)); // 拷贝变移动

        // for debug
        //ShowDoc(doc);
        //break;
    }

    return true;
}

提取title

bool ParserTitle(const std::string &file, std::string *title)
{
    auto begin = file.find("<title>");
    if (begin == std::string::npos)
    {
        return false;
    }

    auto end = file.find("</title>");
    if (end == std::string::npos)
    {
        return false;
    }

    begin += std::string("<title>").size();

    if (begin >= end)
    {
        return false;
    }

    *title = file.substr(begin, end - begin);
    return true;
}

提取content(本质就是在 去标签)

这里我们用个简易的状态机，最开始的状态就是在 < 标签，然后一个个字符读取，遇到 > 标签之后可能下一个就属于content就拿，也有可能是 < 标签不能拿。所以每拿一个字符都要重新判断状态。

bool ParserContent(const std::string &file, std::string *content)
{
    // 写个状态机用来区分当前是在标签还是在内容
    enum status
    {
        LABLE,  // 标签
        CONTENT // 内容
    };

    // 刚开始指向标签
    enum status s = LABLE;
    for (auto c : file)
    {
        switch (s)
        {
        case LABLE:
            if (c == '>')
            {
                s = CONTENT;
            }
            break;
        case CONTENT:
            if (c == '<')
            {
                s = LABLE;
            }
            else
            {
                // 我们不想保留原始文件中的\n,因为我们想用\n作为html解析之后文本的分隔符
                if (c == '\n')
                    c = ' ';
                *content += c;
            }
            break;
        default:
            break;
        }
    }
    return true;
}

提取url

boost库的官方文档，和我们下载下来的文档，是有路径的对应关系的。

官网：

https://www.boost.org/doc/libs/1_87_0/doc/html/accumulators.html

我们下载下来的url样例：

boost_1_78_0/doc/html/accumulators.html

我们拷贝到我们项目中的样例：

data/input/accumulators.html

想把我们的路径变成官网url，我们就拼接一下，相当于形成了一个官网链接

bool ParserUrl(const std::string &file_path, std::string *url)
{
    std::string url_head = "https://www.boost.org/doc/libs/1_87_0/doc/html";
    std::string url_tail = file_path.substr(src_path.size());

    *url = url_head + url_tail;
    return true;
}

将解析内容写入文件中

bool SaveHtml(const std::vector<DocInfo_t> &results, const std::string &output)
{
#define SEP '\3'
    //按照二进制方式进行写入
    std::ofstream ofs(output,std::ios::out | std::ios::binary);
    if(!ofs.is_open())
    {
        cerr << "open" << output << "fail" <<endl;
        return false;
    }
    
    //就可以进行文件内容的写入了
    for(auto& doc : results)
    {
        std::string out_string;
        out_string = doc.title;
        out_string += SEP;
        out_string += doc.content;
        out_string += SEP;
        out_string += doc.url;
        out_string += '\n';
        ofs.write(out_string.c_str(),out_string.size());

    }
    ofs.close();

    return true;
}

6. 编写建立索引的模块 Index

目前已经把处理好的所有文档内容都放在raw.txt中了，下面我们可以从这里拿内容建立正排索引和倒排索引了。

//Index.hpp

#include "Common.h"

// 正排索引文档Id对应文档的内容
typedef struct DocInfo
{
    std::string title;   // 文档的标题
    std::string content; // 文档的内容
    std::string url;     // 该文档在官网的url
    uint64_t doc_id;     // 文档ID,建立倒排排序需要用到
} DocInfo;

// 倒排索引分词对应的文档ID和权重
typedef struct InvertedElem
{
    uint64_t doc_id;//文档id
    std::string word;//关键字,等会对文档内容做摘要要用
    int weight;//权重

    InvertedElem() :doc_id(0), weight(0) {}

} InvertedElem;

// 倒排拉链
typedef std::vector<InvertedElem> InvertedList;

class Index
{
private:
    // 正排索引的数据结构使用数组,数组的下标天然就是文档ID
    std::vector<DocInfo> forward_index; // 正排索引
    // 倒排索引一定是一个关键字和一个或者多个InvertedElem对应关系(关键字和倒排拉链的映射关系)
    std::unordered_map<std::string, InvertedList> inverted_index;

public:

    // 根据doc_id找到文档内容
    DocInfo *GetForwardIndex(const uint64_t doc_id)
    {
        return nullptr;
    }

    // 根据关键字stirng,获得倒排拉链
    InvertedList *GetInvertedIndex(const std::string &word)
    {
        return nullptr;
    }

    // 根据data/raw_html/raw_txt去标签,得到的文档内容,构建正排索引和倒排索引
    bool BuildIndex(const std::string& output) // parse处理完毕的数据交给我
    {
 
        return true;
    }
};

先把根据文档ID得到文档内容，和根据关键字得到倒排拉链，以及读一行建立正排索引和倒排索引简单函数写一下。

// 根据doc_id找到文档内容
DocInfo *GetForwardIndex(const uint64_t doc_id)
{
    if (doc_id >= forward_index.size())
    {
        cerr << "doc_id out range,fail" << endl;
        return nullptr;
    }
    return &forward_index[doc_id];
}

// 根据关键字stirng,获得倒排拉链
InvertedList *GetInvertedIndex(const std::string &word)
{
    auto it = inverted_index.find(word);
    if (it == inverted_index.end())
    {
        cerr << word << "have no InvertedList" << endl;
        return nullptr;
    }
    return &inverted_index[word];
}

// 根据data/raw_html/raw_txt去标签,得到的文档内容,构建正排索引和倒排索引
bool BuildIndex(const std::string& output) // parse处理完毕的数据交给我
{
    std::ifstream ifs(output,std::ios::in | std::ios::binary);
    if(!ifs.is_open())
    {
        //cerr << "sorry, " << output << " open error" << endl;
        LOGMESSAGE(FATAL,"sorry" + output + "open error");
        return false;
    }

    std::string line;
    while(std::getline(ifs,line))
    {
    	//建立正排索引
        DocInfo* doc = BuildForwardIndex(line);

        if(doc == nullptr)
        {
            cerr << "build" << line <<"fail"<<endl;
            continue;
        }
		//建立倒排索引
        BuildInvertedIndex(*doc);
    }
    ifs.close();
    return true;
}

6.1 建立正排索引

每个文档内容都用 \3，用以区分一个文档内的title，desc，url，虽然可以用string自带的find找到每个起始位置，然后使用substr根据起始位置以及长度得到title，desc，url。但是这我们使用boost中的split函数比较方便。

第一个参数表示，切分后结果放哪里
第二个参数表示，要切分的内容
第三个参数表示，按什么切分
第四个参数表示，是否压缩

是否压缩意思是有一个字符串，aaa/3bbb/3/3/3/3ccc
如果压缩 aaa/3bbb/3/3/3/3ccc 切分后结果是 aaa bbb ccc
如果不压缩 aaa/3bbb/3/3/3/3ccc 切分后结果是 aaa bbb ccc，/3和/3之间表示一个空格，压缩就是把/3/3/3/3当从一个/3。

默认是把压缩关闭的。token_compress_on 打开压缩。

//Common.h
#include<boost/algorithm/string.hpp>

//使用boost库的函数,对字符串分割
class StringUtil
{
public:
    static void Spilt(const std::string &target, std::vector<std::string> *out, const std::string &sep)
    {
        boost::split(*out,target,boost::is_any_of(sep),boost::token_compress_on);
    }
};

//Index.hpp

DocInfo* BuildForwardIndex(const std::string& line)
    {
        // 1.对line进行分割
        // line -> title content url

        std::vector<std::string> results;//一行分割的结果
        std::string sep = "\3"; // 行内分割符
        StringUtil::Spilt(line,&results,sep);

        // 2.符串进行填充到DocIinfo
        DocInfo doc;
        doc.title = results[0];
        doc.content = results[1];
        doc.url = results[2];
        doc.doc_id = forward_index.size();//先进行保存id，在插入，id就是当前doc在vector中的下标!

         //3. 插入到正排索引的vector
        forward_index.push_back(std::move(doc));
        return &forward_index.back();

    }

6.2 建立倒排索引

每次建立一个正排索引之后，我们都把结果给拿到，然后去建立倒排索引。

//我们从正排索引拿到的⽂档内容
struct DocInfo{
	std::string title; //⽂档的标题
	std::string content; //⽂档对应的去标签之后的内容
	std::string url; //官⽹⽂档url
	uint64_t doc_id; //⽂档的ID，暂时先不做过多理解
};

//假设⽂档内容：
title ： 吃葡萄
content: 吃葡萄不吐葡萄⽪
url: http://XXXX
doc_id: 123

根据文档内容，形成一个或者多个InvertedElem(倒排拉链)
因为当前我们是一个一个文档进行处理的，一个文档会包含多个”词“， 都应当对应到当前的doc_id

1. 需要对 title && content都要先分词

title: 吃/葡萄/吃葡萄(title_word)
content：吃/葡萄/不吐/葡萄皮(content_word)

词和文档的相关性（词频：在标题中出现的词，可以认为相关性更高一些，在内容中出现相关性低一些）

2. 词频统计

struct word_cnt
{
	title_cnt;
	content_cnt;
}

unordered_map<std::string, word_cnt> word_cnt;

for &word : title_word{
	word_cnt[word].title_cnt++; //吃（1）/葡萄（1）/吃葡萄（1）
}

for &word : content_word {
	word_cnt[word].content_cnt++; //吃（1）/葡萄（1）/不吐（1）/葡萄⽪（1）
}

知道了在文档中，标题和内容每个词出现的次数

3. 自定义相关性

//把关键字从统计每个关键字和文档相关系的word_cnt拿出建立对应的倒排拉链
for &word : word_cnt{
	//具体一个词和123⽂档的对应关系，当有多个不同的词，指向同⼀个⽂档的时候，此时该优先显⽰谁？？相关性！
	struct InvertedElem elem;
	elem.doc_id = 123;
	elem.word = word.first;
	elem.weight = 10*word.second.title_cnt + word.second.content_cnt ; //相关性,我们这⾥拍着脑⻔写了
	//插入关键字对应的倒排拉链
	inverted_index[word.first].push_back(elem);
}

关于如何分词，这里我们使用cppjieba分词。

可以在gitee中搜索cppjieba，随便选一个点进去

然后在linux中使用git clone拉到本地

git clone https://gitee.com/lycium_pkg_mirror/cppjieba.git

不过cppjieba还有一个地方需要注意，还需要把limonp也要克隆到本地，

git clone https://github.com/yanyiwu/limonp.git

如果下载目前对应路径下应该有这两个目录，

下面我们要把limonp拷贝到cppjieba/include/cppjieba下，不然使用就会有问题，找不到对应文件。

最后在你自己项目下使用软链接的方式去链接一下头文件所在路径，不然编译会找不到头文件在哪里。或者你使用绝对路径比如#include “/home/wdl/thridpart/cppjieba/include/cppjieba”

//Common.h

#include"cppjieba/Jieba.hpp"

const char* const DICT_PATH = "./dict/jieba.dict.utf8";
const char* const HMM_PATH = "./dict/hmm_model.utf8";
const char* const USER_DICT_PATH = "./dict/user.dict.utf8";
const char* const IDF_PATH = "./dict/idf.utf8";
const char* const STOP_WORD_PATH = "./dict/stop_words.utf8";


class JiebaUtil
{
private:
    static cppjieba::Jieba jieba;
public:
    static void CutString(const std::string &src, std::vector<std::string> *out)
    {
        jieba.CutForSearch(src, *out);
    }

};
cppjieba::Jieba JiebaUtil::jieba(DICT_PATH, HMM_PATH, USER_DICT_PATH, IDF_PATH, STOP_WORD_PATH);

建立倒排索引，这里还有一点比如你搜索HELLO，hello，Hello，都会有hello的内容，这是因为搜索时忽略大小写了，因此我们在存关键字的时候也要忽略大小写，所以使用 boost::to_lower()把关键字变成小写在存

bool BuildInvertedIndex(const DocInfo& doc)
{
    //DocInfo{title, content, url, doc_id}

    //每个关键字在title和content出现的频次
    struct word_cnt
    {
        int title_cnt = 0;
        int content_cnt = 0;
    };

    //保存关键字和词频的映射关系
    std::unordered_map<std::string,word_cnt> word_map;

    //对标题进行分词
    std::vector<std::string> title_words;
    JiebaUtil::CutString(doc.title,&title_words);


    //对标题进行词频统计
    for(auto s : title_words)
    {
        //搜索的时忽略大小写,所以在倒排中的关键字也需要忽略大小写
        boost::to_lower(s); //需要统一转化成为小写
        word_map[s].title_cnt++;//如果存在就获取，如果不存在就新建
    }

    //对内容进行分词
    std::vector<std::string> content_words;
    JiebaUtil::CutString(doc.content,&content_words);

    
    //对内容进行词频统计
    for(auto s : content_words)
    {
        boost::to_lower(s); //需要统一转化成为小写
        word_map[s].content_cnt++;
    }

    //把在word_map的关键字放到倒排中
    for(auto& word_pair : word_map)
    {
        InvertedElem elem;
        elem.doc_id = doc.doc_id;
        elem.word = word_pair.first;
        elem.weight = 10*word_pair.second.title_cnt + word_pair.second.content_cnt;

        inverted_index[word_pair.first].push_back(std::move(elem));
    }

    return true;
}

Index这个类整个项目有一份就够了，因此我们可以把它写成单例模式

#pragma once
#include "Common.h"
#include <mutex>

// 正排索引文档Id对应文档的内容
typedef struct DocInfo
{
    std::string title;   // 文档的标题
    std::string content; // 文档的内容
    std::string url;     // 该文档在官网的url
    uint64_t doc_id;     // 文档ID,建立倒排排序需要用到
} DocInfo;

// 倒排索引分词对应的文档ID和权重
typedef struct InvertedElem
{
    uint64_t doc_id;
    std::string word;//关键字,等会对文档内容做摘要要用
    int weight;

    InvertedElem() : weight(0) {}

} InvertedElem;

// 倒排拉链
typedef std::vector<InvertedElem> InvertedList;

class Index
{
private:
    // 正排索引的数据结构使用数组,数组的下标天然就是文档ID
    std::vector<DocInfo> forward_index; // 正排索引
    // 倒排索引一定是一个关键字和一个或者多个InvertedElem对应关系(关键字和倒排拉链的映射关系)
    std::unordered_map<std::string, InvertedList> inverted_index;

private:
    //懒汉模式
    static Index* _Sint;
    static std::mutex _mtx;

    Index() {}
    Index(const Index&) = delete;
    Index& operator=(const Index&) = delete;

public:

    static Index* GetInstance()
    {
        if(_Sint == nullptr)
        {
            std::unique_lock<std::mutex> lock(_mtx);
            if(_Sint == nullptr)
            {
                _Sint = new Index;
            }
        }
        return _Sint;
    }
    
	//...
};
Index* Index::_Sint = nullptr;
std::mutex Index::_mtx;