500. 反向索引

描述

创建给定文档的反向索引
确保数据不包含标点符号.

样例

给出一个包括id与内容的文档list(我们提供了document类)

[
{
"id": 1,
"content": "This is the content of document 1 it is very short"
},
{
"id": 2,
"content": "This is the content of document 2 it is very long bilabial bilabial heheh hahaha ..."
},
]
返回一个反向索引(hashmap的key是单词, value是文档的id).
{
"This": [1, 2],
"is": [1, 2],
...
}

说明
文档是有许多的单词组成的，其中每个单词也可以在同一个文档中重复出现很多次，当然，同一个单词也可以出现在不同的文档中。

1. 正排索引(forward index)：从文档角度看其中的单词，表示每个文档（用文档ID标识）都含有哪些单词，以及每个单词出现了多少次（词频）及其出现位置（相对于文档首部的偏移量）。
2. 倒排索引(inverted index，或inverted files)：从单词角度看文档，标识每个单词分别在那些文档中出现(文档ID)，以及在各自的文档中每个单词分别出现了多少次（词频）及其出现位置（相对于该文档首部的偏移量）。

简单记为：正排索引：文档 ---> 单词倒排索引：单词 ---> 文档
倒排索引有着广泛的应用场景，比如搜索引擎、大规模数据库索引、文档检索、多媒体检索/信息检索领域等等。总之，倒排索引在检索领域是很重要的一种索引机制。

代码

/**
 * Definition of Document:
 * class Document {
 *     public int id;
 *     public String content;
 * }
 */
public class Solution {
    /**
     * @param docs a list of documents
     * @return an inverted index
     */
    // 正向索引是遍历文件查找关键词
    // 反向索引是通过关键词得到具有该关键词的文件 id
    public Map<String, List<Integer>> invertedIndex(List<Document> docs) {
        Map<String, List<Integer>> results = new HashMap<String, List<Integer>>();
        for (Document doc : docs) {
            int id = doc.id;
            StringBuffer temp = new StringBuffer("");
            String content = doc.content;
            int n = content.length();
            for (int i = 0; i < n; ++i) {
                // if 判断条件成立表示遍历完了一个关键词
                // temp 一次只存储一个关键词
                if (content.charAt(i) == ' ') {
                    insert(results, temp.toString(), id);
                    temp = new StringBuffer("");
                } else
                    temp.append(content.charAt(i));
            }
            // 最后一个关键词的插入
            insert(results, temp.toString(), id);
        }
        return results;
    }

    // insert 功能把关键字和 id 对应
    // tmp 即为关键字
    public void insert(Map<String, List<Integer>> rt, String tmp, int id) {
        // tmp 关键字不存在
        if (tmp.equals("") || tmp == null)
            return;
        // 建立 HashMap 
        if (!rt.containsKey(tmp))
            rt.put(tmp, new ArrayList<Integer>());
        
        int n = rt.get(tmp).size();
        // hash 表中的 id 的内容不存在或者已经存在的 id 和要添加的 id 不一致，把 id 加入 hash 表
        if (n == 0 || rt.get(tmp).get(n - 1) != id)
            rt.get(tmp).add(id);
    }
}