搜索引擎的實作
- 專案簡介
- 專案背景
- 專案開始前
- 開始前的準備
- 四個模塊
- 預處理模塊
- 索引模塊
- 搜索模塊
- 服務器模塊
專案簡介
這里所實作的并非如同百度、谷歌一樣的全網搜索，我們的硬體條件達不到，并且技術實力也不夠，但是我們可以按照搜索引擎的基本原理，來實作一個站內搜索，實作原理也算是大同小異，此專案分為四個模塊：預處理模塊、索引模塊、搜索模塊、服務器模塊
專案背景
想要寫一個搜索引擎也是源于偶然，在知乎上看到一篇文章，說是百度搜索為什么可以那么快？回答里說了很多方面的技術，其中最核心的就是倒排索引，這讓我產生了濃厚的興趣，但是因為實力和設備都有欠缺，沒法做一個像是百度和搜狗一樣的全網搜索，但我可以做一個站內搜索，來理解相應的技術，
專案開始前
雖然我們要實作的是站內搜索，但是與全網搜索大同小異，那么我們可以看一看搜索應該要包含什么
我們可以看到當我們在上面的文本框輸入關鍵字之后點擊搜索，在下面會顯示出許多具有相關性的搜索結果，而這些搜索結果中至少需要包含以下四個部分：
標題
描述（網頁正文摘要出一部分）
展示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提供了離線版本，那么我們就可以基于離線版本，分析檔案頁面的內容，為搜索功能提供支持，點擊搜索結果的標題的時候，就能夠跳轉到在線版本的檔案上，而如果網站內容無法直接下載，就必須使用爬蟲來抓取頁面到本地，
boost 在線檔案.
我為什么選擇1.53版本的boost呢？其實主要是因為我用的Linux版本是contos7，它默認就是1.53
那么我們現在得到了boost檔案的離線版本之后需要干什么呢？
我們下載下來的boost檔案，其實就是一個個的html，而這些html里面是有很多內容和標簽混合在一起的，而我們需要的只是其中的標題，正文，url，而我們預處理階段所要做的就是讀取原始的html檔案內容，提取我們所要的，整理成一個行文本，以供下面的模塊使用
接下來我們就開始寫預處理模塊的代碼了
首先我們需要定義兩個變數來表示從哪里讀資料和要把最后生成的行文本放到哪個路徑下面展示一些 行內代碼片，
這個變數表示從哪個目錄中讀取boost檔案的html
string g_input_path ="../data/input";
這個變數表示預處理模塊輸出結果放到哪里
string g_output_path ="../data/tmp/raw_input";
我們還需要一個結構體，來表示一個個的html
struct DocInfo{
string title;//檔案的標題
string url;//檔案的url
string content;//檔案的正文
};
既然我們要將所有的html都決議成行檔案，那么我們首要做的就是將所下載的所有html都列舉加載進來，那么我們就可以封裝一個函式
bool EnumFile(const string &input_path, vector<string> *file_list)
其中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);
我前端做的不太好，也就不給大家展示了，
咱們的站內搜索引擎也基本就結束了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/291904.html
標籤：其他
上一篇：《測驗架構師學習進階寶典》終于完成了！花費9個月，16大熱門知識板塊，400頁126508字！（附學習視頻）
下一篇：STM32 舵機控制器