倒排索引演算法

① 搜索引擎演算法中，什麼是正向索引什麼是倒排索引

倒排索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由於不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件。建立全文索引中有兩項非常重要，一個是如何對文本進行分詞，一是建立索引的數據結構。分詞的方法基本上是二元分詞法、最大匹配法和統計方法。索引的數據結構基本上採用倒排索引的結構。
分詞的好壞關繫到查詢的准確程度和生成的索引的大小。在中文分詞發展中，早期經常使用分詞方式是二元分詞法，該方法的基本原理是將包含中文的句子進行二元分割，不考慮單詞含義，只對二元單詞進行索引。因此該方法所分出的單詞數量較多，從而產生的索引數量巨大，查詢中會將無用的數據檢索出來，好處是演算法簡單不會漏掉檢索的數據。之後又發展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對常用單詞生成一個詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產生錯誤，比如「首飾和服裝」會將「和服」作為單詞分出。達夢資料庫採用的是改進的逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復雜的是通過統計方式進行分詞的方法。該方法採用隱式馬爾科夫鏈，也就是後一個單詞出現的概率依靠於前一個單詞出現的概率，最後統計所有單詞出現的概率的最大為分詞的依據。這個方法對新名詞和地名的識別要遠遠高於最大匹配法，准確度隨著取樣文本的數量的增大而提高。
二元分詞方法和統計方法是不依賴於詞典的，而最大匹配法分詞方法是依賴於詞典的，詞典的內容決定分詞結構的好壞。
全文檢索的索引被稱為倒排索引，之所以成為倒排索引，是因為將每一個單詞作為索引項，根據該索引項查找包含該單詞的文本。因此，索引都是單詞和唯一記錄文本的標示是一對多的關系。將索引單詞排序，根據排序後的單詞定位包含該單詞的文本。
步驟1）讀取一整條句子到變數str中，轉到步驟2

步驟2）從句子的尾端讀取1個字到變數word中，轉到步驟3

步驟3）在字典查找word中保存的單詞。如果存在則保存word，轉到步驟4，否則轉到步驟5）

步驟4）如果是字典中最大單詞或者超過最大單詞數（認定為新詞），從句尾去掉該單詞，返回步驟2

步驟5）讀取前一個字到word中，構成新單詞，轉到步驟3）

詞庫的內存數據結構和詞庫中單詞的匹配演算法

內存中單詞採用層次結構保存

假設字典中有如下的單詞：中國 中華民國 國家 人民 民主

在內存中按照如下方式按層排列，其中每一個方塊代表一個字，箭頭所指向為該單詞的前一個字

② 倒排索引

倒排索引(Inverted Index)：

倒排索引從邏輯結構和基本思路上講非常簡單，下面我們通過具體實例來進行說明，使得大家能夠對倒排索引有一個宏觀而直接的感受。

中文和英文等語言不同，單詞之間沒有明確的分隔符號，所以首先要用分詞系統將文檔自動切分成單詞序列，這樣每個文檔就轉換為由單詞序列構成的數據流。

為了系統後續處理方便，需要對每個不同的單詞賦予唯一的單詞編號，同時記錄下哪些文檔包含這個單詞，在處理結束後，我們可以得到最簡單的倒排索引（參考圖4）。

圖4中，「單詞ID」一列記錄了每個單詞對應的編號，第2列是對應的單詞，第3列即每個單詞對應的倒排列表。比如：單詞「谷歌」，其中單詞編號為1，倒排列表為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞。

之所以說圖4的倒排索引是最簡單的，是因為這個索引系統只記載了哪些文檔包含某個單詞。而事實上，索引系統還可以記錄除此之外的更多信息。

圖5是一個相對復雜些的倒排索引，與圖4所示的基本索引系統相比，在單詞對應的倒排列表中不僅記錄了文檔編號，還記載了單詞頻率信息，即這個單詞在某個文檔中出現的次數。之所以要記錄這個信息，是因為詞頻信息在搜索結果排序時，計算查詢和文檔相似度是一個很重要的計算因子，所以將其記錄在倒排列表中，以方便後續排序時進行分值計算。

在圖5所示的例子里，單詞「創始人」的單詞編號為7，對應的倒排列表內容有（3;1），其中3代表文檔編號為3的文檔包含這個單詞，數字1代表詞頻信息，即這個單詞在3號文檔中只出現過1次，其他單詞對應的倒排列表所代表的含義與此相同。

實用的倒排索引還可以記載更多的信息，圖6所示的索引系統除了記錄文檔編號和單詞詞頻信息外，額外記載了兩類信息——即每個單詞對應的文檔頻率信息（圖6的第3列）及單詞在某個文檔出現位置的信息。

文檔頻率信息代表了在文檔集合中有多少個文檔包含某個單詞，之所以要記錄這個信息，其原因與單詞頻率信息一樣，這個信息在搜索結果排序計算中是一個非常重要的因子。

而單詞在某個文檔中出現位置的信息並非索引系統一定要記錄的，在實際的索引系統里可以包含，也可以選擇不包含這個信息，之所以如此，是因為這個信息對於搜索系統來說並非必要，位置信息只有在支持短語查詢的時候才能夠派上用場。

以單詞「拉斯」為例：其單詞編號為8，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排列表為{(3;1;<4>),(5;1;<4>)}，其含義為在文檔3和文檔5出現過這個單詞，單詞頻率都為1，單詞「拉斯」在這兩個文檔中的出現位置都是4，即文檔中第4個單詞是「拉斯」。

圖6所示的倒排索引已經是一個非常完備的索引系統，實際搜索引擎的索引結構基本如此，區別無非是採取哪些具體的數據結構來實現上述邏輯結構。

有了這個索引系統，搜索引擎可以很方便地響應用戶的查詢。比如：用戶輸入查詢詞 「Facebook」，搜索系統查找倒排索引，從中可用讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結果。

而利用單詞詞頻信息、文檔頻率信息即可對這些候選搜索結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統的部分內部流程。

單詞詞典是倒排索引中非常重要的組成部分，它用來維護文檔集合中出現過的 所有單詞 的相關信息，同時用來記載某個 單詞對應的倒排列表在倒排文件中的位置信息 。在支持搜索時，根據用戶的查詢詞，去單詞詞典里查詢，就能夠獲得相應的倒排列表，並以此作為後續排序的基礎。
對於一個規模很大的文檔集合來說，可能包含幾十萬甚至上百萬的不同單詞，能否快速定位某個單詞，這直接影響搜索時的響應速度，所以需要高效的數據結構來對單詞詞典進行構建和查找， 常用的數據結構包括 哈希加鏈表 結構和 樹形 詞典結構。

B樹（或者B+樹）是另外一種高效查找結構，圖8是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字元序），而哈希方式則無須數據滿足此項要求。

B樹形成了層級查找結構，中間節點用於指出一定順序范圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的地址信息，根據這個地址就可以提取出單詞字元串。

具體的大家可以看看[ https://blog.csdn.net/hackerose1994/article/details/50933396?locationNum=11&fps=1 )

③ 正排索引和倒排索引

倒排索引 （英語：Inverted index），也常被稱為 反向索引 、 置入檔案 或 反向檔案 ，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。

有兩種不同的反向索引形式：

一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
後者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建。

所謂的正排索引是從索引文檔到關鍵詞到內容，倒排索引則是相反從關鍵詞到詞頻，位置，目錄等信息，現在通常用於搜索的。由於互聯網上的數據量無限大，不可能存儲足夠多的文檔，所以正排索引用處不大。

有兩種不同的反向索引形式：

​我們就能得到下面的反向文件索引：

對相同的文字，我們得到後面這些完全反向索引，有文檔數量和當前查詢的單詞結果組成的的成對數據。 同樣，文檔數量和當前查詢的單詞結果都從零開始。所以， "banana": {(2, 3)} 就是說 "banana"在第三個文檔里 ( {displaystyle T_{2}} T_{2})，而且在第三個文檔的位置是第四個單詞(地址為 3)。

如果我們執行短語搜索"what is it" 我們得到這個短語的全部單詞各自的結果所在文檔為文檔0和文檔1。但是這個短語檢索的連續的條件僅僅在文檔1得到。

反向索引數據結構是典型的搜索引擎檢索演算法重要的部分。
一個搜索引擎執行的目標就是優化查詢的速度：找到某個單詞在文檔中出現的地方。以前，正向索引開發出來用來存儲每個文檔的單詞的列表，接著掉頭來開發了一種反向索引。 正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證這樣的查詢。
實際上，時間、內存、處理器等等資源的限制，技術上正向索引是不能實現的。
為了替代正向索引的每個文檔的單詞列表，能列出每個查詢的單詞所有所在文檔的列表的反向索引數據結構開發了出來。
隨著反向索引的創建，如今的查詢能通過立即的單詞標示迅速獲取結果（經過隨機存儲）。隨機存儲也通常被認為快於順序存儲。

索引的構建[4] 相當於從正排表到倒排表的建立過程。當我們分析完網頁時 ,得到的是以網頁為主碼的索引表。當索引建立完成後 ,應得到倒排表 ,具體流程如圖所示：
流程描述如下：
1）將文檔分析稱單詞term標記，
2）使用hash去重單詞term
3）對單詞生成倒排列表
倒排列表就是文檔編號DocID，沒有包含其他的信息（如詞頻，單詞位置等），這就是簡單的索引。
這個簡單索引功能可以用於小數據，例如索引幾千個文檔。然而它有兩點限制：
1）需要有足夠的內存來存儲倒排表，對於搜索引擎來說， 都是G級別數據，特別是當規模不斷擴大時 ,我們根本不可能提供這么多的內存。
2）演算法是順序執行，不便於並行處理。

歸並法[4] ,即每次將內存中數據寫入磁碟時，包括詞典在內的所有中間結果信息都被寫入磁碟，這樣內存所有內容都可以被清空，後續建立索引可以使用全部的定額內存。
歸並索引
歸並索引
如圖 歸並示意圖：
合並流程：
1）頁面分析，生成臨時倒排數據索引A，B，當臨時倒排數據索引A，B占滿內存後，將內存索引A，B寫入臨時文件生成臨時倒排文件，
2) 對生成的多個臨時倒排文件 ,執行多路歸並 ,輸出得到最終的倒排文件 ( inverted file)。
合並流程
合並流程
索引創建過程中的頁面分析 ,特別是中文分詞為主要時間開銷。演算法的第二步相對很快。這樣創建演算法的優化集中在中文分詞效率上。

④ ES 索引解析(倒排索引 | 正排索引)

何為倒排索引？首先要了解索引表：由關鍵詞為key，關鍵詞位置屬性為value組成的一張表。由於該表不是由key來確定value值，而是由value的屬性值來確定key的位置，所以稱為倒排索引，帶有倒排索引的文件稱為倒排文件。通俗的講倒排索引就好比書的目錄，通過目錄咱們可以准確的找到相應的數據。下面對lucene倒排索引的結構與演算法進行介紹。

對於獲取關鍵詞有兩種思路，1.根據空格分隔獲取所有的字元2.過濾文檔中沒有意義的詞，獲取其中的關鍵詞。除此以上還會對詞的時態，大小寫，同義詞，標點符號等做相應的處理，不同的分詞器對文檔索引的時候做的操作有所差異。
實例1：Tom lives in Zhangye,I live in Zhangye too.
關鍵詞1：[tom][live][in][zhangye][i][live][zhangye]
實例2：He once lived in Shanghai
關鍵詞2：[he][live][shanghai]

根據關鍵詞我們就可以確定關鍵詞所在的文章號，關鍵詞在文章中出現的頻次以及該關鍵詞在文章中出現的位置（根據上面獲取關鍵詞我們可以知道，索引的時候要麼索引所有字元，要麼索引關鍵詞，lucene採取的就是索引關鍵詞的方式，這樣會節省大量的空間），具體索引如下表：

1）詞典文件：每個關鍵詞以及指向頻率文件和位置文件的指針和filed（用於表達信息位置，每個關鍵詞都有一個或多個field）信息
2）頻率文件：關鍵詞在每個文件中出現頻率的文件
3）位置文件：關鍵詞所在文章中的位置文件

關鍵詞壓縮為<前綴長度，後綴>,例如：「我愛你中國」=》<3,中國>，另外對數字的壓縮，只記錄與上一個數字的差值，比如當前文章號是11890，上一個文章號是11870，壓縮後只需要報錯20，這樣就極大的縮小了存儲空間。

倒排索引服務於es查詢操作，對數據的聚合，排序則需要使用正排索引，下面我們介紹正排索引。

正排索引說白了就是document每個field的值的排序，其實就是doc values，舉例說明：
實例：
doc1: { "name": "張三", "age": 27,"sex":"男" }
doc2: { "name": "李四", "age": 30,"sex":「女」 }
正排索引：
document name age sex
doc1 jack 27 男
doc2 tom 30 女
正排索引使用場景是排序，聚合，過濾等
注意：
對於分詞的field進行聚合（aggregation）操作，需要將fielddata設置為true，否則會報錯提示你打開fielddata、將正排索引載入到內存中
doc values是被保存在磁碟上的，此時如果內存足夠，os會自動將其緩存在內存中，性能還是會很高；如果內存不足夠，os會將其寫入磁碟上。

到此對倒排索引與正排索引就介紹完畢了，如有幫助，請關注！謝謝！

⑤ python倒排索引（Inverted index）

s=raw_input()
lines=s.split('
')
dictlines=lines[:100]
mydict={}
#read
fori,lineinenumerate(dictlines):
forwordinline.split():
mydict.setdefault(word,[]).append(i+1)
#printindices
forwordinmydict.keys():
print"%s:%s"%(word,",".join(map(str,sorted(mydict[word]))))

defandSearch(words_list):
globalmydict
a=set(range(1,101))
forwordinwords_list:
a=a.intersection(set(mydict[word]))
returna

deforSearch(words_list):
globalmydict
a=set([])
forwordinwords_list:
a=a.union(set(mydict[word]))
returna

#Query
index=100
u=lines[index]
whileindex<len(lines):
words_list=u.split()
if":"inu:
ifwords_list[0]=="OR:":
a=orSearch(words_list)
else:
ifwords_list[0]=='AND:':
words_list=words_list[1:]
a=andSearch(words_list)
ifnota:
print",".join(map(str,list(a)))
else:
print"None"
index+=1

大致思想就是這樣。。。。。。。。