爱悠闲 > 【北大天网搜索引擎TSE学习笔记】第8节——检索关键词+结果排序

【北大天网搜索引擎TSE学习笔记】第8节——检索关键词+结果排序

分类: 搜索引擎  |  作者: dongtingzhizi 相关  |  发布日期 : 2012-03-14  |  热度 : 372°

        这一节将介绍搜索功能入口程序TSESearch.cpp的第四步和第五步——检索关键词+结果排序。


        其实,检索关键词非常简单,因为已经建立了倒排表mapBuckets,它是一个map结构,检索某个关键词,就是用map的find方法查询(下面代码中的第27),没有什么需要介绍的。也因此,TSE中将检索关键词和结果排序在一起实现,也就是main函数中调用的函数:iQuery.GetRelevantRst(vecTerm, mapBuckets, setRelevantRst)。

下面就看该函数的源代码,分析TSE中检索关键词和结果排序的实现。TSE的结果排序方法很简单,就是采用的词频(Term frequency)进行排序的,关于词频排序可以到网上搜索TF-IDF词条进行学习,这里不做详细说明。简单说,词频排序就是:网页中某个关键词出现次数(词频)越高,说明该网页与该关键词相关性越高,因而在结果排序中越优。


        下面的代码中加入了详细的注释(以“LB_C”开始的注释为我加入的)进行说明。

//LB_c: vecTerm中存储的用户查询字串分词以后的关键词,mapBucket为倒排表,setRelevantRst存储最终的查询的结果(里面存储
// 的是结果网页的docid)
bool CQuery::GetRelevantRst(vector<string> &vecTerm, 
	map<string,string> &mapBuckets, 
	set<string> &setRelevantRst) const
{
	//LB_c: 临时存储已经查询的结果
	set<string> setSRst;
	bool bFirst=true;

	//LB_c: 分别对vecTerm中的每一个关键词进行查询
	vector<string>::iterator itTerm = vecTerm.begin();
	for ( ; itTerm != vecTerm.end(); ++itTerm ){

		//LB_c: setRelevantRst为已查询的结果,将setRelevantRst存入setSRst中,后面将用到。
		setSRst.clear();
		copy(setRelevantRst.begin(), setRelevantRst.end(), 
		inserter(setSRst,setSRst.begin()));

		//LB_c: mapRstDoc是一个用于临时统计的map,string对应一个docID,int是该docID出现的次数(也就是当前关键词在docid
		// 的网页中出现的次数,也成为"词频",后面将称为"词频"), 后面是根据词频值对搜索结果进行排序的(即关键词出现次数
		// 越多的网页应该越"优")。
		map<string,int> mapRstDoc;
		string docid;
		int doccnt;
		//LB_c: 在倒排表中查询关键词(*itTerm)
		map<string,string>::iterator itBuckets = mapBuckets.find(*itTerm);	
		//LB_c: 在倒排表中找到了该关键词
		if (itBuckets != mapBuckets.end()){

			//LB_c: 获取该关键词出现的文档ID列表(即倒排表记录的第二项,忘记了的朋友可以看看第2节中倒排文件的结构)
			string strBucket = (*itBuckets).second;

			string::size_type idx;
			idx = strBucket.find_first_not_of(" ");
			strBucket = strBucket.substr(idx);

			//LB_c: 循环从文档ID列表字符串中获取一个文档ID,并计算词频,插入mapRstDoc中
			while ( (idx = strBucket.find(" ")) != string::npos ) {
				docid = strBucket.substr(0,idx);
				if (docid.empty()) continue;
				doccnt = 0;	//LB_c: 计算词频
				//LB_c: 到mapRstDoc中查询该docid是否出现过
				map<string,int>::iterator it = mapRstDoc.find(docid);
				//LB_c: 如果docid出现过
				if ( it != mapRstDoc.end() ){
				//LB_c: 获取词频((*it).second)加1存入doccnt
				doccnt = (*it).second + 1;
				//LB_c: 从mapRstDoc把该条记录删除,下面将重新插入
				mapRstDoc.erase(it);
				}

				//LB_c: 将该条记录重新插入到mapRstDoc,其实先删除再插入这条记录的结果就是docid的词频加了1
				//LB_c: 这里应该有点问题! 如果docid没出现过,那么doccnt的值为0,则插入到mapRstDoc的对应于docid
				// 的词频0,所以前面doccnt的初值是不是应该为1呢?
				mapRstDoc.insert( pair<string,int>(docid,doccnt) );

				//LB_c: 去掉分析过的docid更新strBucket,继续分析下一个文档ID
				strBucket = strBucket.substr(idx+1);
			}

			//LB_c: 下面这部分是处理strBucket中最后一个docid,因为while循环结束时,最后一个docid还没有处理
			// remember the last one
			docid = strBucket;
			doccnt = 0;
			map<string,int>::iterator it = mapRstDoc.find(docid);
			if ( it != mapRstDoc.end() ){
			doccnt = (*it).second + 1;
			mapRstDoc.erase(it);
			}
			mapRstDoc.insert( pair<string,int>(docid,doccnt) );
		}
		//LB_c: 这一部分处理完后,mapRstDoc存储的是一系列docid和该docid的词频。

		// sort by term frequencty
		//LB_c: 这部分是对刚才的带有词频的文档查询结果mapRstDoc进行了排序,排序结果存入到newRstDoc中。
		//LB_c: 注意newRstDoc的类型,第一个域为int表示docid的词频,第二个域是string表示docid,第三个域
		// 是排序规则----以键值(词频)的降序排列,注意newRstDoc是multimap,也就是键值可以重复。
		multimap<int, string, greater<int> > newRstDoc;
		map<string,int>::iterator it0 = mapRstDoc.begin();
		for ( ; it0 != mapRstDoc.end(); ++it0 ){
			newRstDoc.insert( pair<int,string>((*it0).second,(*it0).first) );
		}

		//LB_c: 这部分是将当前关键词(*itTerm)的排序查询结果newRstDoc插入到最终的查询结果setRelevantRst中,
		// 这里要参考前面的关键词查询结果。
		multimap<int,string>::iterator itNewRstDoc = newRstDoc.begin();	
		//LB_c: 将最终的查询结果setRelevantRst清空
		setRelevantRst.clear();	
		//LB_c: 循环读取newRstDoc中的每一条记录(这些记录是按docid的词频排序的),根据情况插入到最终结果中
		for ( ; itNewRstDoc != newRstDoc.end(); ++itNewRstDoc ){

			//LB_c: 获取该条记录的docid
			string docid = (*itNewRstDoc).second;		
			//LB_c: 如果当前关键词是第一个查询的关键词,则直接插入到结果集中
			if (bFirst==true) {
				setRelevantRst.insert(docid);
				continue;
			}

			//LB_c: 如果不是第一个关键词查询,则看已查询结果集setSRst中是否有该docid,也就是前面查询的关键词
			// 有没有出现在docid的网页中。这里也体现了TSE搜索的规则: 只有所有关键词都出现的网页才有效,部分关键
			// 词出现的网页不作为搜索结果。如果setSRst中有该docid说明docid的网页也包含前面查询的关键词, 则将
			// docid插入到最终结果集setRelevantRst中。
			if ( setSRst.find(docid) != setSRst.end() ){	
				setRelevantRst.insert(docid);
			}
		}

		//LB_c: 这里思考一下! 首先将setRelevantRst清空,然后将当前关键词(*itTerm)的排序结果newRstDoc插入到最终结果集
		// setRelevantRst中。也就是最终的结果排序是以最后一个查询关键词的词频排序的,即最后一个关键词出现次数多的网页
		// 排在前面。

		bFirst = false;
	}

	return true;
}


这一节之后,关于TSE查询服务子系统的介绍就只剩下最后一节——显示搜索结果了,本来想年前把它写完的,由于明天回家过年了,是在没有时间了,所以只能年后再继续了。回家happy去啦~~ 也预祝各位读者新年快乐,工作顺利~~


By: