1.定义

倒排索引常使用在搜索引擎当中，是搜索引擎为文档内容建立索引，实现内容快速检索必不可少的数据结构。倒排索引是由单词的集合“词典”和倒排列表的集合“倒排文件”组成的。

倒排索引的存储：内存索引和B+树索引。

1.1 正排索引

假设目前有两个 HTML 页面，一个页面内容是 "I like search engines."，而另一个页面内容是 "I search keywords in google."，现在我们将其按照单词进行划分，形成下表所示的结构：

其中，每一行表示一个页面，每一列表示一个单词，0 表示该单词未出现在该页面中，而 1 则表示该单词出现在该页面中。那么当我们搜索含有关键词 "engine" 的页面时，我们需要遍历上表的每一行，这就是正排索引。

其定义如下：当用户发起查询时（假设查询为一个关键词），搜索引擎会扫描索引库中的所有文档，找出所有包含关键词的文档，这样依次从文档中去查找是否含有关键词的方法叫做正排索引。

1.2 倒排索引

现在我们交换上表中的行和列，就会形成如下所示的表格结构：

更进一步的，我们将其转化为如下形式：

那么此时我们搜索含有关键词 "engine" 的页面，可以直接在常数时间复杂度内找到其结果为 P1，这就是倒排索引。并且，我们还可以在建立索引的时候为每个页面加上其他的衡量参数，在建立索引时就可以根据这些参数完成页面排序。

其定义如下：搜索引擎会把正排索引变为倒排索引，即把“文档→单词”的形式变为“单词→文档”的形式。

倒排索引的结构如下图所示：

2.代码实现

2.1 类型定义

倒排项的定义如下:

struct InvertTerm {
    InvertTerm(const string& docid, int freqs, int loc)
        : docid_(docid)
        , freqs_(freqs) {
        locations_.emplace_back(loc);
    }
    
    bool operator==(const InvertTerm& term) const {
        return docid_ == term.docid_;
    }
    
    bool operator<(const InvertTerm& term) const {
        return docid_ < term.docid_;
    }
    
    string    docid_;     // 单词所在的文档
    int       freqs_;     // 单词出现的次数
    list<int> locations_; // 单词出现的位置
};

倒排列表的定义如下：

class InvertList {
public:
    InvertList()  = default;
    ~InvertList() = default;
    
public:
    // 添加倒排项
    void addTerm(const string& docid, int loc);
    // 获取倒排列表内容
    const list<InvertTerm>& getInvertList() const {
        return termList_;
    }
    
private:
    list<InvertTerm> termList_; // 存储当前倒排列表所有的倒排项
};

倒排索引的定义如下：

class InvertIndex {
public:
    // 查询接口
    void query(const string& phrase);
    // 设置本地搜索路径
    void setSearchPath(const string& path);
    // 添加文件后缀
    void addSuffix(const string& suffix);
    // 删除文件后缀
    void removeSuffix(const string& suffix);
    // 清空文件后缀
    void clearSuffix();
    // 后缀是否已经存在
    bool isSuffixExist(const string& suffix);
    
private:
    // 创建倒排索引结构
    void createInvertedIndex();
    // 递归扫描路径下的所有文件
    int getAllFile(const char* path);
    // 去掉单词前后多余的字符
    char* trim(char* word);
    
private:
    vector<string>                    suffixs_;   // 过滤文档后缀
    list<string>                      fileList_;  // 存储所有需要建立倒排索引的文件
    unordered_map<string, InvertList> invertMap_; // 词典+倒排列表
};

2.2 创建倒排索引

创建倒排索引的相关代码如下：

void InvertIndex::createInvertedIndex() {
    int curidx = 1;
    for (string& filePath : fileList_) {
        cout << "Current progress: " << curidx++ << " / " << fileList_.size();
        FILE* pf = fopen(filePath.c_str(), "r");
        if (pf == nullptr) {
            cout << " [Failed to open " << filePath << "!]" << endl;
            continue;
        }
        
        // 按行读取文件中的内容 按照空格进行分词
        vector<string> wordList;
        int            loc             = 0;
        const int      LINE_SIZE       = 2048;
        char           line[LINE_SIZE] = { 0 };
        
        while (!feof(pf)) {
            // 读一行文件内容
            fgets(line, LINE_SIZE, pf);
            
            // 按照空格进行分词
            char* word = strtok(line, " ");
            while (word != nullptr) {
                // 过滤前后多余的空格和换行符
                word = trim(word);
                if (strlen(word) > 0) {
                    wordList.emplace_back(word);
                }
                word = strtok(nullptr, " ");
            }
            
	        // 开始给单词创建倒排列表
            for (string& w : wordList) {
                loc++;
                auto it = invertMap_.find(w);
                if (it == invertMap_.end()) {
                    // 新建该单词的倒排列表
                    InvertList list;
                    list.addTerm(filePath, loc);
                    invertMap_.emplace(w, list);
                } else {
                    it->second.addTerm(filePath, loc);
                }
            }
        }
        
        fclose(pf);
        cout << endl;
    }
}

2.3 关键词搜索

关键词搜索相关的代码如下：

void InvertIndex::query(const string& phrase) {
    // 先进行句子分词操作
    vector<string> wordList;
    char*          word = strtok(const_cast<char*>(phrase.c_str()), " ");
    while (word != nullptr) {
        word = trim(word);
        if (strlen(word) > 0) {
            wordList.emplace_back(word);
        }
        word = strtok(nullptr, " ");
    }
    
    if (wordList.empty())
        return;
        
    if (wordList.size() == 1) {
        auto it = invertMap_.find(wordList[0]);
        if (it == invertMap_.end()) {
            cout << "No match was found!" << endl;
            return;
        }
        
        for (auto& term : it->second.getInvertList()) {
            cout << "id: " << term.docid_ << "  freq: " << term.freqs_ << endl;
        }
    } else {
        // 搜索多个单词
        vector<InvertList> invertList;
        for (int i = 0; i < wordList.size(); ++i) {
            auto it = invertMap_.find(wordList[i]);
            if (it != invertMap_.end()) {
                invertList.emplace_back(it->second);
            }
        }
        
        // 开始遍历所有的倒排列表 求倒排项的交集
        vector<InvertTerm> v1(invertList[0].getInvertList().begin(),
            invertList[0].getInvertList().end());
        vector<InvertTerm> termShared;
        for (int i = 1; i < invertList.size(); i++) {
            vector<InvertTerm> v2(invertList[i].getInvertList().begin(),
                invertList[i].getInvertList().end());
                
            // 使用set_intersection时要保证数据有序
            sort(v1.begin(), v1.end());
            sort(v2.begin(), v2.end());
            set_intersection(v1.begin(), v1.end(),
                v2.begin(), v2.end(),
                back_inserter(termShared));
                
            v1.swap(termShared);
            termShared.clear();
        }
        
        for (auto& term : v1) {
            cout << "id: " << term.docid_ << "  freq: " << term.freqs_ << endl;
        }
    }
}

完整的代码见 Kohirus-Github。