Inverted File 簡介

搜尋引擎在搜尋的時候，如果單純用字串比對就太遜了，效率太差
一定要用索引(indexing)的技術，顧名思義，索引就像是去圖書館借書一樣，
從館藏目錄中，依據字母順序找到想要的書，書名旁邊標示著書本放在哪個櫃子

這邊介紹一個經典的索引技術 - Inverted File
Inverted File 是一種資料結構，記錄著每個字所在的位置，以下舉一個教科書經典例子

假設

S1 = "Have you ever seen tropical fish?"
S2 = "Do you like fish?"
S3 = "My uncle raise tropical fish."
S4 = "My cat ate fish and tropical fruits."



存成 Inverted File 資料結構為：
"單字" : { (單字在哪份文件，單字在該文件的位置) }


"and"     : {(4,5)}
"ate"     : {(4,3)}
"cat"     : {(4,2)}
"do"      : {(2,1)}
"ever"    : {(1,3)}
"fish"    : {(1,6), (2,4), (3,5), (4,4)}
"fruits"  : {(4,7)}
"have"    : {(1,1)}
"like"    : {(2,3)}
"my"      : {(3,1), (4,1)}
"raise"   : {(3,3)}
"seen"    : {(1,4)}
"tropical": {(1,5), (3,4), (4,6)}
"uncle"   : {(3,2)}
"you"     : {(1,2), (2,2)}


假設我們今天要搜尋 "raise tropical fish"
利用Inverted File一個一個字去查，對單字在哪份文件取交集
{(3,3)} ∩ {(1,5), (3,4), (4,6)} ∩  {(1,6), (2,4), (3,5), (4,4)}  =  {(3,3~5)}
我們可以得知 "raise tropical fish" 這句話在S3的第3~5個字