能帮我写一个c++版的倒排索引数据结构吗
时间: 2023-06-20 10:06:15 浏览: 91
当然可以,下面是一个简单的C++实现:
```c++
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
class InvertedIndex {
public:
void addDocument(int docId, const string& document) {
// 分割文档
vector<string> words = split(document);
// 统计每个单词在文档中出现的次数
unordered_map<string, int> wordFreq;
for (const auto& word : words) {
++wordFreq[word];
}
// 将每个单词记录在倒排索引中
for (const auto& p : wordFreq) {
const string& word = p.first;
int freq = p.second;
index_[word][docId] = freq;
}
}
vector<int> search(const string& query) const {
vector<string> words = split(query);
unordered_map<int, int> docFreq;
// 统计包含查询词的文档频率
for (const auto& word : words) {
if (index_.find(word) != index_.end()) {
const auto& docMap = index_.at(word);
for (const auto& p : docMap) {
int docId = p.first;
int freq = p.second;
docFreq[docId] += freq;
}
}
}
// 将文档频率转为文档得分
vector<pair<int, int>> docScores;
for (const auto& p : docFreq) {
int docId = p.first;
int freq = p.second;
docScores.emplace_back(docId, freq);
}
// 按得分排序
sort(docScores.begin(), docScores.end(), [](const auto& a, const auto& b) {
return a.second > b.second;
});
// 取前10个文档
vector<int> results;
for (int i = 0; i < min(10, static_cast<int>(docScores.size())); ++i) {
results.push_back(docScores[i].first);
}
return results;
}
private:
// 分割文本
vector<string> split(const string& text) const {
vector<string> words;
string word;
for (const auto& c : text) {
if (isspace(c)) {
if (!word.empty()) {
words.push_back(word);
word.clear();
}
} else {
word.push_back(c);
}
}
if (!word.empty()) {
words.push_back(word);
}
return words;
}
// 倒排索引
unordered_map<string, unordered_map<int, int>> index_;
};
int main() {
InvertedIndex index;
index.addDocument(1, "the cat in the hat");
index.addDocument(2, "the fat cat sat on the mat");
index.addDocument(3, "the red cat chased the mouse");
vector<int> results = index.search("cat");
for (int docId : results) {
cout << docId << endl;
}
return 0;
}
```
该实现使用了哈希表存储倒排索引,将每个单词映射到一个包含文档编号和词频的哈希表。在搜索时,统计每个包含查询词的文档的得分,并按得分排序,返回前10个文档编号作为搜索结果。
阅读全文