iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 8
2

在Day 6的文章中,我們說到在進行搜尋時,我們首要關心的是查詢的詞與文件間的相似度。我用一個例子作為開端:假如我們有三個檔案,分別叫做doc1, doc2以及doc3,而檔案由以下的文字組成。

https://ithelp.ithome.com.tw/upload/images/20190909/2011868370xJueVPjA.png

為了獲取相似度,我們需要知道每一個文件裡面有哪些字,才能比較查詢與文件之間相似不相似。我們可能想知道這個文件裡面有或沒有這個字(二元,0或1),也可能想知道這個文件裡面出現該字的頻率(詞頻,0或多)。假如我們想知道詞頻,那我們就可以畫出此矩陣:

https://ithelp.ithome.com.tw/upload/images/20190909/20118683YmL8JSN0FF.png

這個矩陣就稱為文件矩陣(Document Term Matrix, DTM)。在空間中,矩陣看起來像這樣:

https://ithelp.ithome.com.tw/upload/images/20190909/20118683ankHxCWimN.png

每個詞會成為一個維度,因為正常人在面對三維以上個空間頭腦會爆掉 (可以試試看這個XD),所以我只用三個詞來做出一個三維空間。接著,若要求出文件與查詢的相似度,我們會使用Cosine Similartiy

現在要來說說DTM的缺點:DTM一個最主要的缺點就是在矩陣中會有很多0,造成多餘的空間消耗。多餘個空間消耗會產生很多問題,除了搜尋效率的本身,多餘的空間消耗也會使原本能存更多索引在記憶體中的部分,不得不存到硬碟當中,其中資料IO的速度會拖累搜尋的速度。因此,DTM被改造成倒排索引(Inverted Index)。

https://ithelp.ithome.com.tw/upload/images/20190909/201186837ShHuWbo8H.png

以上是兩個矩陣都是倒排索引的不同表示法。左邊將文件編號與詞頻作為一組擺在一起,右邊則將編號寫在一起,後面再接著各個文件中該詞的詞頻。

明天的文章中,我們將實作倒排索引 -- Inverted Index。


上一篇
Day 7: 親手寫個檢索系統吧(ㄧ)文件預處理
下一篇
Day 9: 親手寫個檢索系統吧(二)倒排索引
系列文
深入淺出搜尋引擎和自然語言處理30

尚未有邦友留言

立即登入留言