倒排索引Inverted Index
倒排索引是搜尋引擎常用的資料結構,記錄每個詞出現在哪些文件,讓系統能由查詢詞直接找到含有該詞的文件。
- 英文
- Inverted Index
- 台灣常見別名
- 倒排索引、反向索引、反向文件索引
- 簡中用語
- 倒排索引、反向索引
- 類別
- 搜尋引擎運作與資訊檢索
- 提出者與年份
- 資訊檢索通用資料結構,首次提出者未查到
- 官方文件
- Elastic:What is an inverted index?;Brin 與 Page:The Anatomy of a Large-Scale Hypertextual Web Search Engine
倒排索引是什麼?
書末的「索引」頁列著「關鍵字,出現在第幾頁」,倒排索引的概念一樣。一般的文件記錄是「文件,裡面有哪些詞」,倒排索引把它倒過來,變成「詞,出現在哪些文件」,所以叫「倒排」(Inverted)。
它屬於搜尋流程的索引階段:爬蟲抓回頁面後,搜尋引擎把內容切成詞,寫進倒排索引。查詢時,系統不用把幾十億頁逐一讀過,只要查每個詞的名單,再合併名單。
舉例(假想情境)
三篇文章:文件 1 是「咖啡 豆 烘焙」,文件 2 是「咖啡 沖煮 器具」,文件 3 是「烘焙 溫度 曲線」。倒排索引記下:咖啡在文件 1、2,烘焙在文件 1、3,沖煮在文件 2。查詢「咖啡 烘焙」時,取兩份名單的交集,結果是文件 1。
倒排索引的時間線與現況
- 電腦出現以前 書末索引與聖經詞語索引等,由詞找出處的做法早就存在,倒排索引是把它用在電腦檢索上。
- 1998 年 Brin 與 Page 發表《The Anatomy of a Large-Scale Hypertextual Web Search Engine》,描述 Google 原型怎麼把網頁切詞,寫入順向索引,再由排序程式產生倒排索引。
- 現況 Lucene、Elasticsearch、OpenSearch 都以倒排索引為核心。向量搜尋興起後,系統會另外建向量索引,但字面比對與篩選仍靠倒排索引。
結構與查詢方式:倒排索引由兩部分組成,一是排序過的詞典,列出所有出現過的詞;二是每個詞對應的文件清單,稱為倒排列表。清單裡通常記文件編號,也可以多記詞頻與位置。查詢時先在詞典找到詞,取出清單,AND 查詢取清單的交集,OR 查詢取聯集,片語查詢則要再用位置確認詞是否相鄰。多存位置會讓索引變大,但能支援片語;先取候選再比對,比逐篇掃描全文快得多。
為什麼重要
理解倒排索引,就能理解為什麼切詞會影響能不能被搜到:索引裡只有被切出來的詞。型號被拆壞、中文斷詞不當,使用者搜尋的詞就對不上索引裡的詞。Google 在說明裡也把搜尋索引比喻成書末的索引,每個被收錄的頁面裡出現過的詞都有一個條目,內容沒被收錄,就沒有條目可以被查到。
怎麼檢查
- 在 Search Console 用「網址審查」,確認頁面顯示「已編入索引」。
- 用「測試線上網址」看呈現後的 HTML,確認重要文字沒有只靠 JavaScript 才出現。
- 在 Google 搜尋用雙引號搜尋頁面裡的一句獨特文字,確認這段內容有被收錄。
- 若自己架 Elasticsearch 站內搜尋,用
_analyze測試切詞結果,確認型號、品牌名沒有被拆壞。
常見誤解
頁面被收錄,頁面裡的每個詞都找得到。
能不能找到,取決於切詞方式。被拆壞的型號或縮寫,查詢時可能對不上。
倒排索引決定了排名。
它只負責快速找出含有查詢詞的候選文件,排序是後面的評分與排名系統的工作。
倒排索引只存詞。
進階的倒排索引也會存詞頻與位置,這是片語查詢和相關性評分需要的資料。
常見問題
搜尋「無糖茶」這個片語,需要保存什麼?
要保存每個詞在文件裡的位置。只存「詞出現在哪些文件」,只能知道文件同時有「無糖」和「茶」,不能確認它們是不是相鄰,有了位置資料才能判斷是不是連在一起的片語。
改了切詞規則後,需要重建索引嗎?
需要。索引裡存的詞,是依舊規則切出來的,規則改了,已存的資料不會自動更新,要重新處理文件,查詢和索引的切詞方式才會一致。
倒排索引和正排索引差在哪?
方向相反。正排索引是由文件指向它包含的詞,倒排索引是由詞指向包含它的文件。搜尋時要從查詢字詞找文件,所以多數搜尋系統會建倒排索引,查詢時不必逐篇掃描全部文件。
Google 的索引就是倒排索引嗎?
Google 沒有公開索引的內部結構,所以不能直接說是。官方只說明索引是儲存已收錄頁面資訊的大型資料庫。倒排索引是搜尋系統最常見的做法,用它理解檢索原理沒問題。