当前位置：首页 > news >正文

倒排索引实操

news 2025/7/22 9:30:09

倒排索引（Inverted Index）是搜索引擎中用于快速全文检索的核心数据结构。它通过将文档中的单词映射到包含该单词的文档列表及其位置信息，实现了高效的查询功能。以下是倒排索引的详细解释和构建过程：
倒排索引的基本结构
倒排索引通常包含以下两个主要部分：
词典（Dictionary）：存储所有唯一的单词及其对应的倒排列表。
倒排列表（Inverted List）：记录每个单词在哪些文档中出现，以及出现的位置。
构建倒排索引的步骤
分词（Tokenization）：将文档内容分割成单词或短语。
归一化（Normalization）：将单词转换为统一的形式，如小写化、去除标点符号等。
索引构建（Indexing）：为每个单词生成倒排列表，记录其在文档中的位置。
存储索引（Storing）：将构建好的倒排索引存储在内存或磁盘中。

main.cpp

void testInvertedIndex()
{InvertedSearchIndex objIndex;objIndex.BuildIndex(L"D:\\Code\\Local\\Updater\\Document\\Readme.txt");std::cout << "\nInput text to search: ";std::string strInput;std::cin >> strInput;std::wstring wstrSearchDir = Utils::Utf8ToUtf16(Utils::Gbk2Utf8(strInput));std::vector<int64_t> listMatchPos;objIndex.QueryInvertedIndex(wstrSearchDir, listMatchPos);std::cout << "Matched pos size: " << listMatchPos.size() << "\n";
}

InvertedSearchIndex.h

#pragma once
#include <vector>
#include <string>
#include <unordered_map>class InvertedSearchIndex
{
public:bool BuildIndex(const std::wstring& strFile);bool QueryInvertedIndex(const std::wstring& wstrInput, std::vector<int64_t>& listMatchPos);private:void build_index(const std::string& wstrData, int64_t nOffset = 0);std::list<std::wstring> tokenize(const std::wstring& text);std::wstring to_lower(const std::wstring& wstrInput);std::vector<int64_t> search_term(const std::wstring& wstrInput);bool check_consecutive_positions(const std::vector<std::vector<int64_t>>& listPos, std::vector<int64_t>& listMatch);private:std::unordered_map<std::wstring, std::vector<int64_t>> m_listIndex;};

InvertedSearchIndex.cpp

#include "InvertedSearchIndex.h"
#include <fstream>
#include <iostream>
#include <memory>
#include <cwctype>
#include <locale>
#include <codecvt>
#include <algorithm>
#include <unordered_set>
#include "../include/Utils/Conversion.h"bool InvertedSearchIndex::BuildIndex(const std::wstring& strFile)
{// Tips: it should convert filename to local encode, don't use wifstream// Windows, it needs GetACP(), and then user MultiByteToWideChar or WideCharToMultiByte// unixs: it just considers utf8 or icov lib(public)std::string strLocalFile = Utils::Unicode2Gbk(strFile);std::ifstream fin(strLocalFile, std::ios::in| std::ios::binary);if (!fin.is_open()) {std::cout << "Open file failed: " << strLocalFile << "\n";return false;}fin.seekg(0, std::ios::end);std::streamsize nFileSize = fin.tellg();fin.seekg(0, std::ios::beg);const std::streamsize nSliceSize = 10 * 1024 * 1024;int nIndex = 0;while (nFileSize > 0) {std::streamsize nBlockSize = (nFileSize > nSliceSize) ? nSliceSize : nFileSize;std::vector<char> buffer(nBlockSize);fin.read(buffer.data(), nBlockSize);if (!fin) {break;}nFileSize -= nBlockSize;std::string strFileData(buffer.data(), nBlockSize);build_index(strFileData, nIndex * nSliceSize);++nIndex;}fin.close();return true;
}bool InvertedSearchIndex::QueryInvertedIndex(const std::wstring& wstrInput, std::vector<int64_t>& listMatchPos)
{std::list<std::wstring> listTokens = tokenize(wstrInput);std::vector<std::vector<int64_t>> listPos;for (const auto& item : listTokens) {auto listTmpPos = search_term(item);if (listTmpPos.empty()) return false;listPos.emplace_back(listTmpPos);}if (listPos.size() == 1) {listMatchPos = listPos[0];return !listMatchPos.empty();}// Tips: it should check exist only, not gain all matchsreturn check_consecutive_positions(listPos, listMatchPos);
}void InvertedSearchIndex::build_index(const std::string& strData, int64_t nOffset/* = 0*/)
{std::wstring wstrData = Utils::Utf8ToUtf16(strData);std::list<std::wstring> listTokens = tokenize(wstrData);int64_t nPos = 0;for (const auto& item : listTokens) {std::wstring wstrNormaliz = to_lower(item);m_listIndex[wstrNormaliz].emplace_back(nPos + nOffset);++nPos;}
}std::list<std::wstring> InvertedSearchIndex::tokenize(const std::wstring& wstrData)
{auto funcCheckChinese = [=](wchar_t chInput) {return (chInput >= 0x4E00 && chInput <= 0x9FFF) ||(chInput >= 0x3400 && chInput <= 0x4DBF) ||(chInput >= 0x20000 && chInput <= 0x2A6DF);};std::list<std::wstring> listTokens;std::wstring wstrTmpToken;for (wchar_t c : wstrData) {if (std::iswspace(c) || std::iswpunct(c)) {if (!wstrTmpToken.empty()) {listTokens.push_back(wstrTmpToken);wstrTmpToken.clear();}}else if (funcCheckChinese(c)) {if (!wstrTmpToken.empty()) {listTokens.push_back(wstrTmpToken);wstrTmpToken.clear();}listTokens.push_back(std::wstring(1, c));}else {wstrTmpToken.push_back(c);}}if (!wstrTmpToken.empty()) {listTokens.push_back(wstrTmpToken);}return listTokens;
}std::wstring InvertedSearchIndex::to_lower(const std::wstring& wstrInput)
{std::wstring result;result.reserve(wstrInput.size());for (wchar_t c : wstrInput) {if (c >= L'A' && c <= L'Z') {result.push_back(std::tolower(c));}else {result.push_back(c);}}return result;
}std::vector<int64_t> InvertedSearchIndex::search_term(const std::wstring& wstrInput)
{std::wstring normalized = to_lower(wstrInput);auto itFind = m_listIndex.find(normalized);if (itFind != m_listIndex.end()) {return itFind->second;}return std::vector<int64_t>{};
}bool InvertedSearchIndex::check_consecutive_positions(const std::vector<std::vector<int64_t>>& listPos, std::vector<int64_t>& listMatchPos)
{for (int64_t nPrePos : listPos[0]) {bool bMatch = true;int64_t nExpectedPos = nPrePos + 1;for (size_t i = 1; i < listPos.size(); i++) {auto it = std::lower_bound(listPos[i].begin(),listPos[i].end(),nExpectedPos);if (it == listPos[i].end() || *it != nExpectedPos) {bMatch = false;break;}nExpectedPos++;}if (bMatch) {listMatchPos.push_back(nPrePos);}}return !listMatchPos.empty();
}