倒排索引C++实现

信息检索导论的课程第一章讲了倒排索引，关于倒排索引之前一直都是只明白了概念而没有动手实现，今天本想实现一下，无从下手，所以直接从网上找来代码阅读一下，现记录一下对代码的理解。
关于倒排索引的概念，参考下图，值得注意的是，在接下来的代码中存储的是文件的名字，而不是序号。

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