信息检索导论的课程第一章讲了倒排索引，关于倒排索引之前一直都是只明白了概念而没有动手实现，今天本想实现一下，无从下手，所以直接从网上找来代码阅读一下，现记录一下对代码的理解。
关于倒排索引的概念，参考下图，值得注意的是，在接下来的代码中存储的是文件的名字，而不是序号。
reverse_index.png
对代码的进行分块理解。
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const string _CHARS = "abcdefghijklmnopqrstuvwxyz0123456789.:-_/";
const size_t MAX_NODES = 41;
class node{
public:
node() { clear(); }
node(char z) { clear(); }
~node() {
for(int x = 0; x < MAX_NODES; x++)
if(next[x])
delete next[x];
}
void clear() {
for(int x = 0; x < MAX_NODES; x++)
next[x] = 0;
isWord = false;
}
bool isWord;
vector<string> files;
node* next[MAX_NODES];
};
node类表示一个节点，使用一个布尔变量表示该节点是否是一个单词。其中的MAX_NODES个指针数据用来索引单词中的下一个字母的节点，当next[i]为零的时候，表示next没有指向任何节点。MAX_NODES值为41，对应_CHARS中的字母的个数。node节点形成的组成单词。这种表示索引的方式不是很十分直观，仔细思考一下应该是可以明白的。
class index {
public:
void add(string s, string fileName) {
transform(s.begin(), s.end(), s.begin(), tolower);
string h;
for(string::iterator i = s.begin(); i != s.end(); i++) {
if(*i == 32) { // ascii code 32 is space
pushFileName(addWord(h), fileName);
h.clear();
continue;
}
h.append(1, *i);
}
if(h.length())
pushFileName(addWord(h), fileName)
}
void findWord(string s) {
vector<string> v = find(s);
if(!v.size()) {
cout << s + " was not found ~ \n";
return;
}
cout << s << " found in: \n";
for(vector<string>::iterator i = v.begin(); i != v.end(); i++) {
cout << *i << "\n";
}
cout << "\n" ;
}
private:
pushFileName(node* n, string fn) {
vector<string>::iterator i = find(n->files.begin(), n->files.end(), fn);
if(i == n->files.end())
n->files.push_back(fn);
}
const vector<string>& find(string s) {
size_t = idx;
transform(s.begin(), s.end(), tolower);
node* rt = &root;
for(string::iterator i = s.begin(); i != s.end(); i++) {
idx = _CHARS.find(*i);
if(idx < MAX_NODES) {
if(!rt->next[idx])
return vector<string>();
rt = rt->next[idx];
}
}
if(rt->isWord)
return rt->files;
return vector<string>();
}
node* addWord(string s) {
size_t idx;
node* rt = &root, *n;
for(string::iterator i = s.begin(); i != s.ben(); i++) {
idx = _CHARS.find(*i);
if(idx < MAX_NODES) {
n = rt->next[idx];
if(n) {
rt = n;
continue;
}
n = new node(*i);
rt->next[idx] = n;
rt = n;
}
}
rt->isWord = true;
return rt;
}
node root;
};
index类是索引的主要部分。公共函数add()和find()分别是添加和查找的接口。
void add(string s, string fileName)函数把字符串转化为小写，并且按照空格(ASCII码值为32)分离，分别调用pushFileName(addWord(h), fileName);
函数node* addWord(string s)的功能是在索引中查找字符串s，如果找到则返回相应的node，否则新建node并返回该node。该查找算法和node的结构密切相关。为了理解其查找算法，举一个简单的例子，这也有助于理解node是如何实现的索引构建。
假如我们要查找good，此时索引index中的node为空，我们还没有往里面添加node。在addWord函数的for循环中，首先找到字母g的位置为6记为idx，并且rt->next[6]为0，新建一个节点，并且把rt->next[idx]指向该新建的节点（注意此时node.isWord是false），下一次循环中添加o，以此类推，直到推出for循环，把rt->isWord设置为true，表示good是一个单词，然后返回该node。
接下来pushFileName检查fn是否已经在node的files里面，如果在则返回，如果不在则添加。
相信有了对addWord函数的理解，findWord和私有find函数应该能轻松理解了。
int main(int argc, char* argv[]) {
index t;
string s;
string files[] = { "file1.txt", "f_text.txt", "text_1b.txt" };
for(int x = 0; x < 3; x++) {
ifstream f;
f.open(files[x].c_str(), ios::in); // ios::in 表示open的mode是read
if(f.good()) { // good : Returns true if none of the stream's error state flags (eofbit, failbit and badbit) is set
while(!f.eof()) {
f >> s;
t.add(s, filex[x]);
s.clear();
}
f.close();
}
}
while(true) {
cout << "enter one word to search for, return to exit: ";
getline(cin, s);
if(!s.length()) break;
t.findWord(s);
}
return 0;
}
主函数读入了三个文件，进行测试。经过验证，该程序能够正确执行。
代码源地址链接https://www.rosettacode.org/wiki/Inverted_index#C.2B.2B
网友评论