與技術(shù)有關(guān):關(guān)于搜索引擎索引的這些概念

4 評(píng)論 5904 瀏覽 45 收藏 12 分鐘

搜索引擎在我們的日常生活中很常見(jiàn),在各個(gè)領(lǐng)域都發(fā)揮著它獨(dú)特的作用。那今天我們一起從文中來(lái)了解一下關(guān)于搜索引擎索引的這些概念。

索引其實(shí)在日常生活中是很常見(jiàn)的,比如:書(shū)籍的目錄就是一種索引結(jié)構(gòu),目的是為了讓人們能夠更快地找到相關(guān)章節(jié)內(nèi)容。再比如:像hao123這種類型的導(dǎo)航網(wǎng)站,本質(zhì)上也是互聯(lián)網(wǎng)頁(yè)面中的索引結(jié)構(gòu),目的類似,也是為了讓用戶能夠盡快找到有價(jià)值的分類網(wǎng)站。

在計(jì)算機(jī)科學(xué)領(lǐng)域,索引也是非常常用的數(shù)據(jù)結(jié)構(gòu),其根本目的是為了——在具體應(yīng)用中加快查找速度。比如:在數(shù)據(jù)庫(kù)中,在很多高效數(shù)據(jù)結(jié)構(gòu)中,都會(huì)大量采用索引來(lái)提升系統(tǒng)效率。

具體到搜索引擎,索引更是其中最重要的核心技術(shù)之一,面對(duì)海量的網(wǎng)頁(yè)內(nèi)容,如何快速找到包含用戶查詢?cè)~的所有網(wǎng)頁(yè)?倒排索引在其中扮演了關(guān)鍵的角色。

本文主要講解與倒排索引相關(guān)的技術(shù),通過(guò)引入簡(jiǎn)單實(shí)例,介紹與搜索引擎有關(guān)的一些基本概念,了解這些基本概念對(duì)于以后深入了解索引的工作機(jī)制非常重要。

一、單詞-文檔矩陣

單詞-文檔矩陣是表達(dá)兩者之間所具有的一種包含關(guān)系的概念模型,圖1展示了其含義,圖1中的每列代表一個(gè)文檔,每行代表一個(gè)單詞,打?qū)吹奈恢么戆P(guān)系。

圖1:?jiǎn)卧~-文檔矩陣

  • 從縱向即文檔這個(gè)維度來(lái)看:每列代表文檔包含了哪些單詞,比如:文檔1包含了詞匯1和詞匯4,而不包含其他單詞。
  • 從橫向即單詞這個(gè)維度來(lái)看:每行代表了哪些文檔包含了某個(gè)單詞,比如:對(duì)于詞匯1來(lái)說(shuō),文檔1和文檔4中出現(xiàn)過(guò)詞匯1,而其他文檔不包含詞匯1,矩陣中其他的行列也可做此種解讀。

搜索引擎的索引其實(shí)就是實(shí)現(xiàn)單詞-文檔矩陣的具體數(shù)據(jù)結(jié)構(gòu),可以有不同的方式來(lái)實(shí)現(xiàn)上述概念模型。比如:倒排索引、簽名文件、后綴樹(shù)等方式。

但是各項(xiàng)試驗(yàn)數(shù)據(jù)表明,倒排索引是單詞到文檔映射關(guān)系的最佳實(shí)現(xiàn)方式,所以本文主要介紹倒排索引的技術(shù)細(xì)節(jié)。

二、倒排索引基本概念

在這里向大家解釋倒排索引常用的一些專用術(shù)語(yǔ):

  • 文檔:一般搜索引擎的處理對(duì)象是互聯(lián)網(wǎng)網(wǎng)頁(yè),而文檔這個(gè)概念要更寬泛些,代表以文本形式存在的存儲(chǔ)對(duì)象。相比網(wǎng)頁(yè)來(lái)說(shuō),涵蓋更多形式。比如:Word、PDF、XML等不同格式的文件都可以稱為文檔;再比如:一封郵件、一條短信、一條微博也可以稱為文檔。
  • 文檔集合:由若干文檔構(gòu)成的集合稱為文檔集合。比如:海量的互聯(lián)網(wǎng)網(wǎng)頁(yè)或者說(shuō)大量的電子郵件,都是文檔集合的具體例子。
  • 文檔編號(hào):在搜索引擎內(nèi)部,會(huì)為文檔集合內(nèi)每個(gè)文檔賦予一個(gè)唯一的內(nèi)部編號(hào),以此編號(hào)來(lái)作為這個(gè)文檔的唯一標(biāo)識(shí),這樣方便內(nèi)部處理,每個(gè)文檔的內(nèi)部編號(hào)即稱為文檔編號(hào)。
  • 單詞編號(hào):與文檔編號(hào)類似,搜索引擎內(nèi)部以唯一的編號(hào)來(lái)表征某個(gè)單詞,單詞編號(hào)可以作為某個(gè)單詞的唯一表征。
  • 倒排索引:倒排索引是實(shí)現(xiàn)單詞-文檔矩陣的一種具體存儲(chǔ)形式。通過(guò)倒排索引,可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表,倒排索引主要由兩個(gè)部分組成:?jiǎn)卧~詞典和倒排文件。
  • 單詞詞典:搜索引擎通常的索引單位是單詞,單詞詞典是由文檔集合中出現(xiàn)過(guò)的所有單詞構(gòu)成的字符串集合,單詞詞典內(nèi)每條索引項(xiàng)記載單詞本身的一些信息及指向倒排列表的指針。
  • 倒排列表:倒排列表記載了,出現(xiàn)某個(gè)單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息,每條記錄稱為一個(gè)倒排項(xiàng)。根據(jù)倒排列表,即可獲知哪些文檔包含某個(gè)單詞。
  • 倒排文件:所有單詞的倒排列表往往順序地存儲(chǔ)在磁盤的某個(gè)文件里,這個(gè)文件即被稱為倒排文件,倒排文件是存儲(chǔ)倒排索引的物理文件。

關(guān)于這些概念之間的關(guān)系,通過(guò)圖2可以比較清晰地看出來(lái):

圖2:倒排索引基本概念示意圖

三、倒排索引簡(jiǎn)單實(shí)例

倒排索引從邏輯結(jié)構(gòu)和基本思路上講非常簡(jiǎn)單,下面我們通過(guò)具體實(shí)例來(lái)進(jìn)行說(shuō)明,使得大家能夠?qū)Φ古潘饕幸粋€(gè)宏觀而直接的感受。

假設(shè)文檔集合包含5個(gè)文檔,每個(gè)文檔包含內(nèi)容如下圖所示:在圖3中最左端一欄是每個(gè)文檔對(duì)應(yīng)的文檔編號(hào),我們的任務(wù)就是對(duì)這個(gè)文檔集合建立倒排索引。

圖3:文檔集合

中文和英文等語(yǔ)言不同,單詞之間沒(méi)有明確的分隔符號(hào),所以首先要用分詞系統(tǒng)將文檔自動(dòng)切分成單詞序列,這樣每個(gè)文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流。

為了系統(tǒng)后續(xù)處理方便,需要對(duì)每個(gè)不同的單詞賦予唯一的單詞編號(hào),同時(shí)記錄下哪些文檔包含這個(gè)單詞,在處理結(jié)束后,我們可以得到最簡(jiǎn)單的倒排索引(參考圖4)。

圖4中,“單詞ID”一列記錄了每個(gè)單詞對(duì)應(yīng)的編號(hào),第2列是對(duì)應(yīng)的單詞,第3列即每個(gè)單詞對(duì)應(yīng)的倒排列表。比如:?jiǎn)卧~“谷歌”,其中單詞編號(hào)為1,倒排列表為{1,2,3,4,5},說(shuō)明文檔集合中每個(gè)文檔都包含了這個(gè)單詞。

之所以說(shuō)圖4的倒排索引是最簡(jiǎn)單的,是因?yàn)檫@個(gè)索引系統(tǒng)只記載了哪些文檔包含某個(gè)單詞。而事實(shí)上,索引系統(tǒng)還可以記錄除此之外的更多信息。

圖5是一個(gè)相對(duì)復(fù)雜些的倒排索引,與圖4所示的基本索引系統(tǒng)相比,在單詞對(duì)應(yīng)的倒排列表中不僅記錄了文檔編號(hào),還記載了單詞頻率信息,即這個(gè)單詞在某個(gè)文檔中出現(xiàn)的次數(shù)。之所以要記錄這個(gè)信息,是因?yàn)樵~頻信息在搜索結(jié)果排序時(shí),計(jì)算查詢和文檔相似度是一個(gè)很重要的計(jì)算因子,所以將其記錄在倒排列表中,以方便后續(xù)排序時(shí)進(jìn)行分值計(jì)算。

在圖5所示的例子里,單詞“創(chuàng)始人”的單詞編號(hào)為7,對(duì)應(yīng)的倒排列表內(nèi)容有(3;1),其中3代表文檔編號(hào)為3的文檔包含這個(gè)單詞,數(shù)字1代表詞頻信息,即這個(gè)單詞在3號(hào)文檔中只出現(xiàn)過(guò)1次,其他單詞對(duì)應(yīng)的倒排列表所代表的含義與此相同。

圖4:最簡(jiǎn)單的倒排索引

圖5:帶有單詞頻率信息的倒排索引

實(shí)用的倒排索引還可以記載更多的信息,圖6所示的索引系統(tǒng)除了記錄文檔編號(hào)和單詞詞頻信息外,額外記載了兩類信息——即每個(gè)單詞對(duì)應(yīng)的文檔頻率信息(圖6的第3列)及單詞在某個(gè)文檔出現(xiàn)位置的信息。

圖6:帶有單詞頻率、文檔頻率和出現(xiàn)位置信息的倒排索引

文檔頻率信息代表了在文檔集合中有多少個(gè)文檔包含某個(gè)單詞,之所以要記錄這個(gè)信息,其原因與單詞頻率信息一樣,這個(gè)信息在搜索結(jié)果排序計(jì)算中是一個(gè)非常重要的因子。

而單詞在某個(gè)文檔中出現(xiàn)位置的信息并非索引系統(tǒng)一定要記錄的,在實(shí)際的索引系統(tǒng)里可以包含,也可以選擇不包含這個(gè)信息,之所以如此,是因?yàn)檫@個(gè)信息對(duì)于搜索系統(tǒng)來(lái)說(shuō)并非必要,位置信息只有在支持短語(yǔ)查詢的時(shí)候才能夠派上用場(chǎng)。

以單詞“拉斯”為例:其單詞編號(hào)為8,文檔頻率為2,代表整個(gè)文檔集合中有兩個(gè)文檔包含這個(gè)單詞,對(duì)應(yīng)的倒排列表為{(3;1;<4>),(5;1;<4>)},其含義為在文檔3和文檔5出現(xiàn)過(guò)這個(gè)單詞,單詞頻率都為1,單詞“拉斯”在這兩個(gè)文檔中的出現(xiàn)位置都是4,即文檔中第4個(gè)單詞是“拉斯”。

圖6所示的倒排索引已經(jīng)是一個(gè)非常完備的索引系統(tǒng),實(shí)際搜索引擎的索引結(jié)構(gòu)基本如此,區(qū)別無(wú)非是采取哪些具體的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)上述邏輯結(jié)構(gòu)。

有了這個(gè)索引系統(tǒng),搜索引擎可以很方便地響應(yīng)用戶的查詢。比如:用戶輸入查詢?cè)~ “Facebook”,搜索系統(tǒng)查找倒排索引,從中可用讀出包含這個(gè)單詞的文檔,這些文檔就是提供給用戶的搜索結(jié)果。

而利用單詞詞頻信息、文檔頻率信息即可對(duì)這些候選搜索結(jié)果進(jìn)行排序,計(jì)算文檔和查詢的相似性,按照相似性得分由高到低排序輸出,此即為搜索系統(tǒng)的部分內(nèi)部流程。

 

本文由 @kevin 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可,禁止轉(zhuǎn)載

題圖來(lái)自Unsplash,基于CCO協(xié)議

更多精彩內(nèi)容,請(qǐng)關(guān)注人人都是產(chǎn)品經(jīng)理微信公眾號(hào)或下載App
評(píng)論
評(píng)論請(qǐng)登錄
  1. 非技術(shù)出身產(chǎn)品經(jīng)理的技術(shù)溝通秘籍!15天補(bǔ)齊程序/代碼、前端、后端、數(shù)據(jù)庫(kù)4大模塊基礎(chǔ)技術(shù)知識(shí)。
    詳情戳>http://996.pm/7daXE 或咨詢起點(diǎn)學(xué)院蘑菇(wx:qdxymg)

    來(lái)自廣東 回復(fù)
  2. 我現(xiàn)在有個(gè)項(xiàng)目需要,百度搜索關(guān)鍵詞,在百度排第一怎么,做操作

    回復(fù)
  3. 看看 ??

    來(lái)自安徽 回復(fù)
  4. 我的

    回復(fù)