BoostCompass(建立正排索引和倒排索引模块)

2024-04-14 01:04
文章标签 模块 索引 建立 正排 倒排 boostcompass

本文主要是介绍BoostCompass(建立正排索引和倒排索引模块)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

阅读导航

  • 一、模块概述
  • 二、编写正排索引和倒排索引模块
    • ✅安装 jsoncpp
    • ✅Jieba分词库的安装
    • 1. 代码基本框架
    • 2. 正排索引的建立
    • 3. 倒排索引的建立
  • 三、整体代码
    • ⭕index.hpp

一、模块概述

这个模块我们定义了一个名为Index的C++类，用于构建和维护一个文档索引系统。该系统采用单例模式确保只有一个索引实例，并使用正排索引和倒排索引来快速检索文档。正排索引存储了文档的基本信息，如标题、内容和URL，而倒排索引则根据关键词将文档分组。类中提供了构建索引、获取文档信息和获取倒排列表的方法。构建索引的过程涉及读取处理过的数据文件，解析文档数据，并根据文档内容构建索引。此外，我们还实现了简单的进度显示功能。整个索引系统的构建旨在提高文档检索的效率和准确性。

二、编写正排索引和倒排索引模块

✅安装 jsoncpp

🔴安装方法：sudo yum install -y jsoncpp-devel

✅Jieba分词库的安装

PS：我们要先在Linux机器上安装Jieba分词库链接：🔴 "结巴(Jieba)"中文分词的C++版本

在这里插入图片描述

1. 代码基本框架

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <mutex>
#include "util.hpp" 
#include "log.hpp"  namespace ns_index {// 定义文档信息结构体struct DocInfo {std::string title;   // 文档的标题std::string content; // 文档内容（去标签后）std::string url;     // 文档的URLuint64_t doc_id;     // 文档的唯一ID};// 定义倒排列表中的元素结构体struct InvertedElem {uint64_t doc_id;   // 文档IDstd::string word;  // 关键字int weight;        // 关键字权重InvertedElem() : weight(0) {} // 默认构造函数，权重初始化为0};// 获取单例模式的实例static Index* GetInstance() {// 双重检查锁定模式，确保线程安全地获取单例if (nullptr == instance) {mtx.lock();if (nullptr == instance) {instance = new Index();}mtx.unlock();}return instance;}// 定义索引类Indexclass Index {private:// 构造函数、拷贝构造函数和赋值操作符都设置为私有，防止被实例化Index() {}Index(const Index&) = delete;Index& operator=(const Index&) = delete;// 单例模式的实例指针static Index* instance;// 保护单例模式的互斥锁static std::mutex mtx;public:// 析构函数~Index() {}// 根据关键字获取倒排拉链InvertedList* GetInvertedList(const std::string& word) {auto iter = inverted_index.find(word);if (iter == inverted_index.end()) {std::cerr << word << " have no InvertedList" << std::endl;return nullptr;}return &(iter->second);}};// 初始化单例模式的实例指针为nullptrIndex* Index::instance = nullptr;// 初始化互斥锁std::mutex Index::mtx;
}

⭕代码分析

  1. 文档信息结构体 (DocInfo)：

    • 定义了存储文档信息的结构体，包括标题、内容、URL和文档ID。

  2. 倒排列表元素结构体 (InvertedElem)：

    • 定义了倒排列表中的元素结构体，包括文档ID、关键字和关键字权重。

  3. 单例模式的实现 (Index 类)：

    • Index 类使用单例模式来确保整个程序中只有一个索引实例。
    • 构造函数、拷贝构造函数和赋值操作符都是私有的，防止外部直接创建实例。
    • GetInstance 方法用于获取索引实例，采用双重检查锁定模式来确保线程安全。
    • GetInvertedList 方法用于根据关键字获取对应的倒排列表。

  4. 全局变量和互斥锁：

    • instance 是一个静态指针，指向Index类的实例。
    • mtx 是一个静态互斥锁，用于保护单例模式的实例创建过程。

总体来说，上面的代码展示了一个索引系统的基础框架，包括文档信息的存储结构和单例模式的索引管理。

2. 正排索引的建立

// 定义宏常量
#define NUM 101// 正排索引存储文档信息
std::vector<DocInfo> forward_index;// 根据文档ID获取文档信息
DocInfo* GetForwardIndex(uint64_t doc_id) {if (doc_id >= forward_index.size()) {std::cerr << "doc_id out of range, error!" << std::endl;return nullptr;}return &forward_index[doc_id];
}// 构建索引，输入为处理完毕的数据文件路径
bool BuildIndex(const std::string& input) {// 打开输入文件std::ifstream in(input, std::ios::in | std::ios::binary);if (!in.is_open()) {std::cerr << "sorry, " << input << " open error" << std::endl;return false;}// 读取文件行并构建索引std::string line;int count = 0;std::string bar(NUM, ' '); // 创建进度条bar[1] = '=';while (std::getline(in, line)) {DocInfo* doc = BuildForwardIndex(line);if (nullptr == doc) {continue;}BuildInvertedIndex(*doc);count++;// 显示进度if (count % 86 == 0) {int cnt = count / 86 + 1;bar[cnt] = '=';std::cout << "成功建立索引进度: " << bar << " [" << cnt << "%]" << "\r";std::cout.flush();}}std::cout << std::endl;return true;
}// 私有辅助函数，用于构建正排索引
DocInfo* BuildForwardIndex(const std::string& line) {// 分割字符串为标题、内容和URLstd::vector<std::string> results;const std::string sep = "\3"; // 行内分隔符ns_util::StringUtil::Split(line, &results, sep);if (results.size() != 3) {return nullptr;}// 创建文档信息并添加到正排索引DocInfo doc;doc.title = results[0];doc.content = results[1];doc.url = results[2];doc.doc_id = forward_index.size();// 插入到正排索引的vectorforward_index.push_back(std::move(doc));return &forward_index.back();
}

⭕代码分析

  1. forward_index 是一个 std::vector，用于存储所有文档的正排索引信息。
  2. GetForwardIndex 函数通过文档ID从正排索引中检索文档信息。如果文档ID超出范围，则返回空指针并打印错误信息。
  3. BuildIndex 函数用于从数据文件中读取文档数据并构建索引。它打开输入文件，逐行读取并处理每一行，构建正排索引和倒排索引，并显示进度条。
  4. BuildForwardIndex 函数是一个私有辅助函数，用于构建单个文档的正排索引条目。它将输入行分割为标题、内容和URL，创建一个 DocInfo 对象，并将其添加到 forward_index 向量中。

3. 倒排索引的建立

// 定义宏常量
#define X 10
#define Y 1// 倒排索引存储关键字到倒排列表的映射
std::unordered_map<std::string, InvertedList> inverted_index;// 定义倒排列表的类型为InvertedElem元素的向量
typedef std::vector<InvertedElem> InvertedList;// 私有辅助函数，用于构建倒排索引
bool BuildInvertedIndex(const DocInfo& doc) {// 分词并统计词频struct word_cnt {int title_cnt;int content_cnt;word_cnt() : title_cnt(0), content_cnt(0) {}};// 用来暂存词频的映射表std::unordered_map<std::string, word_cnt> word_map;// 对标题进行分词std::vector<std::string> title_words;ns_util::JiebaUtil::CutString(doc.title, &title_words);// 对标题进行词频统计for (std::string s : title_words) {boost::to_lower(s);  // 将单词转换为小写word_map[s].title_cnt++;  // 如果存在就增加计数，否则创建新条目}// 对文档内容进行分词std::vector<std::string> content_words;ns_util::JiebaUtil::CutString(doc.content, &content_words);// 对内容进行词频统计for (std::string s : content_words) {boost::to_lower(s);word_map[s].content_cnt++;}// 构建倒排列表for (const auto& word_pair : word_map) {InvertedElem item;item.doc_id = doc.doc_id;item.word = word_pair.first;// 计算权重，标题中的词乘以X，内容中的词乘以Yitem.weight = X * word_pair.second.title_cnt + Y * word_pair.second.content_cnt;// 获取对应关键字的倒排列表，并添加新的倒排元素InvertedList& inverted_list = inverted_index[word_pair.first];inverted_list.push_back(std::move(item));}return true;
}

⭕代码分析

  1. 定义数据结构：

    • DocInfo 结构体定义了文档信息，包括标题、内容、URL和唯一的文档ID。
    • InvertedElem 结构体定义了倒排列表中的元素，包括文档ID、关键字和权重。
    • InvertedList 类型定义为 std::vector<InvertedElem>，表示一个倒排列表，包含多个 InvertedElem 元素。

  2. 构建正排索引：

    • forward_index 是一个 std::vector<DocInfo>，用于存储所有文档的正排索引信息。
    • GetForwardIndex 函数通过文档ID从正排索引中检索文档信息。

  3. 构建倒排索引：

    • inverted_index 是一个 std::unordered_map<std::string, InvertedList>，用于存储关键字到倒排列表的映射。
    • BuildInvertedIndex 函数用于根据文档信息构建倒排索引。它首先对文档的标题和内容进行分词，然后统计每个词在标题和内容中出现的次数（词频）。
    • 每个分词后的词都会被转换为小写，以便进行不区分大小写的搜索。
    • 为每个词创建一个 InvertedElem 对象，并根据其在标题和内容中的出现次数计算权重。
    • 将 InvertedElem 对象添加到 inverted_index 中对应关键字的倒排列表中。

  4. 处理文本数据：

    • BuildIndex 函数打开并读取输入文件，该文件包含处理完毕的文档数据。
    • 对文件中的每一行数据，使用 BuildForwardIndex 函数构建正排索引条目，并调用 BuildInvertedIndex 函数构建倒排索引。
    • 在构建索引的过程中，显示进度条以指示索引构建的进度。

整体来说，上面这段代码展示了如何从文本数据中提取文档信息，并构建正排索引和倒排索引，以便在搜索引擎中快速检索相关文档。通过倒排索引，可以有效地根据关键字找到所有相关文档，提高搜索效率。

三、整体代码

⭕index.hpp

#pragma once
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <unordered_map>
#include <mutex>
#include "util.hpp" 
#include "log.hpp"  #define NUM 101
#define X 10
#define Y 1namespace ns_index {// 定义文档信息结构体struct DocInfo {std::string title;   // 文档的标题std::string content; // 文档内容（去标签后）std::string url;     // 文档的URLuint64_t doc_id;     // 文档的唯一ID};// 定义倒排列表中的元素结构体struct InvertedElem {uint64_t doc_id;   // 文档IDstd::string word;  // 关键字int weight;        // 关键字权重InvertedElem() : weight(0) {} // 默认构造函数，权重初始化为0};// 倒排拉链储存列表typedef std::vector<InvertedElem> InvertedList;// 定义索引类Indexclass Index {private:// 正排索引存储文档信息std::vector<DocInfo> forward_index;// 倒排索引存储关键字到倒排列表的映射std::unordered_map<std::string, InvertedList> inverted_index;// 构造函数、拷贝构造函数和赋值操作符都设置为私有，防止被实例化Index() {}Index(const Index&) = delete;Index& operator=(const Index&) = delete;// 单例模式的实例指针static Index* instance;// 保护单例模式的互斥锁static std::mutex mtx;public:// 析构函数~Index() {}// 获取单例模式的实例static Index* GetInstance() {// 双重检查锁定模式，确保线程安全地获取单例if (nullptr == instance) {mtx.lock();if (nullptr == instance) {instance = new Index();}mtx.unlock();}return instance;}// 根据文档ID获取文档信息DocInfo* GetForwardIndex(uint64_t doc_id) {if (doc_id >= forward_index.size()) {std::cerr << "doc_id out of range, error!" << std::endl;return nullptr;}return &forward_index[doc_id];}// 根据关键字获取倒排拉链InvertedList* GetInvertedList(const std::string& word) {auto iter = inverted_index.find(word);if (iter == inverted_index.end()) {std::cerr << word << " have no InvertedList" << std::endl;return nullptr;}return &(iter->second);}// 构建索引，输入为处理完毕的数据文件路径bool BuildIndex(const std::string& input) {// 打开输入文件std::ifstream in(input, std::ios::in | std::ios::binary);if (!in.is_open()) {std::cerr << "sorry, " << input << " open error" << std::endl;return false;}// 读取文件行并构建索引std::string line;int count = 0;std::string bar(NUM, ' '); // 创建进度条bar[1] = '=';while (std::getline(in, line)) {DocInfo* doc = BuildForwardIndex(line);if (nullptr == doc) {continue;}BuildInvertedIndex(*doc);count++;// 显示进度if (count % 86 == 0) {int cnt = count / 86 + 1;bar[cnt] = '=';std::cout << "成功建立索引进度: " << bar << " [" << cnt << "%]" << "\r";std::cout.flush();}}std::cout << std::endl;return true;}private:// 私有辅助函数，用于构建正排索引DocInfo* BuildForwardIndex(const std::string& line) {// 分割字符串为标题、内容和URLstd::vector<std::string> results;const std::string sep = "\3"; // 行内分隔符ns_util::StringUtil::Split(line, &results, sep);if (results.size() != 3) {return nullptr;}// 创建文档信息并添加到正排索引DocInfo doc;doc.title = results[0];doc.content = results[1];doc.url = results[2];doc.doc_id = forward_index.size();//插入到正排索引的vectorforward_index.push_back(std::move(doc));return &forward_index.back();}// 私有辅助函数，用于构建倒排索引bool BuildInvertedIndex(const DocInfo& doc) {// 分词并统计词频struct word_cnt{int title_cnt;int content_cnt;word_cnt():title_cnt(0), content_cnt(0){}};std::unordered_map<std::string, word_cnt> word_map; //用来暂存词频的映射表//对标题进行分词std::vector<std::string> title_words;ns_util::JiebaUtil::CutString(doc.title, &title_words);//对标题进行词频统计for(std::string s : title_words){boost::to_lower(s);      //需要统一转化成为小写word_map[s].title_cnt++; //如果存在就获取，如果不存在就新建}//对文档内容进行分词std::vector<std::string> content_words;ns_util::JiebaUtil::CutString(doc.content, &content_words);//对内容进行词频统计for(std::string s : content_words){boost::to_lower(s);word_map[s].content_cnt++;}// 构建倒排列表for (const auto& word_pair : word_map) {InvertedElem item;item.doc_id = doc.doc_id;item.word = word_pair.first;item.weight = X * title_cnt.title_cnt + Y * content_cnt.content_cnt;InvertedList& inverted_list = inverted_index[word_pair.first];inverted_list.push_back(std::move(item));}return true;}};// 初始化单例模式的实例指针为nullptrIndex* Index::instance = nullptr;// 初始化互斥锁std::mutex Index::mtx;
}

这篇关于BoostCompass(建立正排索引和倒排索引模块)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/901710。

相关文章

Python通用唯一标识符模块uuid使用案例详解

Python通用唯一标识符模块uuid使用案例详解

《Python通用唯一标识符模块uuid使用案例详解》Pythonuuid模块用于生成128位全局唯一标识符,支持UUID1-5版本,适用于分布式系统、数据库主键等场景,需注意隐私、碰撞概率及存储优... 目录简介核心功能1. UUID版本2. UUID属性3. 命名空间使用场景1. 生成唯一标识符2. 数
阅读更多...
浅谈mysql的not exists走不走索引

浅谈mysql的not exists走不走索引

《浅谈mysql的notexists走不走索引》在MySQL中,​NOTEXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引,下面就来介绍一下mysql的notexists走不走索... 在mysql中，​NOT EXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引。以下
阅读更多...
Python中re模块结合正则表达式的实际应用案例

Python中re模块结合正则表达式的实际应用案例

《Python中re模块结合正则表达式的实际应用案例》Python中的re模块是用于处理正则表达式的强大工具,正则表达式是一种用来匹配字符串的模式,它可以在文本中搜索和匹配特定的字符串模式,这篇文章主... 目录前言re模块常用函数一、查看文本中是否包含 A 或 B 字符串二、替换多个关键词为统一格式三、提
阅读更多...
MySQL之InnoDB存储引擎中的索引用法及说明

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》：本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二
阅读更多...
全面解析MySQL索引长度限制问题与解决方案

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言：为什么会有索引键长度问题？一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决
阅读更多...
MySQL中的索引结构和分类实战案例详解

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2
阅读更多...
python3如何找到字典的下标index、获取list中指定元素的位置索引

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》：本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat
阅读更多...
从入门到精通MySQL 数据库索引(实战案例)

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么？能干嘛？核心作用：二、索引的 4 种主要类型（附通俗例子）1. BTree 索引（
阅读更多...
一文深入详解Python的secrets模块

一文深入详解Python的secrets模块

《一文深入详解Python的secrets模块》在构建涉及用户身份认证、权限管理、加密通信等系统时,开发者最不能忽视的一个问题就是“安全性”,Python在3.6版本中引入了专门面向安全用途的secr... 目录引言一、背景与动机：为什么需要 secrets 模块？二、secrets 模块的核心功能1. 基
阅读更多...
MySQL 添加索引5种方式示例详解(实用sql代码)

MySQL 添加索引5种方式示例详解(实用sql代码)

《MySQL添加索引5种方式示例详解(实用sql代码)》在MySQL数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中,下面给大家分享MySQL添加索引5种方式示例详解(实用sql代码),... 在mysql数据库中添加索引可以帮助提高查询性能，尤其是在数据量大的表中。索引可以在创建表时定义，也可
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2