進擊的搜尋引擎原理淺談


By – 楊明翰

一、搜尋引擎的基本結構

一個搜尋引擎(Search Engine)大致上可以拆解成幾個部分,第一個是爬蟲(Crawler),功能是在網際網路中以隨機遊走的方式對大量網頁做存取,並將網頁內容下載來。第二個是檢索模組(Indexer),功能是把爬蟲爬回來的內容經過分析之後產生索引文件(Index),第三部分是查詢引擎(Query Engine),功能分析查詢的Query並藉由索引文件比對符合條件的內容,並展示給使用者。通常為了方便操作,會再封裝一層介面。

根據以上的描述,我們可以把這樣的結構用底下的圖來表示:

001S.png

二、索引的數據結構

SQL類的資料庫採用的索引結構因為不考慮詞彙,所以是以B+ Tree做為索引的結構,單位是字元。而搜尋引擎考量的單位是詞彙,所以是採用字典+反向索引(Inverted index)的結構。所謂的反向索引就是以Key為詞彙,Value為文檔編號的數據結構。通常長的像底下這個:002S

三、搜尋引擎的效益評估

003S.png

對使用者而言,搜尋引擎是否能提供他們所需要的關鍵資訊是搜尋引擎的效益衡量的關鍵指標。通常使用者第一優先的考量是準確度,所以一個搜尋引擎是否能準確的找到使用者想找的資源,是搜尋引擎追求的關鍵效益之一。

 

四、個人化搜尋結果

如果有稍微注意一下平常的和搜尋引擎互動的過程,你會發現每個人在Google Search上搜尋一樣的關鍵字,會得到不同的排序結果,這是由於Google Search導入客製化的搜尋結果。(因為每個人所在意的事情面向不同)。

像是我拿Epic創業筆記做實驗,在有登錄和沒登錄的情況之下:第四筆和第五筆搜尋結果很顯然的不一樣。

004S.png
這是我在登錄Google的情況下搜尋"Epic創業筆記"

 

005S.png
沒登錄的情況下搜尋"Epic創業筆記"

具體實現個人化搜尋的技術,可以從文檔的排序去思考。對一個搜尋結果而言,最簡單的排序手法就是用詞頻去排序,也就是某詞彙出現越多次,排在越前面,這時候就會考量到詞權重的問題,最常見的公式是TF-IDF以及BM25兩種。而個人化的排序則是透過搜尋紀錄,去優化權重的部分。目前機器學習的風氣相當熱,我相信Google應該有利用機器學習排序來幫助Google Search 做客製化。

 

五、常見的詞權重方法

  • TF-IDF
  • BM25(Okapi)
  • Mod-Okapi
  • LM(Dirichlet Prior Method)
  • DFR(Divergence From Randomness)
  • F2EXP
  • DFI(Divergence From Independence)
  • MIRDF
  • TW-IDF
  • TI-IDF
 補充

有朋友提醒我現在的搜尋引擎會把Indexer的斷詞元件拆出去變成Tokenizer藉此提高索引效率

本文章發表於:科技

加入43

鼓勵作者

目前持有 Blink Coin: Loading..

選擇禮物


愛心

(Coin 10)

幫高調

(Coin 20)

咖啡

(Coin 30)

掌聲鼓勵

(Coin 40)

崇拜眼神

(Coin 50)

驚呆了

(Coin 60)

神人4ni

(Coin 70)

花束

(Coin 100)

鑽石

(Coin 300)

紅寶石

(Coin 500)

藍寶石

(Coin 1000)

黃寶石

(Coin 3000)


送出鼓勵



發表匿名文章不會出現你的大頭圖與名稱,你可暢所欲言,但文章內容務必遵守「佈告欄使用規範」!


回應

送出回應


想回應這篇文章嗎?也想發表文章嗎?
馬上登入來發表文章、追蹤作者、收藏文章或回應文章吧!

註冊 登入