一、什麼是反向索引？
1.1 概念
見其名知其意，有反向索引，對應肯定，有正向索引。
正向索引（forward index），反向索引（inverted index）更熟悉的名字是反向索引。
在搜尋引擎中每個檔案都對應一個檔案ID，檔案内容被表示為一系列關鍵詞的集合（實際上在搜尋引擎索引庫中，關鍵詞也已經轉換為關鍵詞ID）。例如“文檔1”經過分詞，提取了20個關鍵詞，每個關鍵詞都會記錄它在文檔中的出現次數和出現位置。
正向索引的結構如下：
“文檔1”的ID > 單詞1：出現次數，出現位置清單；單詞2：出現次數，出現位置清單；…………。
“文檔2”的ID > 此文檔出現的關鍵詞清單。
一般是通過key，去找value。
當使用者在首頁上搜尋關鍵詞“華為手機”時，假設隻存在正向索引（forward index），那麼就需要掃描索引庫中的所有文檔，找出所有包含關鍵詞“華為手機”的文檔，再根據打分模型進行打分，排出名次後呈現給使用者。因為網際網路上收錄在搜尋引擎中的文檔的數目是個天文數字，這樣的索引結構根本無法滿足實時傳回排名結果的要求。
是以，搜尋引擎會将正向索引重新建構為反向索引，即把檔案ID對應到關鍵詞的映射轉換為關鍵詞到檔案ID的映射，每個關鍵詞都對應着一系列的檔案，這些檔案中都出現這個關鍵詞。
反向索引的結構如下：
“關鍵詞1”：“文檔1”的ID，“文檔2”的ID，…………。
“關鍵詞2”：帶有此關鍵詞的文檔ID清單。
從詞的關鍵字，去找文檔。
1.2 單詞——文檔矩陣
單詞-文檔矩陣是表達兩者之間所具有的一種包含關系的概念模型，如下圖的每列代表一個文檔，每行代表一個單詞，打對勾的位置代表包含關系。
從縱向即文檔這個次元來看，每列代表文檔包含了哪些單詞，比如文檔1包含了詞彙1和詞彙4，而不包含其它單詞。從橫向即單詞這個次元來看，每行代表了哪些文檔包含了某個單詞。比如對于詞彙1來說，文檔1和文檔4中出現過單詞1，而其它文檔不包含詞彙1。矩陣中其它的行列也可作此種解讀。
搜尋引擎的索引其實就是實作“單詞-文檔矩陣”的具體資料結構。可以有不同的方式來實作上述概念模型，比如“反向索引”、“簽名檔案”、“字尾樹”等方式。但是各項實驗資料表明，“反向索引”是實作單詞到文檔映射關系的最佳實作方式，是以本博文主要介紹“反向索引”的技術細節。
1.3，反向索引基本概念
文檔(Document)：一般搜尋引擎的處理對象是網際網路網頁，而文檔這個概念要更寬泛些，代表以文本形式存在的存儲對象，相比網頁來說，涵蓋更多種形式，比如Word，PDF，html，XML等不同格式的檔案都可以稱之為文檔。再比如一封郵件，一條短信，一條微網誌也可以稱之為文檔。在本書後續内容，很多情況下會使用文檔來表征文本資訊。
**文檔集合(Document Collection)：**由若幹文檔構成的集合稱之為文檔集合。比如海量的網際網路網頁或者說大量的電子郵件都是文檔集合的具體例子。
**文檔編号(Document ID)：**在搜尋引擎内部，會将文檔集合内每個文檔賦予一個唯一的内部編号，以此編号來作為這個文檔的唯一辨別，這樣友善内部處理，每個文檔的内部編号即稱之為“文檔編号”，後文有時會用DocID來便捷地代表文檔編号。
**單詞編号(Word ID)：**與文檔編号類似，搜尋引擎内部以唯一的編号來表征某個單詞，單詞編号可以作為某個單詞的唯一表征。
**反向索引(Inverted Index)：**反向索引是實作“單詞-文檔矩陣”的一種具體存儲形式，通過反向索引，可以根據單詞快速擷取包含這個單詞的文檔清單。反向索引主要由兩個部分組成：“單詞詞典”和“倒排檔案”。
**單詞詞典(Lexicon)：**搜尋引擎的通常索引機關是單詞，單詞詞典是由文檔集合中出現過的所有單詞構成的字元串集合，單詞詞典内每條索引項記載單詞本身的一些資訊以及指向“倒排清單”的指針。
**倒排清單(PostingList)：**倒排清單記載了出現過某個單詞的所有文檔的文檔清單及單詞在該文檔中出現的位置資訊，每條記錄稱為一個倒排項(Posting)。根據倒排清單，即可獲知哪些文檔包含某個單詞。
**倒排檔案(Inverted File)：**所有單詞的倒排清單往往順序地存儲在磁盤的某個檔案裡，這個檔案即被稱之為倒排檔案，倒排檔案是存儲反向索引的實體檔案。
關于這些概念之間的關系，通過圖2可以比較清晰的看出來。
1.4 反向索引簡單執行個體
反向索引從邏輯結構和基本思路上來講非常簡單。下面我們通過具體執行個體來進行說明，使得讀者能夠對反向索引有一個宏觀而直接的感受。
假設文檔集合包含五個文檔，每個文檔内容如圖3所示，在圖中最左端一欄是每個文檔對應的文檔編号。我們的任務就是對這個文檔集合建立
中文和英文等語言不同，單詞之間沒有明确分隔符号，是以首先要用分詞系統将文檔自動切分成單詞序列。這樣每個文檔就轉換為由單詞序列構成的資料流，為了系統後續處理友善，需要對每個不同的單詞賦予唯一的單詞編号，同時記錄下哪些文檔包含這個單詞，在如此處理結束後，我們可以得到最簡單的反向索引 如下圖，“單詞ID”一欄記錄了每個單詞的單詞編号，第二欄是對應的單詞，第三欄即每個單詞對應的倒排清單。比如單詞“谷歌”，其單詞編号為1，倒排清單為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞
之是以說上圖所示反向索引是最簡單的，是因為這個索引系統隻記載了哪些文檔包含某個單詞，而事實上，索引系統還可以記錄除此之外的更多資訊。下圖是一個相對複雜些的反向索引，與上圖的基本索引系統比，在單詞對應的倒排清單中不僅記錄了文檔編号，還記載了單詞頻率資訊（TF），即這個單詞在某個文檔中的出現次數，之是以要記錄這個資訊，是因為詞頻資訊在搜尋結果排序時，計算查詢和文檔相似度是很重要的一個計算因子，是以将其記錄在倒排清單中，以友善後續排序時進行分值計算。在圖5的例子裡，單詞“創始人”的單詞編号為7，對應的倒排清單内容為：（3:1），其中的3代表文檔編号為3的文檔包含這個單詞，數字1代表詞頻資訊，即這個單詞在3号文檔中隻出現過1次，其它單詞對應的倒排清單所代表含義與此相同。
實用的反向索引還可以記載更多的資訊，下圖所示索引系統除了記錄文檔編号和單詞頻率資訊外，額外記載了兩類資訊，即每個單詞對應的“文檔頻率資訊”（對下圖的第三欄）以及在倒排清單中記錄單詞在某個文檔出現的位置資訊。
“文檔頻率資訊”代表了在文檔集合中有多少個文檔包含某個單詞，之是以要記錄這個資訊，其原因與單詞頻率資訊一樣，這個資訊在搜尋結果排序計算中是非常重要的一個因子。而單詞在某個文檔中出現的位置資訊并非索引系統一定要記錄的，在實際的索引系統裡可以包含，也可以選擇不包含這個資訊，之是以如此，因為這個資訊對于搜尋系統來說并非必需的，位置資訊隻有在支援“短語查詢”的時候才能夠派上用場。
以單詞“拉斯”為例，其單詞編号為8，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排清單為：{(3;1;<4>)，(5;1;<4>)},其含義為在文檔3和文檔5出現過這個單詞，單詞頻率都為1，單詞“拉斯”在兩個文檔中的出現位置都是4，即文檔中第四個單詞是“拉斯”。
1.5，樹形結構
B樹（或者B+樹）是另外一種高效查找結構，圖8是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字元序），而哈希方式則無須資料滿足此項要求。
B樹形成了層級查找結構，中間節點用于指出一定順序範圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的位址資訊，根據這個位址就可以提取出單詞字元串。
1.6 總結
單詞ID：記錄每個單詞的單詞編号；
單詞：對應的單詞；
文檔頻率：代表文檔集合中有多少個文檔包含某個單詞
倒排清單：包含單詞ID及其他必要資訊
DocId：單詞出現的文檔id
TF：單詞在某個文檔中出現的次數
POS：單詞在文檔中出現的位置
以單詞“加盟”為例，其單詞編号為6，文檔頻率為3，代表整個文檔集合中有三個文檔包含這個單詞，對應的倒排清單為{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含義是在文檔2，3，5出現過這個單詞，在每個文檔的出現過1次，單詞“加盟”在第一個文檔的POS是4，即文檔的第四個單詞是“加盟”，其他的類似。
這個反向索引已經是一個非常完備的索引系統，實際搜尋系統的索引結構基本如此。
二、字典樹
2.1 手寫反向索引
trie.insert(“華為”);
trie.insert(“華為手機”);
trie.insert(“華為平闆”);
trie.insert(“華為牛逼”);
trie.insert(“鴻蒙”);
trie.insert(“華為鴻蒙作業系統”);
文檔—《華為 華為手機 華為平闆 華為牛逼 鴻蒙 華為鴻蒙作業系統》
分詞
–華為
–華為手機
–華為平闆
–華為牛逼
–鴻蒙
–華為鴻蒙作業系統
針對上面的分詞放到字典樹之後的結果為
2.2 代碼手寫倒排
節點Node資料結構
@Data
public class Node {
private char content;//存在目前節點的字
private boolean isEnd;//是否是詞的結尾
private int count;//這個詞在這個字下面的分支的個數
private LinkedList<Node> childList;//子節點
/***
* @Description: 構造方法 初始化節點使用
*/
public Node(char c){
childList=new LinkedList<>();
isEnd=false;
content=c;
count=0;
}
/****
* @Description: 提供一個周遊node中的linkedList中是否有這個字。有就意味着可以繼續查找下去，沒有就沒有
*/
public Node subNode(char c){
if(null!=childList&&!childList.isEmpty()){
for (Node node : childList) {
if(node.content==c){
return node;
}
}
}
return null;
}
} public class TrieTree {
private Node root;//根
/***
* @Description: 因為隻有一個根
*/
public TrieTree(){
root=new Node(' ');//構造一個空的根節點
}
/***
* @Description: 查詢
* @Param: word 要判斷的詞
* @return: 是否存在
*/
public boolean search(String word){ //華為
Node current=root;//從根節點開始找
if(null!=word){
//轉成字元數組
char[] chars = word.toCharArray();
if(null!=chars&&chars.length>0){
for (char c : chars) {
Node node = current.subNode(c);
if(null==node){//如果傳回的子節點為空 說明不存在
return false;
}else{
current=current.subNode(c);
}
}
//判斷目前節點是否是結束節點
if(current.isEnd()){
return true;
}else{
return false;
}
}else{
return false;
}
}else{
return false;
}
}
/***
* @Description: 插入方法，先判斷是否有這個詞，(通過上面的寫的查詢方法) 如果沒有，。就一個一個按順序判斷裡面的字
* 如果有這個字，繼續判斷下一個，當沒有字個字的時候，對空上字new Node對象，放到上一個字的LindkedList裡面
*/
public void insert(String word){ //華為電腦
//判斷有沒有這個詞 有就直接說這個詞在整個字典數已存在
if(this.search(word)){
return;
}
//如果不存在 ，就從根節點一個一個找
Node current=root;
if(null!=word){
char[] chars = word.toCharArray();
if(null!=chars&&chars.length>0){
for (char c : chars) {
Node child = current.subNode(c);
if(null!=child){
current=child;
}else{
//構造新的
current.getChildList().add(new Node(c));
current=current.subNode(c);
}
current.setCount(current.getCount()+1);//出現次數+1
}
//循環結束之後把最後一個字變成isEnd是true
current.setEnd(true);
}
}
}
/***
* @Description: 删除分詞
* @Param: [word] 要删除的分詞
*/
public void deleteWord(String word) {
//查詢一個詞在不在字典樹
if (this.search(word) == false) {
return;
}
Node current = root;
if (null != word) {
char[] chars = word.toCharArray();
if (null != chars && chars.length > 0) {
for (char c : chars) {
Node node = current.subNode(c);
if (node.getCount() == 1) {
current.getChildList().remove(node);
return;
} else {
current.setCount(current.getCount() - 1);
current = node;
}
}
current.setEnd(false);//isend設定為false代表目前路上的字連起來不是一相詞了
}
}
}
} public class TestTrieTree {
public static void main(String[] args) {
String content="華為-華為手機-華為平闆-華為牛逼-鴻蒙-華為鴻蒙作業系統";
//模拟分詞
String[] split = content.split("-");
//構造字典樹
TrieTree trie = new TrieTree();
//把分詞插入
for (String s : split) {
trie.insert(s);
}
System.out.println(trie.search("華為"));
System.out.println(trie.search("華為手"));
trie.deleteWord("華為");
System.out.println(trie.search("華為"));
System.out.println(trie.search("華為手機"));
}
}