跳到主要內容

倒排索引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。

倒排索引的時間線與現況

  1. 電腦出現以前 書末索引與聖經詞語索引等,由詞找出處的做法早就存在,倒排索引是把它用在電腦檢索上。
  2. 1998 年 Brin 與 Page 發表《The Anatomy of a Large-Scale Hypertextual Web Search Engine》,描述 Google 原型怎麼把網頁切詞,寫入順向索引,再由排序程式產生倒排索引。
  3. 現況 Lucene、Elasticsearch、OpenSearch 都以倒排索引為核心。向量搜尋興起後,系統會另外建向量索引,但字面比對與篩選仍靠倒排索引。

結構與查詢方式:倒排索引由兩部分組成,一是排序過的詞典,列出所有出現過的詞;二是每個詞對應的文件清單,稱為倒排列表。清單裡通常記文件編號,也可以多記詞頻與位置。查詢時先在詞典找到詞,取出清單,AND 查詢取清單的交集,OR 查詢取聯集,片語查詢則要再用位置確認詞是否相鄰。多存位置會讓索引變大,但能支援片語;先取候選再比對,比逐篇掃描全文快得多。

為什麼重要

理解倒排索引,就能理解為什麼切詞會影響能不能被搜到:索引裡只有被切出來的詞。型號被拆壞、中文斷詞不當,使用者搜尋的詞就對不上索引裡的詞。Google 在說明裡也把搜尋索引比喻成書末的索引,每個被收錄的頁面裡出現過的詞都有一個條目,內容沒被收錄,就沒有條目可以被查到。

怎麼檢查

  1. 在 Search Console 用「網址審查」,確認頁面顯示「已編入索引」。
  2. 用「測試線上網址」看呈現後的 HTML,確認重要文字沒有只靠 JavaScript 才出現。
  3. 在 Google 搜尋用雙引號搜尋頁面裡的一句獨特文字,確認這段內容有被收錄。
  4. 若自己架 Elasticsearch 站內搜尋,用 _analyze 測試切詞結果,確認型號、品牌名沒有被拆壞。

常見誤解

  • 頁面被收錄,頁面裡的每個詞都找得到。

    能不能找到,取決於切詞方式。被拆壞的型號或縮寫,查詢時可能對不上。

  • 倒排索引決定了排名。

    它只負責快速找出含有查詢詞的候選文件,排序是後面的評分與排名系統的工作。

  • 倒排索引只存詞。

    進階的倒排索引也會存詞頻與位置,這是片語查詢和相關性評分需要的資料。

常見問題

搜尋「無糖茶」這個片語,需要保存什麼?

要保存每個詞在文件裡的位置。只存「詞出現在哪些文件」,只能知道文件同時有「無糖」和「茶」,不能確認它們是不是相鄰,有了位置資料才能判斷是不是連在一起的片語。

改了切詞規則後,需要重建索引嗎?

需要。索引裡存的詞,是依舊規則切出來的,規則改了,已存的資料不會自動更新,要重新處理文件,查詢和索引的切詞方式才會一致。

倒排索引和正排索引差在哪?

方向相反。正排索引是由文件指向它包含的詞,倒排索引是由詞指向包含它的文件。搜尋時要從查詢字詞找文件,所以多數搜尋系統會建倒排索引,查詢時不必逐篇掃描全部文件。

Google 的索引就是倒排索引嗎?

Google 沒有公開索引的內部結構,所以不能直接說是。官方只說明索引是儲存已收錄頁面資訊的大型資料庫。倒排索引是搜尋系統最常見的做法,用它理解檢索原理沒問題。

AK · AKSEO Labs · 上線