[数据结构与算法]C++项目:boost网站站内搜索

一.项目需求

针对boost网站没有搜索导航功能，为boost网站文档的查找提供搜索功能

二.正排索引和倒排索引

正排索引类似于书的目录，我们可以根据页数查找到对应的内容
倒排索引和正排索引是相反的概念，我们可以根据文档内容查询到这部分内容在哪些文件中出现，从而找到对应的文件

三.项目模块

1.预处理模块

将离线的所有的html文档组织成为一个行文本文件
具体流程：
利用boost提供的filesystem枚举出所有html文档的路径，方便后续打开；
读取每个文档的内容，解析得到标题、url、正文,将每个文档的标题、url、正文组织为一行数据，将所有文档解析后得到的数据都写入文件，方便后续进行处理。

2.索引模块

解析预处理模块得到的行文件，构建正排索引和倒排索引，并提供查正排和查倒排接口供外界使用
具体流程：
1.设计正排索引和倒排索引对应的数据结构
正排索引通过数组存储，下标对应文档id，数组中存储的是文档信息结构体DocInfo，这个文档信息结构体的内容有文档的id、标题、在线的url、内容;
倒排索引通过哈希表存储，key是文档中的词,value是这个词出现的所有文档集合，这个文档集合我们称之为倒排拉链，倒排拉链用一个数组表示，这个数组中存储着文档中的词对应的文档信息结构体Weight,Weight结构体中包含文档id,单词对应的权重、单词的内容三部分.

	//文档信息
	struct DocInfo{
		int64_t docId;//文档id
		string title;//标题
		string url;//url
		string content;//内容
	};

	//单词出现的文档信息
	struct Weight{
		int64_t docId;//文档id
		int weight;//权重
		string word;//备份	
	};

	//倒排拉链
	typedef vector<Weight> InvertedList;

	vector<DocInfo> forwardIndex;//正排索引
	unordered_map<string, InvertedList> invertedIndex;//倒排索引:内容+出现的文档集合

2.按行读取预处理得到的行文本文件，将每行数据进行解析构建正排索引个倒排索引

• 构建正排索引
  对每行数据按照不可见字符’\3’进行分割，得到文档的标题、url、正文,组织一个DocInfo对象，将DocInfo对象尾插到正排索引数组中，建立数组下标和DocInfo信息的一种类似于哈希的映射关系。

//创建正排索引
DocInfo* Index::buildForward(const string& line){
	//1.按照\3进行切割
	vector<string> tokens;
	common::Util::split(line,"\3",&tokens);
	if(tokens.size() != 3){
		return nullptr;
	}
	
	//2.创建DocInfo对象，并将分割的内容进行填充
	DocInfo docInfo;
	docInfo.docId=forwardIndex.size();
	docInfo.title=tokens[0];
	docInfo.url=tokens[1];
	docInfo.content=tokens[2];
	//forwardIndex.push_back(docInfo);
	//将docInfo直接搬运----C++11
	forwardIndex.push_back(std::move(docInfo));
	//3.返回得到的DocInfo对象的指针，供倒排索引的构造来使用
	//不能返回 &DocInfo,因为退出作用域之后就会销毁DocInfo,再去解引用就会使用野指针
	return &forwardIndex.back();
}

• 构建倒排索引
  对文档信息中的标题进行分词，使用哈希表统计分词后的结果在标题中出现的次数；
  对文档信息中的正文进行分词，使用哈希表统计分词后的结果在正文中出现的次数；
  分词后的单词在哈希表中对应的频次信息采用一个结构体表示，这个结构体有两个成员：标题中出现的次数和正文中出现的次数。
  遍历存储频次信息的哈希表，拿到每一个单词对应的频次信息，计算对应的权重，权重等于单词在标题中出现的次数*10+在正文中出现的次数，组织一个Weight结构体；获取倒排索引这个哈希表中该单词对应的value的引用,将也就是倒排拉链，将Weight结构体添加到该单词出现的文档信息集合(倒排拉链)中；当哈希表遍历完毕之后，倒排索引构建完成。

//构建倒排索引
void Index::buildInverted(const DocInfo& docInfo){
	//创建用于统计词频的结构体
	struct WordCnt{
		int titleCnt;  //标题中出现的次数
		int contentCnt;//正文中出现的次数
		WordCnt() : titleCnt(0), contentCnt(0){}
	};
	//使用hash表进行词频的统计
	unordered_map<string,WordCnt> wordCntMap;

	//1.针对文档标题进行分词
	vector<string> titleTokens;
	cutWord(docInfo.title,&titleTokens);
	//2.根据分词结果，统计每个词在标题中出现的次数
	for(string word:titleTokens){
		//不区分大小写，全部转换为小写
		boost::to_lower(word);
		++wordCntMap[word].titleCnt;
	}
	//3.针对文档正文进行分词
	vector<string> contentTokens;
	cutWord(docInfo.content,&contentTokens);
	//4.根据分词结果，统计每个词在正文中的出现次数
	for(string word:contentTokens){
		//不区分大小写，全部转换为小写
		boost::to_lower(word);
		++wordCntMap[word].contentCnt;
	}
	//5.遍历统计结果，构建倒排索引
	//(key是词，value是权重)
	//auto得到的类型是一个pair
	for(auto wordPair : wordCntMap){
		Weight weight;
		weight.docId=docInfo.docId;
		//权重的算法:标题中出现的次数*10+正文中出现的次数
		weight.weight=wordPair.second.titleCnt * 10 + wordPair.second.contentCnt;
		//将这个词在weight对象中也存储一份，以备后用
		weight.word=wordPair.first;
		//更新倒排索引
		//根据当前词，在倒排索引中查找对应的倒排拉链
		//存在的话返回对应的倒排拉链的引用
		//不存在创建一个元素，并返回key为当前词的映射值的引用
		//把权重对象插入到倒排拉链尾部
		InvertedList& invertedList = invertedIndex[wordPair.first];
		invertedList.push_back(weight);
	}
}

3.实现查正排和查倒排接口
查正排的内部逻辑是根据下标访问vector容器，文档id就是vector的下标；
查倒排的内部逻辑是通过哈希表的key获取value，根据单词获取对应的倒排拉链

3.搜索模块

根据查询词查询倒排索引和正排索引，组织一个查询结果
具体流程是：
对查询词进行分词；
对分词结果查询倒排，将所有的倒排拉链合并到一个大的数组中，这个数组中存放查询词出现的所有文档集合；
对文档集合中的所有元素按照权重降序排序；
对排序后的集合查正排,将查询正排得到的结果组织成一个JSON对象，这个对象中有三个成员:标题、url、摘要，将集合中所有元素查正排后的结果整体组织成一个JSON格式的结果；

	//处理搜索
	bool Searcher::search(const std::string& query, std::string* output){
		//1.分词:对查询词进行分词
		vector<string> tokens;
		index->cutWord(query,&tokens);
		//2.触发:根据分词结果，查倒排，找到相关的文档id
		vector<Weight> allTokens;//存放查询的所有的
		for(string word : tokens){
			//查倒排之前忽略大小写
			boost::to_lower(word);
			const auto* invertedList = index->getInverted(word);
			if(invertedList == nullptr){
				//该词没找到
				continue;
			}
			//找到查询结果，将查询结果合并到一个大的数组中
			//分词结果可能是多个，将每个单词的倒排拉链合并为一个数组
			//然后对数组进行排序
			allTokens.insert(allTokens.end(),invertedList->begin(),invertedList->end());
		}	
		//3.排序:根据该词在该文档中的次数，对结果进行排序
		//按照权重降序排列
		std::sort(allTokens.begin(),allTokens.end(),
			[](const Weight& w1, const Weight& w2){
				return w1.weight > w2.weight;
			});
		//4.构造结果:根据最终的结果查正排，构造json格式的数据
		//Json::Value这个类可以当作vector,也可以当作map使用
		Json::Value results;
		for(const auto& weight : allTokens){
			//根据weight中的docId,查正排
			//将查询结果的相关内容，构造成json格式的字符串
			const auto* docInfo = index->getDocInfo(weight.docId);
			Json::Value result;
			result["title"]=docInfo->title;
			result["url"]=docInfo->url;
			result["desc"]=generateDesc(docInfo->content,weight.word);//获取正文摘要
			results.append(result);
		}

		//将Json::Value对象序列化转为字符串，写入到output这个字符串中
		Json::FastWriter writer;
		*output=writer.write(results);
		return true;
	}

4.服务器模块

搭建http服务器处理来自浏览器的查询请求，调用搜索模块的代码得到查询结果，将查询结果组织成为一个静态网页，这个网页允许用户可以点击跳转到相关的网页，并显示网页的标题和网站内容的相关摘要。

四.技术点

正排索引和倒排索引；
C++11移动语义；
IO多路复用；
线程池；

五.项目源码

https://gitee.com/xigongxiaoche/project/tree/master/boostSearch