什么是倒排索引

倒排索引（Inverted index），個(gè)人理解倒排的意思是說，普通的搜索算法，是從文檔里搜索一個(gè)關(guān)鍵詞（文檔→關(guān)鍵詞），而倒排索引是首先知道了每個(gè)關(guān)鍵詞都出現(xiàn)在了哪些文檔里，從關(guān)鍵詞搜文檔（關(guān)鍵詞→文檔），正好目的反過來，和“顛倒搜索”沒什么關(guān)系。

倒排索引的好處

想象一個(gè)場景，你要對一個(gè)很大的文件搜索其中是否有一個(gè)關(guān)鍵詞，常規(guī)的做法是遍歷整個(gè)文檔，那么如果關(guān)鍵詞在文檔最后，就會非常慢

倒排索引先記錄了每個(gè)關(guān)鍵詞出現(xiàn)在了哪些文檔里，需要哪個(gè)關(guān)鍵詞，把含有的文檔直接拎出來就可以，這樣就快多了

主流的搜索工具，ElasticSearch都是基于倒排索引的方式

如何建立一個(gè)倒排索引

舉個(gè)栗子，假設(shè)我們有如下0-4五個(gè)文檔

分詞后可以得到這16個(gè)關(guān)鍵詞，倒排列表中記錄的是那些文檔包含這個(gè)關(guān)鍵詞

實(shí)際使用的一些問題

自己實(shí)現(xiàn)一個(gè)倒排，個(gè)人感覺需要注意一下模糊搜索的問題和匹配算法的設(shè)計(jì)，在使用ES時(shí)，雖然這些已經(jīng)做好了，但是感覺有時(shí)效果不佳，具體實(shí)現(xiàn)機(jī)制還需要再研究。

模糊匹配

我們應(yīng)該希望系統(tǒng)具有這樣的能力

• 匹配縮寫：搜索 UK ，會返回包含 United Kindom 的文檔
• 匹配詞根：搜索 jump ，會匹配 jumped ， jumps
• 匹配同義詞：搜索 johnny walker 會匹配 Johnnie Walker ， 搜索 people ，會返回包含 person 的文檔
• 理解語境：搜索fox news hunting 應(yīng)該返回福克斯新聞（ Foxs News ）中關(guān)于狩獵的故事，而搜素so fox hunting news 應(yīng)該返回關(guān)于獵狐的故事

要使得系統(tǒng)能夠坐到這一點(diǎn)，就需要在分詞階段，對詞條進(jìn)行規(guī)范，真實(shí)場景下，很多時(shí)候并不能實(shí)現(xiàn)兩個(gè)token之間的完美匹配，這時(shí)基于token的匹配就失去的作用

自己在使用ES的過程中，普通的匹配無法做到對單復(fù)數(shù)這種簡單情況的處理，或許在建立索引是有一些操作，還需要繼續(xù)研究

匹配算法設(shè)計(jì)

如何設(shè)計(jì)一個(gè)合理的匹配算法也是值得研究的問題，如何給搜索結(jié)果打分。

例如一個(gè)文檔，我們用大寫字母表示詞條，大寫字母組成的字符串表示一個(gè)文檔，對于一個(gè)關(guān)鍵詞CDEF，匹配算法應(yīng)該能夠?qū)τ谶@幾種情況給出不同的分?jǐn)?shù)

匹配到不同數(shù)量的詞條的得分應(yīng)該是不一樣的
比如有的匹配到CDF三個(gè)，有的只匹配到CD兩個(gè)，通常是匹配更多數(shù)量的分?jǐn)?shù)應(yīng)該更高

匹配到相同數(shù)量的詞條得分應(yīng)該是不一樣的
比如都是匹配到三個(gè)詞條，一個(gè)是CDE，一個(gè)是DEF，如果C是一個(gè)類似頻繁項(xiàng)的詞條，F是一個(gè)對文檔比較重要的詞條，那么后者的的風(fēng)應(yīng)該更高

匹配到相同的詞條列表的得分應(yīng)該是不一樣的
比如都是匹配到CDE三個(gè)詞條，有的是連續(xù)出現(xiàn)的（ABCDEFG），有的是分開出現(xiàn)（ABCGDFE）或者順序不同(ABCEDFG)，他們的得分應(yīng)該是不同的。
另外從搜索的意圖上看

如果搜索的關(guān)鍵詞是一個(gè)專有名詞
一些專有名詞本質(zhì)上就是不可分割的(New York不能看成New和York)
一些專有名詞去掉其中一些token或改變順序也并不影響詞義（University of Pittsburgh和Pittsburgh university）。

2. 如果搜索僅僅是幾個(gè)關(guān)鍵詞的組合，比如平時(shí)使用搜索引擎的場景，那么每個(gè)token都是獨(dú)立的可以以任意順序在文檔中出現(xiàn)。

參考資料

https://www.zhihu.com/question/23202010

總結(jié)

以上是生活随笔為你收集整理的倒排索引原理_搜索引擎都在用的倒排索引——原理与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。