模块二：网页搜索

该模块用来提供网页搜索功能，当输入一些关键词后，推荐内容相关的网页，作用类似于百度搜索

1 建立网页库、网页偏移库和索引库

1.1 网页库

（1）首先需要建立网页库和网页偏移库，前者用来存储网页的内容，后者用来记录该网页在文件中偏移，方便后续输出这个网页的内容

网页库的格式采用xml 的形式（需提前利用爬虫准备好这些文件，这里可直接使用现成的），细分为<doc>,<id>,<title>,<url>,<content>,具体形式如下：

<doc>

<id>1</docid>

<url>http://baidu.com/</url>

<title>博客榜—查看频道“中国互联网观察”</title>

<content>博客榜—查看频道“中国互联网观察”…</content>

</doc>

<doc>

<docid>2</docid>

<url>……</url>

<title>….. </title>

<content>博客榜博客榜—查看频道,随便扯淡吧……. </content>

</doc>

tinyxml2是一个开源插件，用于解析xml文件。建立网页库的代码实现如下：

using namespace tinyxml2;
void WebPages::addPage(const string& filepath) {
    XMLDocument doc;
    XMLError result = doc.LoadFile(filepath.c_str());
    if(result == XML_SUCCESS){
        XMLElement* root = doc.RootElement();
        if(root){
            XMLElement * channel = root->FirstChildElement("channel");
            while(channel){
                XMLElement* title = channel->FirstChildElement("title");
                XMLElement* link = channel->FirstChildElement("link");
                XMLElement* description = channel->FirstChildElement("description");
                if(description == nullptr) {
                    channel = channel->NextSiblingElement("channel");
                    continue;
                }
                XMLElement* item = description->NextSiblingElement();
                            //cout << "while(item)" << endl;
                while(item){
                    if(strcmp(item->Name(), "item") == 0){
                        XMLElement* item_title = item->FirstChildElement("title");
                        XMLElement* item_link = item->FirstChildElement("link");
                        XMLElement* item_description = item->FirstChildElement("description");
                        if(item_description == nullptr){
                            item = item->NextSiblingElement();
                            continue;
                        }
                        //cout << _pages[_pages.size()-1].title << endl;
                        XMLElement* content = item_description->NextSiblingElement();
                        while(content){
                            //cout << content->Name() << endl;;
                            if(strncmp(content->Name(), "content", strlen("content"))==0){
                                if(content->GetText()!=nullptr){
                                    _pages.push_back({item_title->GetText(),
                                                      item_link->GetText(),
                                                      dealHTML(description->GetText()),
                                                      dealHTML(content->GetText())});

                                    addTermFrequency(_pages.back().content);
                                }

                            }
                            content = content->NextSiblingElement();
                        }

                    }else if(strncmp(item->Name(), "content", strlen("content"))==0){
                        if(item->GetText()!=nullptr){
                            _pages.push_back({title->GetText(),
                                             link->GetText(),
                                             dealHTML(description->GetText()),
                                             dealHTML(item->GetText())});
                            
                            //cout << "addFrequency" << endl;
                            addTermFrequency(_pages.back().content);
                        }
                    }
                    item = item->NextSiblingElement();
                }
                channel = channel->NextSiblingElement("channel");
            }
        }else{
            LogError("RootElement failed");

            exit(1);
        }
    }else{
        LogError("LoadFile failed");
        exit(1);
    }
    //cout << _pages.size() << endl;
}

（2）将所给语料库中的所有文档按照格式，构造成网页库ripepage.dat；提取网页的标题的策略如下：

1) 如果查找到字符串“【标题】”，则抽取该行的内容为标题；

2) 如果没有找到，则提取文档的第一行为标题，整个文档的全部内容为content（包括标题），Url 使用每篇文档所在的绝对路径；然后将所有的字符串拼接起来，构成一篇格式化的文档，例如：

string fmtTxt = "<doc><docid>" + docid +

"</docid><url>" + url+

"</url><title>" + title +

"</title><content>" + content +

"</content></doc>";

网页库的格式实现：

string WebPages::getPage(int i) {
    if(i>(int)_pages.size() || i < 0) {
        cout << "out of range" << endl;
        return "";
    }
    ostringstream oss;
    oss << "<doc>"
        << "<docid>" << i+1 << "</docid>"
        << "<title>" << _pages[i].title << "</title>"
        << "<link>" << _pages[i].link << "</link>"
        << "<description>" << _pages[i].description << "</description>"
        << "<content>" << _pages[i].content << "</content>"
        << "</doc>";
    return oss.str();
}

1.2 偏移库

（1）获取格式化好的文档之后，通过C++的文件输出流将文档写到文件中去，同时记录下该篇文档在文件的位置信息，即offset.dat。

偏移库的实现：

OffsetPage::OffsetPage(Configuration& conf, WebPages& webPage)
    : _configuration(conf), _webPage(webPage) {
}

void OffsetPage::store() {
    // 从Configuration对象获取配置数据
    std::map<string, string> config_data = _configuration.getConfigMap();

    // 创建一个文件输出流，文件路径由Configuration对象提供
    ofstream ofs(config_data["OffsetPage.dat"]);
    if(!ofs.good()) {
        LogError("Failed to open offset file: %s", config_data["OffsetPage.dat"].c_str());    // 记录错误信息
        return;
    }

    // 从WebPages对象获取文章数量
    size_t size = _webPage.getSize();

    // 初始化偏移量和长度
    streampos offset = 0;

    // 遍历webPage
    for(size_t i = 0; i < size; ++i) {
        // 获取第i个doc的内容
        string content = _webPage.getPage(i);
        // 获取内容的长度
        int length = content.size();
        // 写入docid，偏移量和长度
        ofs << i + 1 << " " << offset << " " << length << endl;
        // 更新偏移量
        offset += length;
    }
    if(ofs.fail()) {
        LogError("Failed to write to file %s", config_data["OffsetPage.dat"].c_str());    // 记录错误信息
    }
}

偏移库的格式：id 开始位置 该网页的长度

1 0 10046

2 10046 7752

3 17798 9559

4 27357 12548

5 39905 16412

6 56317 9338

7 65655 14165

8 79820 12987

9 92807 8296

10 101103 21113

11 122216 13215

12 135431 44896

....

（2）在网页库和偏移库的基础上，建立索引库，用于存储一个词组所在的网页以及对应的权重系数，这里需要了解权重系数的计算方式

TF-IDF 算法：

TF : Term Frequency, 某个词在文章中出现的次数；

DF: Document Frequency, 某个词在所有文章中出现的次数，即包含该词语

的文档数量；

IDF: Inverse Document Frequency, 逆文档频率，表示该词对于该篇文章的重

要性的一个系数，其计算公式为：

IDF = log2(N/(DF+1))，其中N 表示文档的总数或网页库的文档数

最后，词语的权重w 则为：

w = TF * IDF

可以看到权重系数与一个词在文档中的出现次数成正比，与该词在整个网页库

中的出现次数成反比。

而一篇文档包含多个词语w1,w2,...,wn，还需要对这些词语的权重系数进行归一

化处理，其计算公式如下：

w' = w /sqrt(w1^2 + w2^2 +...+ wn^2)

w'才是需要保存下来的，即倒排索引的数据结构中InvertIndexTable 的double 类

型所代表的值

为了计算TF和DF，需要统计每个网页中词组出现的频率(addTermFrequency)和所有网页中词组出现的频率（addDocFrequency）：

void WebPages::addTermFrequency(const string & str){
    //cut content using splict_tool
    vector<string> tmpvec = _splictTool->cut(str);
    tmpvec = _splictTool->removeStopWords(tmpvec);
    //create word-frekuency map for this webPage
    unordered_map<string, int> tmpmap;
    for(auto & it : tmpvec){
        if(tmpmap.find(it)==tmpmap.end()){
            tmpmap[it] = 1;
        }else{
            ++tmpmap[it];
        }
    }
    _termFrequency.push_back(std::move(tmpmap));
}

void WebPages::addDocFrequency(){
    //clear _docFrequency for recalculate it after remove duplicate
    _docFrequency.clear();
    for(auto itTerm : _termFrequency){
        for(auto wordFrequency : itTerm){
            if(_docFrequency.find(wordFrequency.first) == _docFrequency.end()){
                _docFrequency[wordFrequency.first] = 1;
            }else{
                ++_docFrequency[wordFrequency.first];
            }
        }
    }
}

IDF的计算：

void WebPages::calculateTfidf(){
    //calculate _docFrequency
    addDocFrequency();
    //clear _idf for recalculate it after remove duplicate
    _idf.clear();
    int size = _pages.size();
    for(int i = 0; i < size; ++i){
        int id = i+1;
        map<string, double> tmp;
        tmp.clear();
        //IDF = log2(N/(DF+1))，
        for(auto it : _termFrequency[i]){
            long tf = it.second;
            long df = 0;
            if(_docFrequency.find(it.first)!=_docFrequency.end()){
                df = _docFrequency[it.first];
            }
            double idf = log2((double)size/(df+1)); 
            double w = tf * idf;
            tmp.insert({it.first, w});
        }
        //归一化
        //w' = w /sqrt(w1^2 + w2^2 +...+ wn^2)
        double norm = 0;
        for(auto & it : tmp){
            norm += pow(it.second, 2);
        }     
        norm = sqrt(norm);
        for(auto & it : tmp){
            it.second = it.second/norm;
        }
        _idf.insert({id, std::move(tmp)});
    }
}

这里的_idf用来存储一个网页中，所有词语对应的权重系数

1.3 索引库的建立：

class IndexPage {
public:
    // 构造函数，接受 Configuration 和 WebPages 对象的引用作为参数
    IndexPage(Configuration& conf, WebPages& webPage)
        : _configuration(conf),
        _webPage(webPage) {}

    // 存储索引页数据
    void store() {
        map<string, string> config_data = _configuration.getConfigMap();
        map<int, map<string, double>> webPage_data = _webPage.getTfidf();
        map<string, map<int, double>> res;
        std::ofstream ofs(config_data["IndexPage.dat"]);
        if (!ofs.good()) {
            cout << "IndexPage::ofs is not good." << std::endl;
            return;
        }
        // 构建索引页数据
        for (auto i : webPage_data) {
            for (auto j : i.second) {
                if (res.find(j.first) == res.end()) {
                    res[j.first] = {};
                }
                res[j.first].insert({i.first, j.second});
            }
        }
        // 将索引页数据写入文件
        for (auto i : res) {
            ofs << i.first << " ";
            for (auto j : i.second) {
                ofs << j.first << " " << j.second << " ";
            }
            ofs << endl;
        }
    }
    ~IndexPage() {}

private:
    Configuration& _configuration;  // Configuration 对象的引用
    WebPages& _webPage;  // WebPages 对象的引用
};

索引库格式：

站点 54 0.0644483 86 0.0162756

竞争 9 0.0117943 10 0.00890861 12 0.00161958 95 0.0100773 177 0.0243834 243 0.0178622 299 0.0472355 309 0.0202292 340 0.0590459 458 0.0986078 518 0.0164677 521 0.0340066

竞争力 95 0.0275853 105 0.0138203 126 0.0456681 162 0.0364533 231 0.0171097 271 0.015947 299 0.0646506 300 0.0282437 305 0.0189844 309 0.055375 332 0.0256729 346 0.0241807 409 0.0194195 413 0.0124952 437 0.0129991 518 0.0450783 534 0.0149574

竞争对手 9 0.0177331

竞争性 305 0.0274027 500 0.0287652 522 0.0876479

竞争能力 465 0.0331229

竞技 246 0.0357331 292 0.0289071 409 0.0280308

竞相 197 0.0176948 309 0.0282089

章法 15 0.0285327

章节 14 0.0243993

.....

2 网页去重

当网页库建立好之后，需要删除网页库中相同的文档，即网页去重，这里使用去重的插件为Simhash 算法。

Simhash算法的五个步骤：分词、哈希、加权、合并、降维，使用实例如下：

void test()
{
Simhasher simhasher("../dict/jieba.dict.utf8",
"../dict/hmm_model.utf8",
"../dict/idf.utf8",
"../dict/stop_words.utf8");
string s("我是蓝翔技工拖拉机学院手扶拖拉机专业的。不用多久，我就会升职加薪，当上总经
理，出任CEO，走上人生巅峰。");
size_t topN = 5;
uint64_t u64 = 0;
vector<pair<string ,double> > res;
simhasher.extract(s, res, topN); //提取关键词与权重
simhasher.make(s, topN, u64); //
cout<< "文本：\"" << s << "\"" << endl;
cout << "关键词序列是: " << res << endl;
cout<< "simhash值是: " << u64 <<endl;
const char * bin1 = "100010110110";
const char * bin2 = "110001110011";
uint64_t u1, u2;
u1 = Simhasher::binaryStringToUint64(bin1);
u2 = Simhasher::binaryStringToUint64(bin2);
cout << bin1 << "和" << bin2 << " simhash值的相等判断如下："<<endl;
cout << "海明距离阈值默认设置为3，则isEqual结果为："
<< (Simhasher::isEqual(u1, u2)) << endl;
cout << "海明距离阈值默认设置为5，则isEqual结果为："
<< (Simhasher::isEqual(u1, u2, 5)) << endl;
return EXIT_SUCCESS;
}

3 建立倒排索引

倒排索引：英文原名为Inverted index，大概因为Invert 有颠倒的意思，就被翻译成了倒排。一个未经处理的网页库中，一般是以文档ID 作为索引，以文档内容作为记录。而Inverted index 指的是将单词或记录作为索引，将文档ID 作为记录，这样便可以方便地通过单词或记录查找到其所在的文档。在此项目中，倒排索引的数据结构采用的是：unordered_map <string, vector<pair<int, double>>> InvertIndexTable

其中unordered_map 的key 为出现在文档中的某个词语，对应的value 为包含该词语的文档ID 的集合以及该词语的权重值w。

倒排索引的建立需要在前面的索引库、偏移库和网页库基础上建立：

ebPageReader::WebPageReader(const string& indexPath, const string& offsetPath, const string& webPath) {
    // 读取倒排索引文件
    ifstream indexFile(indexPath);
    if(!indexFile.is_open()) {
        LogError("Failed to open index file: %s", indexPath.c_str());
        return;
    }
    string line;
    // 按行读取文件
    while(getline(indexFile, line)) {
        istringstream iss(line);
        string word;
        // 每行第一个字符串是关键词
        iss >> word;
        int docId;
        double weight;
        // 关键词后面是文档ID和权重的对
        while(iss >> docId >> weight) {
            // _invert_index_lib[word][docId] = weight;
            _invert_index_lib[word].insert({ weight, docId });
        }
    }
    indexFile.close();

    // 读取偏移文件
    ifstream offsetFile(offsetPath);
    if(!offsetFile.is_open()) {
        LogError("Failed to open offset file: %s", offsetPath.c_str());
        return;
    }
    while(getline(offsetFile, line)) {
        istringstream iss(line);
        int docId, start, length;
        // 每行是文档ID，起始位置和长度的三元组
        iss >> docId >> start >> length;
        _offset_lib[docId] = make_pair(start, length);
    }
    offsetFile.close();

    // 读取web文件
    ifstream webFile(webPath);
    if(!webPath.c_str()) {
        LogError("Failed to open webPath file: %s", webPath.c_str());
        return;
    }
    // 根据偏移文件，获取每篇文档的内容
    for(const auto& offsetPair : _offset_lib) {
        webFile.seekg(offsetPair.second.first);
        char* buffer = new char[offsetPair.second.second + 1];
        webFile.read(buffer, offsetPair.second.second);
        buffer[offsetPair.second.second] = '\0';
        // 把buffer传给方法
        _web_lib[offsetPair.first] = getRssItem(string(buffer));
        delete[] buffer;
    }

    webFile.close();
    // _invert_index_lib : 单词 （权重，docID) （权重，docID) ...
    // 生成id_word_weight : docID  (单词, 权重)，(单词, 权重) ...
    // 对于每个关键词，获取它在每篇文档中的权重
    for(const auto& indexPair : _invert_index_lib) {
        for(const auto& weightPair : indexPair.second) {
            // weightPair.first为权重 weightPair.second 为docID
            _id_word_weight[weightPair.second].push_back(make_pair(indexPair.first, weightPair.first));
        }
    }
}

4 网页查询

（1）在处理查询请求时，对于查询的关键词，将它们视为一篇文档X，通过TF-IDF 算法计算出每个关键词的权重系数；将其组成一个向量(x1, x2, ...,xn)，该向量作为基准向量Base，在下面的(3)中使用；

（2）通过倒排索引表去查找包含所有关键字的网页；只要其中有一个查询词不在索引表中，就认为没有找到相关的网页

//获取拥有关键词的docid，传入切好词的数组
std::vector<int> WebPageQuery::getDocId(const std::vector<std::string>& words) {
    std::vector<int> res;

    //获取每一个关键词的拥有的docid
    for (const auto& word : words) {

        //对关键词进行防冲突处理
        string newWord="网页查询："+word;

        //判断redis有无这个关键词
        string rres = _redis->getRedisData(newWord);

        //如果redis中没有这个关键词从词库中查找
        if (rres == string()) {
            LogInfo("从词库中查询%s",word.c_str());

            //获取倒排索引表
            std::map<std::string, std::multimap<double, int>> invert_index_lib = _webPageReader->getInvertIndexLib();

            //将每一项加入set去重,排序
            std::set<int> tmp;
            for (const auto& item : invert_index_lib[word]) {
                tmp.insert(item.second);

            }

            //将set转成vector适应接口
            vector<int> resTmp(tmp.begin(),tmp.end());
            res=resTmp;

            //将数组转成字符串
            string sdocIds = WstringOperation::vectorToString(res);

            //写入redis
            _redis->setRedisData(newWord, sdocIds);
            _redis->expireRedisData(newWord, 10);

        } 
        //如果redis中存在关键词
        else 
        {
            //将从redis中获取的字符串转成string
            res = WstringOperation::stringToVector(rres);
            LogInfo("从Redis中查询%s",word.c_str());
        }

    }
    return res;

}

（3）如果找到了网页，则需要对查找到的网页进行排序。排序算法采用余弦相似度。既然查找到的网页都包含查询词，那么获取每个查询词的w，将它们组成一个向量Y = (y1,y2, ... yn)，用该向量代表这篇网页，该向量Y 是网页的特征，然后计算它与Base 的余弦值，该余弦值代表的就是Y 与X 的相似度；那么现在只需要将查找到的所有网页都与X 进行余弦相似度cosθ的计算，然后根据cosθ的大小进行排序，cosθ越大越相似，这样的网页应该出现在前排的位置。cosθ的计算方法如下：

X * Y = (x1 *y1 + x2 * y2 + x3 * y3)

cosθ = (X * Y) / (|X| * |Y|)

计算余弦相似度：

//计算关键词与网页的余弦值，形参为网页库的id和关键词组
double WebPageQuery::getCos(int ID, const std::vector<std::string>& keyWords) {

    //获取<网页id,搜索词，权重>的表
    std::map<int, std::vector<std::pair<std::string, double>>> id_word_weight = _webPageReader->getIdWordWeight();

    //获取当前id的搜索词和权重的表
    std::vector<std::pair<std::string, double>> vcp = id_word_weight[ID];
    std::vector<double> pointx;
    std::vector<double> pointy;
    int size = keyWords.size();
    int count = 0;

    //便利当前id的搜索词和权重的表，将关键词和文章的点标出
    for (const auto& item : vcp) {
        count++;
        if (std::find(keyWords.begin(), keyWords.end(), item.first) != keyWords.end()) {
            double value = 1.0 / size;
            pointy.push_back(value);

        } else {
            pointy.push_back(0);

        }
        pointx.push_back(item.second);

    }
    double XmulY = 0;
    double Xdis2 = 0;
    double Ydis2 = 0;

    //计算两个点的余弦值
    for (int i = 0; i < count; i++) {
        XmulY += (pointx[i] * pointy[i]);
        Xdis2 += pointx[i] * pointx[i];
        Ydis2 += pointy[i] * pointy[i];

    }
    double res = XmulY / (sqrt(Xdis2) * sqrt(Ydis2));
    return res;

}

网页排序：

//对获取的docid的余弦值排序，并去除对应项的内容形参为拥有关键词的docid数组和关键字词组
std::map<double, RssItem, std::greater<double>> WebPageQuery::getRes(const std::vector<int>& docIds, const std::vector<std::string>& keyWords) {

    std::map<double, RssItem, std::greater<double>> res;
    std::map<int,double> tmp;
    string key="网页查询排序："+WstringOperation::vectorToString(keyWords);
    string rss= _redis->getRedisData(key);
    if(rss==string())
    {
        for (const auto& id : docIds) {
            //获取docids项与关键词的余弦值
            double cosTmp = getCos(id, keyWords);
            tmp[id]=cosTmp;
            //获取docid的内容
            //RssItem strTmp = _webPageReader->getWebLib()[id];

        }
        string value=WstringOperation::mapToString(tmp);
        _redis->setRedisData(key,value);
    }
    else
    {
        tmp=WstringOperation::stringToMap(rss);
    }

    for(auto& id:docIds)
    {
        double cosTmp=tmp[id];
        RssItem strTmp=_webPageReader->getWebLib().at(id);
        res[cosTmp] = strTmp;
    }
    //便利拥有关键词的docid数组
    return res;

}

(4)当找到网页之后，还需要提取每篇网页中的标题和摘要信息，然后将这些信息封装成一个JSON 字符串，交给服务器框架模块去发送给客户端。要注意的是：摘要信息是根据查询词自动生成的。

//将rssItem根据关键词修改成json
nlohmann::json WebPageQuery::modifyJson(RssItem rssIems, vector<string> keyWord) {

    //获取rssIems的内容
    string str = getContent(rssIems);

    //找出内容中的关键字的位置索引
    map<string, vector<size_t>> idxs = findKeyword(str, keyWord);

    //根据位置索引对每一项的内容进行切割、标红
    string redStr;
    for (auto idx : idxs) {
        int keyWordLength = idx.first.length();
        for (auto num : idx.second) {
            //对这一项的内容进行切割、标红
            redStr += "..." + signRed(str, num, keyWordLength) + "...\n";

        }

    }

    //对标题进行标红
    string title=rssIems.title;
    title = ChangeColor::colorizeString(title.c_str(),0,title.length(),BLUE_COLOR_STRING);

    //对链接进行标红
    string link=rssIems.link;
    link=ChangeColor::colorizeString(link.c_str(),0,link.length(),GREEN_COLOR_STRING);

    //将结果打包成json
    nlohmann::json newJson;
    newJson["title"] = title;
    newJson["link"] = link;
    newJson["description"] = rssIems.description;
    newJson["content"] = redStr;
    return newJson;

}

完整逻辑实现：

//对外提供的查询接口，形参是要查询的字符串
nlohmann::json WebPageQuery::Query(const std::string& word) {
    LogInfo("start");
    //将字符串分词
    std::vector<std::string> words = cut(word);
//    travel(words);

    //获取各个分词的关联docid
    vector<int> docIds = getDocId(words);
  //  travel(docIds);

    LogInfo("order start");
    //利用docids获取doc表项
    std::map<double, RssItem, std::greater<double>> resMap = getRes(docIds, words);
    LogInfo("order end");

    LogInfo("signRed start");
    //将各个表项存入json然后汇总成数组
    vector<nlohmann::json> vecRes;
    //travel(vecRes);
    for (const auto& i : resMap) {
        nlohmann::json newJson = modifyJson(i.second, words);
        vecRes.push_back(newJson);

    }
    LogInfo("signRed end")

    //在最外面套上一层json，加上必要信息
    nlohmann::json res;
    res["item"] = vecRes;
    res["messageId"] = "200";
    
    LogInfo("endl");

    return res;

}