搜尋引擎的實作
- 項目簡介
-
- 項目背景
- 項目開始前
-
- 開始前的準備
- 四個子產品
-
- 預處理子產品
- 索引子產品
- 搜尋子產品
- 伺服器子產品
項目簡介
這裡所實作的并非如同百度、谷歌一樣的全網搜尋，我們的硬體條件達不到，并且技術實力也不夠，但是我們可以按照搜尋引擎的基本原理，來實作一個站内搜尋，實作原理也算是大同小異，此項目分為四個子產品：預處理子產品、索引子產品、搜尋子產品、伺服器子產品
項目背景
想要寫一個搜尋引擎也是源于偶然，在知乎上看到一篇文章，說是百度搜尋為什麼可以那麼快？回答裡說了很多方面的技術，其中最核心的就是反向索引，這讓我産生了濃厚的興趣，但是因為實力和裝置都有欠缺，沒法做一個像是百度和搜狗一樣的全網搜尋，但我可以做一個站内搜尋，來了解相應的技術。
項目開始前
雖然我們要實作的是站内搜尋，但是與全網搜尋大同小異，那麼我們可以看一看搜尋應該要包含什麼
我們可以看到當我們在上面的文本框輸入
關鍵字
之後點選搜尋，在下面會顯示出許多具有相關性的搜尋結果，而這些搜尋結果中至少需要包含以下四個部分：
标題
描述（網頁正文摘要出一部分）
展示url
點選url，點選标題會跳轉到另外一個url中
是以我們可以仿照百度的方式，來實作我們的搜尋引擎
開始前的準備
httplib
g++版本必須得是4.9以上
jieba分詞的庫
用這個庫的時候直接用include是不夠的，需要将
deps
目錄下的
limonp
也拷貝到include目錄下
boost： yum install boost-devel.x86_64
jsoncpp： yum install jsoncpp-devel.x86_64
建立這樣的一個目錄結構
四個子產品
預處理子產品
這裡就要提一下我為什麼會選擇boost網站來實作站内搜尋了，
- 我們暫時無法實作一個全網搜尋，隻能完成站内搜尋
- boost官方文檔沒有一個搜尋功能，但是boost文檔很常用，沒有搜尋功能比較麻煩
- boost文檔提供了兩個版本，
離線版本
線上版本
boost 線上文檔.
我為什麼選擇1.53版本的boost呢？其實主要是因為我用的Linux版本是contos7，它預設就是1.53
那麼我們現在得到了boost文檔的離線版本之後需要幹什麼呢？
我們下載下傳下來的boost文檔，其實就是一個個的html，而這些html裡面是有很多内容和标簽混合在一起的，而我們需要的隻是其中的
标題
，
正文
，
url
，而我們預處理階段所要做的就是讀取原始的html文檔内容，提取我們所要的，整理成一個行文本，以供下面的子產品使用
接下來我們就開始寫預處理子產品的代碼了
首先我們需要定義兩個變量來表示從哪裡讀資料和要把最後生成的行文本放到哪個路徑下面展示一些
内聯代碼片
。
這個變量表示從哪個目錄中讀取boost文檔的html
這個變量表示預處理子產品輸出結果放到哪裡
我們還需要一個結構體，來表示一個個的html
struct DocInfo{
string title;//文檔的标題
string url;//文檔的url
string content;//文檔的正文
};
既然我們要将所有的html都解析成行檔案，那麼我們首要做的就是将所下載下傳的所有html都枚舉加載進來，那麼我們就可以封裝一個函數
其中input_path為輸入參數，file_list是輸出參數，将上面定義的輸入變量傳進來，然後将所有的html都枚舉到輸出參數file_list中。我們的枚舉過程中是會遇到目錄的，而我們隻要枚舉html，C++的标準庫中沒有能做到這個的，但是boost庫中可以。
//把boost::filesystem這個命名空間定義一個别名
39 namespace fs = boost::filesystem;
40 fs::path root_path(input_path);
41 if(!fs::exists(root_path)){
42 std::cout << "目前的目錄不存在" << std::endl;
43 }
44
45 //遞歸目錄疊代器，疊代器使用循環實作的時候可以自動完成遞歸
46
47 fs::recursive_directory_iterator end_iter;
48 for(fs::recursive_directory_iterator begin_iter(root_path); begin_iter != end_iter; ++begin_iter){
49 //需要判定目前的路徑對應的是不是一個普通檔案
50 //如果是目錄直接跳過
51 if(!fs::is_regular_file(*begin_iter))
52 {
53 continue;
54 }
55 //目前路徑對應的檔案是不是一個html檔案，如果不是也跳過
56 if(begin_iter->path().extension() != ".html"){
57 continue;
58 }
59
60 //把得到的html加入到最終結果的vector中
61 file_list->push_back(begin_iter->path().string());
接下來就是周遊vector裡面的html了，打開每一個html，然後解析其中的内容，解析出标題、正文、url，對應我們之前建立好的結構體
找到标題
70 //找到html中的title标簽
71 bool ParseTitle(const string& html, string *title){
72 size_t beg = html.find("<title>");
73 if(beg == string::npos){
74 std::cout << "标題未找到" << std::endl;
75 return false;
76 }
77 size_t end = html.find("</title>");
78 if(end == string::npos){
79 std::cout <<"标簽未找到" <<std::endl;
80 return false;
81 }
82 beg += string("<title>").size();
83 if(beg >= end){
84 std::cout <<"标題位置不合法" <<std::endl;
85 return false;
86 }
87 *title = html.substr(beg, end-beg);
88 return true;
89
90 }
擷取url
70 //找到html中的title标簽
71 bool ParseTitle(const string& html, string *title){
72 size_t beg = html.find("<title>");
73 if(beg == string::npos){
74 std::cout << "标題未找到" << std::endl;
75 return false;
76 }
77 size_t end = html.find("</title>");
78 if(end == string::npos){
79 std::cout <<"标簽未找到" <<std::endl;
80 return false;
81 }
82 beg += string("<title>").size();
83 if(beg >= end){
84 std::cout <<"标題位置不合法" <<std::endl;
85 return false;
86 }
87 *title = html.substr(beg, end-beg);
88 return true;
89
90 }
找到正文
101 //擷取正文
102 bool ParseContent(const string& html, string* content){
103 //這裡引入一個bool變量，當進入标簽之後，此值為false
104 //判斷這個變量就能知道是在标簽内還是在标簽外了
105 bool is_content = true;
106 for(auto c : html){
107 if(is_content){
108 //目前是正文
109 if(c == '<'){
110 is_content = false;
111 }
112 else{
113 //目前是普通字元，就把結果寫入到content中
114 if(c == '\n'){
115 c = ' ';
116 }
117 content->push_back(c);
118 }
119 }
120 else{
121 //目前是在标簽内
122 if(c == '>')
123 {
124 //标簽結束
125 is_content = true;
126 }
127 //标簽裡的其他内容都直接忽略掉
128 }
129 }
130 return true;
131 }
最後隻需要将我們解析出來的結果寫入到我們最開始設定好的輸出檔案中就可以了，不過要記得選擇一個不可見分隔符對标題、正文、url進行分割！！不然會出現粘包問題！！
以上就是預處理子產品的全部内容了，可以編譯運作一下，看看輸出檔案中是否如願解析出來了。
索引子產品
現在我們已經有了解析好的行文本了，那麼我們接下來就要進入索引子產品了，索引子產品是最核心的部分，在這個子產品我們就要引入反向索引了！！！
不管是站内搜尋還是全網搜尋，面對大量的資料，最核心的點就是效率，我們需要在大量的資料中，快速而準确的找出我們所要的資料，那麼解決這個問題，最核心的就是反向索引。
那麼什麼是反向索引呢？
我們來看一個經典的例子，我所學習反向索引的時候，就是看的這個例子
中文和英文等語言不同，單詞之間沒有明确分隔符号，是以首先要用分詞系統将文檔自動切分成單詞序列。這樣每個文檔就轉換為由單詞序列所組成，然後對每個不同的單詞賦予唯一的單詞編号，同時記錄下哪些文檔包含這個單詞，在如此處理結束後，我們可以得到最簡單的反向索引。
我們可以概括性的了解為：
正排索引就是利用文檔id來得到文本内容，反向索引就是根據文本内容來得到文本id
那麼我們的基本邏輯就是建構出正排索引，并且對字元串進行分詞切割，然後切分出來的單詞，再根據切分的單詞和正排索引建構反向索引，通過反向索引找到對應的文檔id，再通過文檔id查找正排索引，從正排索引找到文檔的内容。
是以我們現在要做的就是：建構正排索引，建構反向索引，進行分詞，查找反向索引，查找正排索引
下面我們建構一下正排索引和反向索引的基本結構體
23 struct DocInfo {
24 int64_t doc_id;
25 string title;
26 string url;
27 string content;
28 };
29
30 // 反向索引是給定詞, 映射到包含該詞的文檔 id 清單. (此處不光要有文檔 id,
31 // 還得有權重資訊, 以及該詞的内容)
32 struct Weight {
33 // 該詞在哪個文檔中出現
34 int64_t doc_id;
35 // 對應的權重是多少
36 int weight;
37 // 詞是什麼
38 string word;
39 };
這就是我們需要做的所有操作
37 typedef vector<Weight> InvertedList;
38
39 // Index 類用于表示整個索引結構, 并且提供一些供外部調用的 API
40 class Index {
41 private:
42 // 索引結構
43 // 正排索引, 數組下标就對應到 doc_id
44 vector<DocInfo> forward_index;
45 // 反向索引, 使用一個 hash 表來表示這個映射關系
46 unordered_map<string, InvertedList> inverted_index;
47
48 public:
49 Index();
50 // 提供一些對外調用的函數
51 // 1. 查正排
52 const DocInfo* GetDocInfo(int64_t doc_id);
53 // 2. 查倒排
54 const InvertedList* GetInvertedList(const string& key);
55 // 3. 建構索引
56 bool Build(const string& input_path);
57 // 4. 分詞函數
58 void CutWord(const string& input, vector<string>* output);
59
60 private:
61 DocInfo* BuildForward(const string& line);
62 void BuildInverted(const DocInfo& doc_info);
63
64 cppjieba::Jieba jieba;
65 };
接下來就具體實作一下，咱們先挑簡單的查正排和查倒排來實作一下
28 const DocInfo* Index::GetDocInfo(int64_t doc_id) {
29 if (doc_id < 0 || doc_id >= forward_index.size()) {
30 return nullptr;
31 }
32 return &forward_index[doc_id];
33 }
34
35 const InvertedList* Index::GetInvertedList(const string& key) {
36 auto it = inverted_index.find(key);
37 if (it == inverted_index.end()) {
38 return nullptr;
39 }
40 return &it->second;
41 }
這倆就是查找正排和倒排，查不到就傳回nullptr，查到了就傳回對應的指針即可
接下來要做的就是建構索引了
43 bool Index::Build(const string& input_path) {
44 // 1. 按行讀取輸入檔案内容(上個環節預處理子產品生成的 raw_input 檔案)
45 // 每一行又分成三個部分, 使用 \3 來切分, 分别是标題, url, 正文
46 std::cerr << "開始建構索引" << std::endl;
47 std::ifstream file(input_path.c_str());
48 if (!file.is_open()) {
49 std::cout << "raw_input 檔案打開失敗" << std::endl;
50 return false;
51 }
52 string line;
53 while (std::getline(file, line)) {
54 // 2. 解析成 正排結構的DocInfo 對象, 并構造為正排索引
55 DocInfo* doc_info = BuildForward(line);
56 if (doc_info == nullptr) {
57 std::cout << "建構正排失敗!" << std::endl;
58 continue;
59 }
60 // 3.構造成反向索引.
61 BuildInverted(*doc_info);
62
63 //此時需要知道進度是多少，但是如果每一個都進行列印
64 //每個資料都進行I/O操作的話過于影響效率
65 if (doc_info->doc_id % 100 == 0) {
66 std::cerr << doc_info->doc_id << std::endl;
67 }
68 }
69 std::cerr << "結束建構索引" << std::endl;
70 file.close();
71 return true;
72 }
這是整體的建構思路，我們接下來就分别完成反向索引和正排索引
=正排索引=
我們要做的核心操作: 按照
設定的分隔符
對
行文本
進行切分, 第一個部分就是
标題
, 第二個部分就是
url
, 第三個部分就是
正文
，然後将這三個部分填充到正排索引對應的結構體中即可。
77 DocInfo* Index::BuildForward(const string& line) {
78 // 1. 先把 line 按照 \3 切分成 3 個部分
79 vector<string> tokens;
80 common::Util::Split(line, "\3", &tokens);
81 if (tokens.size() != 3) {
82 return nullptr;
83 }
84 // 2. 把切分結果填充到 DocInfo 對象中
85 DocInfo doc_info;
86 doc_info.doc_id = forward_index.size();
87 doc_info.title = tokens[0];
88 doc_info.url = tokens[1];
89 doc_info.content = tokens[2];
90 forward_index.push_back(std::move(doc_info));
91 return &forward_index.back();
92 }
這裡的切分，在C++的标準庫中并沒有，但是boost庫中是有的，是以我們用boost庫中的split函數，不過這裡我将split封裝了一下，比boost庫中的split函數少了一個參數，也就是boost::token_compress_on：将連續多個分隔符當一個，預設沒有打開，當用的時候一般是要打開的。
boost:: token_compress_off：不會壓縮分割結果，連續的分隔符時會傳回 ""字元串
我預設選擇了compress_off因為也許有的html中的字段是空的，那我們也不能将其壓縮。
并且最後我選擇了将doc_info轉化成了右值（将亡值）進行了右值引用（效率就是一點點省出來的哦）
接下來就是建構反向索引了，而我們建構反向索引要做的首先就是建構正排和分詞，現在正排已經建構完畢了，那我們就需要分詞了，分詞我們選擇了
cppjieba分詞庫
來幫我們完成
147 void Index::CutWord(const string& input, vector<string>* output) {
148 jieba.CutForSearch(input, *output);
149 }
那麼我們現在終于可以開始期待已久的反向索引了
97 void Index::BuildInverted(const DocInfo& doc_info) {
98 // 建立專門用于統計詞頻的結構
99 struct WordCnt {
100 int title_cnt;
101 int content_cnt;
102 WordCnt() : title_cnt(0), content_cnt(0) {
103 }
104 };
105 unordered_map<string, WordCnt> word_cnt_map;
106 // 針對标題進行分詞
107 vector<string> title_token;
108 CutWord(doc_info.title, &title_token);
109 // 周遊分詞結果, 統計每個詞出現的次數
110 for (string word : title_token) {
111 //将隻是大小寫不同的詞當作同一個詞來處理
112 //是以都轉化成小寫
113 boost::to_lower(word);
114 ++word_cnt_map[word].title_cnt;
115 }
116 // 針對正文進行分詞
117 vector<string> content_token;
118 CutWord(doc_info.content, &content_token);
119 // 周遊分詞結果, 統計每個詞出現的次數
120 for (string word : content_token) {
121 boost::to_lower(word);
122 ++word_cnt_map[word].content_cnt;
123 }
124 // 填充Weight對象
125 for (const auto& word_pair : word_cnt_map) {
126 // 構造 Weight 對象
127 Weight weight;
128 weight.doc_id = doc_info.doc_id;
129 // 權重 = 标題出現次數 * 10 + 正文出現次數
130 weight.weight = 10 * word_pair.second.title_cnt + word_pair.second.content_cnt;
131 weight.word = word_pair.first;
132
133 // 把 weight 對象插入到反向索引中
134 InvertedList& inverted_list = inverted_index[word_pair.first];
135 inverted_list.push_back(std::move(weight));
136 }
137 }
整體思路就是将反向索引設定成一個hash表，key是關鍵詞，value 是倒排拉鍊 (包含若幹個 Weight 對象)，同時設定一個hash表，來統計詞頻key是關鍵詞，value是WordCnt結構體，是以統計出标題的詞頻和正文的詞頻，根據這兩者的詞頻算出權重，将權重和分詞結果、文檔id填入Weight對象，再将Weight對象填入到第一個hash表中。
以上就是索引部分的全部内容了。
搜尋子產品
上面我們建構好了索引子產品，現在我們的搜尋子產品就是要利用上面的索引，首先我們還是将這個子產品進行一個封裝
68 class Searcher {
69 private:
70 Index* index;
71
72 public:
73 Searcher() : index(new Index()) {
74 }
75 bool Init(const string& input_path);
76 bool Search(const string& query, string* results);
77
78 private:
79 string GenerateDesc(const string& content, const string& word);
80 };
這裡的對象是Index的一個指針，因為我們要使用到上一個類，而Init初始化也是這個用處
145 bool Searcher::Init(const string& input_path) {
146 return index->Build(input_path);
147 }
也就是将所有的正排索引和反向索引都建立好，以便我們接下來使用，接下來就是查詢倒排了，并且按照權重進行排序了
149 // 搜尋查詢詞, 得到搜尋結果.
150 bool Searcher::Search(const string& query, string* output) {
151 // 針對查詢詞進行分詞
152 vector<string> tokens;
153 index->CutWord(query, &tokens);
154 // 根據分詞結果, 查倒排, 把相關的文檔都擷取到
155 vector<Weight> all_token_result;
156 for (string word : tokens) {
157 boost::to_lower(word);
158 auto* inverted_list = index->GetInvertedList(word);
159 if (inverted_list == nullptr) {
160 continue;
161 }
162 // 将搜尋到的結果都合并到一起進行統一的排序
163 all_token_result.insert(all_token_result.end(), inverted_list->begin(), inverted_list->end());
164 }
165 std::sort(all_token_result.begin(), all_token_result.end(), [](const Weight& w1, const Weight& w2) {
166 return w1.weight > w2.weight;
167 });
然後用得到的文檔id，去查找正排，再将正排查到的行文本轉化成json格式以便我們使用，使用 jsoncpp 這個庫來實作 json 的操作.
170 Json::Value results;
171 for (const auto& weight : all_token_result) {
172 // 根據 weight 中的 doc_id 查正排
173 const DocInfo* doc_info = index->GetDocInfo(weight.doc_id);
174 // 把這個 doc_info 對象再進一步的包裝成一個 JSON 對象
175 Json::Value result;
176 result["title"] = doc_info->title;
177 result["url"] = doc_info->url;
178 result["desc"] = GenerateDesc(doc_info->content, weight.word);
179 results.append(result);
180 }
181 // 把得到的 results 這個 JSON 對象序列化成字元串. 寫入 output 中
182 Json::FastWriter writer;
183 *output = writer.write(results);
184 return true;
185 }
而這裡的desc，就是在網頁上所顯示的，文本的部分摘要的内容，而我們要用多少文本來作為摘要呢？
我們先根據正文, 找到 word 出現的位置. 以該位置為中心, 往前找 80 個位元組, 作為描述的起始位置.
再從起始位置開始往後找 160 個位元組, 作為整個描述. 這裡的取值完全根據個人自定義就行
187 string Searcher::GenerateDesc(const string& content, const string& word) {
188 // 1. 先找到 word 在正文中出現的位置.
189 size_t first_pos = content.find(word);
190 size_t desc_beg = 0;
191 if (first_pos == string::npos) {
192 // 如果找不到, 就直接從頭開始作為起始位置.
193 if (content.size() < 160) {
194 return content;
195 }
196 string desc = content.substr(0, 160);
197 desc[desc.size() - 1] = '.';
198 desc[desc.size() - 2] = '.';
199 desc[desc.size() - 3] = '.';
200 return desc;
201 }
202 // 2. 找到了 first_pos 位置, 以這個位置為基準, 往前找一些位元組.
203 desc_beg = first_pos < 80 ? 0 : first_pos - 80;
204 if (desc_beg + 160 >= content.size()) {
205 // desc_beg 後面的内容不夠 160 了, 直接到末尾結束即可
206 return content.substr(desc_beg);
207 } else {
208 string desc = content.substr(desc_beg, 160);
209 desc[desc.size() - 1] = '.';
210 desc[desc.size() - 2] = '.';
211 desc[desc.size() - 3] = '.';
212 return desc;
213 }
214 }
這就是搜尋子產品所實作的所有功能了，像是測試，我就不在這裡寫了，不過完成每一個子產品的時候都要測試一下，不要最後發現出錯了都不知道去哪裡找
伺服器子產品
接下來就是最後的一個子產品了，伺服器子產品，這裡我們就用cpp-httplib庫來搭建伺服器了，就不自己手動用stocket套接字搭建了，根據項目文檔來使用即可，這裡我就不多介紹了
25 Server server;
26 server.Get("/searcher", [&searcher](const Request& req, Response& resp) {
27 if (!req.has_param("query")) {
28 resp.set_content("您發的請求參數錯誤", "text/plain");
29 return;
30 }
31 string query = req.get_param_value("query");
32 string results;
33 searcher.Search(query, &results);
34 resp.set_content(results, "application/json");
35 });
先建立Server對象，然後調用Get函數，這個函數有兩個參數，第一個表示的是，你要用哪個http路徑來觸發get操作，第二個參數是一個lambda表達式，是一個回調函數，也就是當伺服器收到第一個參數的請求的時候，會觸發回調函數的操作，Request就是請求，Response就是相應，我們收到請求之後就可以解析請求，根據請求内容，來完成響應。set_content就是将我們的結果寫到響應的body中，然後傳回，他的第二個參數就是傳回的body的資料格式，text/plain就是純文字，application/json就是json格式。
最後将我們的所做的前端頁面，也就是靜态資源挂載就可以了。
36 // 告訴伺服器, 靜态資源存放在 wwwroot 目錄下. (html, css, js, 圖檔....)
37 server.set_mount_point("/", "./ShySearcher");
38 // 3. 啟動伺服器
39 server.listen("0.0.0.0", 10001);
我前端做的不太好，也就不給大家展示了。
咱們的站内搜尋引擎也基本就結束了。