創(chuàng)建給定文檔的反向索引
確保數(shù)據(jù)不包含標點符號.
樣例
給出一個包括id與內(nèi)容的文檔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],
...
}
說明
文檔是有許多的單詞組成的妆丘，其中每個單詞也可以在同一個文檔中重復出現(xiàn)很多次锄俄，當然，同一個單詞也可以出現(xiàn)在不同的文檔中勺拣。
- 正排索引(forward index)：從文檔角度看其中的單詞奶赠，表示每個文檔（用文檔ID標識）都含有哪些單詞，以及每個單詞出現(xiàn)了多少次（詞頻）及其出現(xiàn)位置（相對于文檔首部的偏移量）药有。
- 倒排索引(inverted index毅戈，或inverted files)：從單詞角度看文檔，標識每個單詞分別在那些文檔中出現(xiàn)(文檔ID)愤惰，以及在各自的文檔中每個單詞分別出現(xiàn)了多少次（詞頻）及其出現(xiàn)位置（相對于該文檔首部的偏移量）苇经。
簡單記為：正排索引：文檔 ---> 單詞倒排索引：單詞 ---> 文檔
倒排索引有著廣泛的應用場景，比如搜索引擎宦言、大規(guī)模數(shù)據(jù)庫索引扇单、文檔檢索、多媒體檢索/信息檢索領域等等奠旺≈├剑總之，倒排索引在檢索領域是很重要的一種索引機制响疚。
代碼
/**
* 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 的內(nèi)容不存在或者已經(jīng)存在的 id 和要添加的 id 不一致兼都，把 id 加入 hash 表
if (n == 0 || rt.get(tmp).get(n - 1) != id)
rt.get(tmp).add(id);
}
}
