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個字

Information Retrieval

最近比賽要用到的query expansion，是Information Retrieval領域的一部分
以下為參考資料

陳信希教授開的 Information Retrieval and Extraction 

只有2009年這課程的投影片沒設密碼，所以這邊貼出09年的課程網站

不過還是可以根據底下列的推薦用書去查query expansion部分
連結：http://nlg.csie.ntu.edu.tw/courses/IR/IR2009.html

Introduction to Information Retrieval 

2008出版的IR參考書，官網上有電子書和投影片，我們要的query expansion在第九章
連結：http://nlp.stanford.edu/IR-book/

Modern Information Retrieval

整個第五章在講query expansion，礙於版權問題，就不放連結
去GOOGLE一下就有電子書了
http://www.cs.utexas.edu/~mooney/ir-course/
這連結是本書的相關課程的投影片