TWI549005B - 多層搜尋引擎索引 - Google Patents

Description

多層搜尋引擎索引

本發明係關於：多層搜尋-引擎索引。

用於定位文件(例如網頁)的策略包含：呈遞搜尋查詢至搜尋引擎，該等文件透過網路(例如網際網路)而為可獲得使用的。一些網路包含大量的文件，以使得回應於搜尋查詢而搜尋每一個別的文件係不可行的。從而，搜尋引擎經常包含：資訊的索引，該資訊的索引以一方式來組織化以赋能搜尋引擎以：識別與該搜尋查詢相關的文件。當回應於搜尋查詢時，分析該索引可為耗費成本的服務(意即可需要相對為大量的計算資源)。

與處理在搜尋-引擎索引中的資訊相關聯之成本可取決於各種因素。舉例而言，索引的結構和包含在索引中的資訊量可影響成本。此外，被使用以分析該索引的計算元件可影響成本。

由於前述原因在此提供本發明的各種態樣之高層級的總覽，以提供本揭示的總覽及作出選擇性觀念的介紹，該等觀念進一步於後文的【實施方式】的段落中描述。此【發明內容】無意於識別所請求申請標的之關鍵特徵 或必要特徵，及無意於被單獨地使用而作為助益以決定所請求申請標的之範圍。簡要地及處於高層級地，此揭示描述(除了其它事項之外(among other things))搜尋-引擎索引，該搜尋-引擎索引被利用以服務(serve)搜尋查詢。

在此描述的申請標的包含：多層搜尋-引擎索引。舉例而言，搜尋-引擎索引的一部分包含：詞彙索引(term index)，及搜尋-引擎索引的另一部分包含：文件索引(document index)。可使用各種計算元件來服務(serve)該詞彙索引和該文件索引，例如固態硬碟(solid-state drive)。

在此明確地描述本發明的選擇實施例之申請標的以符合法定要求。但是描述本身無意於定義：被視為所請求的發明者；而是，此者為：申請專利範圍所請求者。所請求的申請標的可利用其它的方式來體現以包含：不同的步驟或類似於在此文件中所描述者的步驟之組合，以與其它目前或未來的技術相結合。詞彙不應被解釋為：暗示在此揭示的各個步驟之間任何特定的順序，除非和除了當各個步驟的順序被清楚地陳述的時候。

如同所指示者，在此描述的申請標的包含：多層搜尋-引擎索引。從而，搜尋-引擎索引被分為多個索引，該等 索引的每一索引包含：個別集合的資訊，該資訊被使用以服務(意即回應於)查詢。一個索引包含：詞彙索引，該詞彙索引組織集合的詞彙，該等詞彙會在集合的文件間被找到。舉例而言，若100個文件為可獲得使用的而被搜尋，詞彙索引組織每一可搜尋詞彙，該詞彙會在每一文件的內容間被找到。另一索引包含：文件索引，該文件索引組織可搜尋的集合的文件。繼續進行已給定的實例，若100個文件為可獲得使用的而被搜尋，文件索引可包含：100個集合的文件-特定(document-specific)的資訊，其中該等集合的每一集合描述：個別的文件。計算裝置被使用以服務搜尋-引擎索引(意即當識別與搜尋查詢相關的文件時分析該索引)。從而，目前將描述示例性計算裝置。

初始特定地參照至第1圖，用於實施本發明的實施例之示例性作業環境被顯示及一般性地被指定為計算裝置100。計算裝置100僅為適當的計算環境的一個實例，及無意於顯示關於本發明的實施例之使用範圍或功能性的任何限制。計算環境100不應被解釋為：具有關於所示例說明的元件之任何一者或組合的任何相依性或要求。

本發明的實施例可用電腦代碼或機器可使用的指令之一般性上下文來描述，包含電腦可執行指令，例如程式模組，該等指令係由電腦或其它的機器來執行，例如個人資料助理或其它的手持裝置。一般而言，包含常式、程式、物件、元件、資料結構等等的程式模組意指：執 行特定任務或實施特定抽象資料型別的代碼。本發明的實施例可被實施在各種系統組態中，包含手持裝置、消費者電子裝置、一般性目的電腦、更為特殊性計算裝置等等。本發明的實施例亦可實施於分散式計算環境中，其中任務係由遠端處理裝置執行，該等遠端處理裝置係透過通訊網路來鏈結。

參照至第1圖，計算裝置100包含：匯流排110，該匯流排直接或間接地耦合下列裝置：記憶體112、一或多個處理器114、一或多個呈現元件116、輸入/輸出埠118、輸入/輸出元件120及示例說明性功率供應122。匯流排110代表：一或多個匯流排者(例如位址匯流排、資料匯流排或所述者之組合)。雖然為了清楚起見，第1圖的各個區塊用線段來圖示，實際上，描繪各個元件並非如此得清楚，及隠喻地，線段更精確地為灰色和模糊的。舉例而言，吾人可考慮呈現元件(例如顯示裝置)以作為I/O元件。亦者，處理器具有記憶體。吾人認識到：此者係技術的本質，及重申：第1圖的示圖僅示例說明示例性計算裝置，該計算裝置可與本發明的一或多個實施例結合使用。不在例如為「工作站」、「伺服器」、「膝上型電腦」、「手持裝置」等等的類型之間作出區別，如在第1圖的範圍內考慮的所有者及對「計算裝置」的參照。

計算裝置100典型地包含：各種電腦可讀取媒體。電腦可讀取媒體可為：任何可獲得使用的媒體，該等媒體 可由計算裝置100存取，及包含：揮發性和非揮發性媒體二者、可移除和不可移除媒體二者。藉由實例的方式，而非限制，電腦可讀取媒體可包含：電腦儲存媒體和通訊媒體。

電腦儲存媒體包含：揮發性和非揮發性、非暫時、可移除和不可移除媒體，該等媒體以任何方法或技術來實施以儲存資訊，例如電腦可讀取指令、資料結構、程式模組或其它資料。電腦儲存媒體包含：RAM、ROM、EEPROM、快閃記憶體或其它的記憶體技術、CD-ROM、數位影音光碟(DVD)或其它的光碟儲存、磁性卡匣、磁帶及磁碟儲存或其它的磁性儲存裝置，其中每一者可被使用以儲存所欲資訊及可由計算裝置100存取。

通訊媒體典型地體現電腦可讀取指令、資料結構、程式模組或在調變資料訊號中的其它資料，例如載波或其它的傳輸機制，及包含：任何資訊傳送媒體。詞彙「調變的資料訊號(modulated data signal)」意指：訊號，該訊號具有一或多個特性集，或以此方式改變以將資訊編碼在該訊號中。藉由實例的方式，通訊媒體包含：有線媒體，例如有線網路或直接線路連接，及無線媒體，例如聲音、RF、紅外線及其它的無線媒體。前述的任何者之組合應亦被包含在電腦可讀取媒體的範圍內。

記憶體112包含：電腦儲存媒體，該電腦儲存媒體具有揮發性及/或非揮性記憶體的形式。記憶體可為：可移除的、不可移除的或所述者之組合。示例性硬體裝置包 含：固態記憶體、硬碟機、光碟機等等。計算裝置100包含：一或多個處理器，該等處理器從各種實體讀取資料，例如記憶體112或I/O元件120。呈現元件(多個)116呈現資料指示至使用者或其它裝置。示例性呈現元件包含：顯示裝置、揚聲器、列印元件、振動元件等等。

I/O埠118允許計算裝置100邏輯地耦合至包含I/O元件120的其它裝置，其中一些者可為內建的。示例說明性元件包含：麥克風、搖桿、遊戲手把、衛星碟、掃描器、印表機、無線裝置等等。

目前參照至第2圖，其中描繪另一示例性計算環境210。環境210包含：客戶端計算裝置212，該客戶端計算裝置與搜尋引擎214交換資訊，例如藉由網路(例如網際網路)。舉例而言，客戶端212傳送資訊216至搜尋引擎214。資訊216被描繪在分解示圖218中，該分解示圖描繪：資訊216包含搜尋查詢。示例性搜尋查詢包含：搜尋詞彙「食品雜貨(grocery)」。環境210亦描繪：搜尋引擎214傳送資訊220至客戶端212，及資訊220被描繪在分解示圖222中。分解示圖222指示：資訊220包含搜尋-結果網頁(search-results webpage)，例如網頁的列表，該等網頁已被視為與包含在資訊216中的搜尋查詢相關。示例性搜尋詞彙「食品雜貨(grocery)」將遍及在各種說明中的此描述被使用。

搜尋引擎214包含各種元件，該等元件與另一者相通訊及賦能搜尋引擎214以將文件視為與搜尋查詢相關。 舉例而言，搜尋引擎214包含：複數個計算裝置(意即計算裝置1、計算裝置2...計算裝置X)，其中每一者處理個別集合的文件。第2圖描繪：計算裝置1處理文件1-100，計算裝置2處理文件101-200等等。搜尋引擎214的元件一同運作以決定：文件1-N的何者與接收的搜尋查詢相關。舉例而言，搜尋引擎214包含：搜尋-查詢接收器(search-query receiver)224，該搜尋-查詢接收器接收搜尋查詢，該等搜尋查詢被傳送至搜尋引擎214。搜尋引擎214亦包含：匹配器226及排序器228。

匹配器226識別數個文件，該等文件係搜尋查詢或搜尋詞彙的匹配者。「匹配(match)」係典型地藉由匹配演算法的應用來決定，該匹配演算法當決定文件是否為搜尋查詢的匹配者時考慮到各種因素。舉例而言，匹配演算法當決定該文件是否為匹配者時，考慮到：搜尋詞彙在文件的內容間出現的次數。匹配器226可識別：儲存在每一計算裝置(意即計算裝置1到X)上包含搜尋詞彙的所有文件。可替代性地，可建立匹配臨界值，以使得匹配器226識別：並未超過該匹配臨界值的數個匹配的文件。舉例而言，若匹配臨界值為：五個文件，則匹配器226識別在每一計算裝置上與搜尋查詢相匹配的前五個文件。當匹配器進行一些估測-排序活動(estimated-ranking activities)或預先排序活動(pre-ranking activities)時，匹配器226可不指定：在此些識別的匹配的文件間任何的最後搜尋-結果 (search-result)的排序。

排序器228接收由匹配器226視為匹配者的文件之一識別，及在彼此間排序此些匹配的文件。舉例而言，若排序器228接收前面的匹配的文件(例如作為匹配者的前面的五個文件)之識別，排序器228應用排序演算法以決定：前面的匹配的文件之每一者的個別的排序。排序演算法可考慮各種因素，其中的一些者亦可由匹配器226來考慮，及其中的其它者僅由排序器228來評估。

如同所指示者，當應用匹配演算法或排序演算法時，匹配器226及排序器228並不必然地重新檢視每一文件的全部內容。而是，搜尋引擎214包含：資訊的索引，該資訊的索引包含：從文件的每一者取出的僅有的選擇資訊。該等索引代表可搜尋文件的濃縮版本(condensed version)，及該等索引典型地相較於文件的全文更為有效率地加以分析(例如利用匹配演算法和排序演算法)。

搜尋引擎214包含：計算裝置2(由參照編號230而識別)，當服務搜尋查詢時，計算裝置2處理文件101-200。舉例而言，計算裝置2決定文件101-200的何者被視為與搜尋查詢「食品雜貨(grocery)」相關。文件101-200被描繪在分解示圖232中，該分解示圖示例說明：被使用以組織和總括文件101-200的各種資訊結構。

一種被使用以組織文件101-200的資訊結構包含：詞彙索引234。詞彙索引234係反向索引(inverted index)，該反向索引包含：在文件101-200的內容間會被找到的 可搜尋詞彙。詞彙索引234包含：集合的詞彙記錄(term postings)(例如「記錄列表1(posting list 1)」、「記錄列表2(posting list 2)」等等)，該等詞彙記錄的每一者包含：關於個別的詞彙之資訊。記錄可用各種順序排置，例如按照字母順序或按照詞彙的普遍性。第2圖描繪：記錄236包含與搜尋詞彙「食品雜貨(grocery)」相關的資訊。

典型地，每一詞彙記錄包含：被使用以決定文件是否相關於(意即匹配於)搜尋查詢的資訊。舉例而言，詞彙記錄236包含三個資訊集合(意即由參照編號238、240及242所識別)，該等資訊集合的每一者包含：與包含詞彙「食品雜貨(grocery)」的個別的文件(例如網頁)相關的資訊。與許多詞彙索引相反，詞彙索引234忽略某種類型的資訊，例如位置資訊，該位置資訊指示：在每一文件內詞彙可被找到的位置。舉例而言，資訊集合242並不包含：指示在文件M3中何處可找到詞彙「食品雜貨(grocery)」的任何資訊。藉由忽略某種類型的資訊，詞彙索引234更小，藉此減少與匹配搜尋詞彙相關聯的計算成本。雖然詞彙記錄236忽略某種類型的資訊(例如位置資訊)，該資訊當應用排序演算法時係由排序器228使用，詞彙記錄236包含：其它類型的資訊，該資訊被使用於匹配演算法以識別前面的文件匹配者，例如詞彙頻率(意即詞彙在文件中被找到的次數)。

第2圖描繪：資訊集合242包含：與文件M3相關的 資訊，該文件M3包含：詞彙「食品雜貨(grocery)」。舉例而言，資訊集合242包含：標籤「文件M3資訊(Doc M3 Info)」，該標籤指示資訊242包含：與文件M3相關的資訊。資訊集合242以一方式來編碼，該方式平衡下列期望；具有減少用以解碼資訊集合242所需的CPU使用之目的，而限制記憶體的利用。舉例而言，使用以識別文件M3的文件識別符被插入：「食品雜貨(grocery)」的詞彙頻率。雖然在此描述詞彙頻率以達到說明性目的，其它的資訊亦可(或替代性地)用該文件識別符來編碼，該文件識別符對於決定文件是否為對查詢詞彙的匹配者係有用的。

在一個實施例中，文件識別符可為增量編碼(delta encoded)的可變整數，然而詞彙頻率係可變整數。從而，示例性資訊當維持於詞彙索引234時可採取下列的形式： 解碼的版本(Decoded Version)[UInt64]+：D1,TF1,D2,TF2,D3,TF3,...

編碼的版本(Encoded Version)[UInt64]+：D1,TF1,D2-D1,TF2,D3-D2,TF3,...

替代性的編碼機制(在該編碼機制中文件識別符被插入詞彙頻率)考慮到：許多詞彙頻率低於臨界值(例如3)的事實。從而，保留一數量的位元以儲存編碼的文件資訊(意即文件識別符和詞彙頻率)。在此編碼機制下，當詞彙頻率低於頻率-數值(frequency-value)的臨界值(例 如3)時，該數量的位元被使用以編碼詞彙頻率，及額外的位元組並不被使用以編碼頻率欄位。此外，按照此機制，當詞彙頻率超過頻率-數值的臨界值，額外的位元組被使用以編碼該頻率欄位。此編碼機制可允許較佳的壓縮率，以作為減低的解碼效能的交換。從而，示例性資訊當維持於詞彙索引234時及當TF欄位固定為2位元時可採取下列的形式： 解碼的資訊(decoded information)[UInt64]+：D1,TF1,D2,TF2,D3,TF3,...

編碼的資訊(encoded information)[UInt64]+：D1,D2-D1,TF2Exception,D3-D2,...

其中，解碼邏輯係：若(TF≦3)則使用2位元以用於TF，並無額外的TF欄位

此外

2位元=“00”，具有額外的TF欄位

TF=額外的TF欄位的數值+3

在另外的實施例，在記錄中區塊可被使用以包含：出現(occurrences)之群組。舉例而言，區塊可被使用以包含；資訊集合238、240及242。在此實施例中，選擇LSB位元的數值(N)，以使得在該區塊中最高的詞彙頻率係在2^N-1內，及其它的詞彙頻率附在例外列表(exception list)中而附加至該區塊的開始處或結束處。在每一群組中，文件索引首先被編碼為VarInt，而後詞彙頻率例外地被 編碼(每個詞彙頻率用2位元)。

基於編碼機制和排序資訊的忽略，相對於包含排序資訊或使用替代性的編碼機制之其它的索引，詞彙索引234包含：較小的總大小(total size)。此較小的大小(size)允許較多的文件符合記憶體元件(例如SSD、HDD等等)，及減小當執行匹配操作時所導致的CPU成本。在一個實施例中，該詞彙索引被儲存在記憶體和SSD中及一同在記憶體和SSD中被服務，藉此利用索引服務最佳化。舉例而言，可應用在記憶體中/在緩衝區中的快取架構。

第2圖亦描繪：詞彙-索引查找表格244，該詞彙-索引查找表格包含：詞彙「食品雜貨(grocery)」對在詞彙索引234中的特定位置之映射。映射係藉由箭頭246來表示。舉例而言，映射246可為對應到在記憶體或SSD中的位置，藉此有助於定位記錄236對於「食品雜貨(grocery)」的起始點。

如同所指示者，資訊集合242包含：文件識別符，該文件識別符被使用以識別與「文件M3(Doc M3)」相關的資訊。舉例而言，箭頭248描繪：文件識別符可在每個-文件-索引查找表格(per-document-index lookup table)250中被查找，該每個-文件-索引查找表格映射該文件識別符至在每個-文件索引(per-document index)252中的位置，文件-排序資訊(document-ranking information)被維持在該每個-文件索引的該位置處。

每個-文件索引252以每個-文件為基礎來組織化，以使得每一每個-文件索引表格將關於特定文件的資訊分類。意即，若計算裝置2 230包含：文件101-200，則每個-文件索引252包含：對於包含在文件101-200的文件之每一者的每個-文件索引表格。方盒254、256及258代表關於文件101、167及200(個別地)的資訊。每一每個-文件索引表格包含：豐富的資訊，該資訊係由排序器218使用以決定個別的文件之排序。意即，排序器218將從每個-文件索引表格取出的資訊置入排序演算法以決定在搜尋結果間文件的排序。文件-排序資訊的實例包含：可典型地被包含在詞彙索引中的資訊(例如位置資訊)，但該資訊已從該詞彙索引中被忽略，以為了減小該詞彙索引的大小。此外，每一每個-文件索引表格可包含：被使用以產生標題或片段的資訊(例如文件本身的拷貝)，該資訊被使用以代表在搜尋-結果列表中的文件。

目前參照至第3圖，其中描繪來自每個-文件索引310的示例性資訊。意即，描繪在第3圖中的資訊代表：可被包含在特定文件的每個-文件索引表格中的資訊。第3圖描繪：特定文件的資訊包含：索引標頭306、映射314及詞彙索引312。

示例性索引標頭306包含：目前的文件資料(例如靜態排序、長度等等)。此外，標頭306可包含：描述包含在文件中的數個詞彙類別(例如類別1、類別2及類別3)及其它的文件特徵(例如語言)的資訊。

包含在每個-文件索引中的資訊亦包含：所有可搜尋詞彙之識別，該等詞彙被包含在文件的內容間。此些詞彙使用全域的詞彙-至-WordID映射(term-to-WordID mapping)314來編碼。第3圖指示：映射314包含：靜態映射表格318，該靜態映射表格被使用以將普遍的詞彙映射至1或2位元組的整數。此外，映射314包含雜湊函數320以將較不普遍的詞彙映射至8-位元組的雜湊數值。使用映射314，在詞彙索引312中的所有的詞彙並不用原始的文字格式來儲存，藉此節省空間。更為特定而言，包含在詞彙索引312中的每一詞彙被映射至WordID(例如整數)。在詞彙索引312中，相對於該詞彙，WordID被儲存。從而，當查找在反向詞彙索引312中的詞彙(例如食品雜貨(grocery))時，該詞彙首先在映射中被查找以識別WordID，及而後WordID在詞彙索引312中被參照。

如同所指示者，WordID可包含：二個變化中之一者：固定的映射(來自318)或雜湊映射(來自320)。一般而言，普遍的詞彙接收WordID，該WordID使用固定的映射方法來產生，以使得每一詞彙映射至在[0...2^k-1]的空間中的預先定義(pre-defined)的數字。基於詞彙的普遍性，1或2位元組被使用以產生個別的WordID。為了促進更快的搜尋，映射可被建立至與每個-文件索引相關聯的記憶體中。在示例性的實施例中，前面255個時常出現的詞彙使用1位元組的WordID來表示，及此些時常 出現的詞彙在詞彙索引312中被分類為類別1。下個前面-64K(top-64K)的詞彙在詞彙索引312中被識別為類別2的詞彙及由2位元組ID來表示。詞彙對類別1的詞彙和類別2的詞彙二者的WordID之映射(使用例如雜湊映射架構)可被明確地儲存在記憶體中。基於此些示例性的大小，及假設：平均詞彙文字長度係25位元組，此映射表格將使用大約1.6M位元組的記憶體。

在另外的實例中，較不普遍的詞彙係由6或8位元組WordID來表示(來自320)及在詞彙索引312中被識別為類別3。對在類別3的每一詞彙而言，WordID係詞彙文字的雜湊數值。假設：文件具有平均1000個獨有的詞彙，二個詞彙可在該文件中相抵觸的機率係C(2,1000)/2⁶⁴=1/2⁴⁵。對10B的文件全集，具有文詞相抵觸的文件之總數目大約為10B/2⁴⁵=0.0003。

詞彙索引312係反向詞彙索引312，該反向詞彙索引列出可搜尋詞彙的WordID，該等可搜尋詞彙被包含在該文件的內容間。每一詞彙記錄包含：當詞彙自身關聯於該文件時與此個別的詞彙相關的資訊。舉例而言，記錄項目的最高位元指示：對此詞彙是否具有多於一個的記錄(意即此詞彙是否在該文件的內容間被找到多於一次)。若詞彙僅在該文件的內容間被找到一次，則記錄位置被儲存在項目(entry)的較低位元。此情況係由箭頭324來描繪。然而，若該詞彙在該文件的內容間被找到多於一次，則該項目的較低位元包含：指向記錄列表的溢位 陣列330(overflow array)之指標。此情況係由箭頭326來描繪。

溢位陣列330儲存用於在文件的內容間具有多於一個位置的詞彙之額外的記錄位置。每一項目的最高位元係連續位元以表示下個項目是否屬於目前的詞彙。若該位元為0，則目前的項目係在詞彙的記錄列表中的最後一個項目。每一位置項目使用固定數目的位元組以儲存位置資訊，及大小取決於該文件的總大小。

返回參照至第2圖，排序器228從每個-文件索引取出資訊以利用排序演算法來分析。舉例而言，一旦文件匹配者已由匹配器226所識別，排序器228從每一文件匹配者的個別的每個-文件索引中擷取資訊，及決定在文件匹配者間個別的排序。在一個實施例中，每個-文件索引表格被儲存在固態記憶體中，藉此利用I/O效能能力。舉例而言，匹配的文件(意即被匹配器226識別為匹配者的文件)之每個-文件索引資訊可依需要載入。

藉由應用多層索引方法，如同前文所描述者，多個查詢可被平行地服務。舉例而言，當第一查詢的處理從匹配器226進行至排序器228，在相同的計算裝置上的第二查詢之匹配處理可開始進行，即使該第一查詢依然正由排序器228處理。此外，在SSD中的服務詞彙索引234和每個-文件索引304允許搜尋引擎214利用SSD的效能能力以用於更為有效率的查詢服務。

目前參照至第4圖，流程圖描繪：一系列的步驟，該 等步驟促進：將文件視為與搜尋查詢相關的方法410。當描述第4圖時，亦可參照第2圖和第3圖以達到說明性目的。在一個實施例中，電腦-儲存媒體包含：體現於其上的電腦可執行指令，當執行該等指令時，執行在第4圖中識別的步驟。舉例而言，由參照編號260和262識別的一或多個應用程式係個別地由匹配器和排序器來執行。當執行應用程式260和262時，進行方法410的步驟。

方法410在步驟412包含以下步驟：藉由搜尋引擎接收搜尋查詢，該搜尋查詢包含：搜尋詞彙。舉例而言，如同已描述者，搜尋-查詢接收器224接收包含「食品雜貨(grocery)」的搜尋查詢以作為搜尋詞彙。搜尋引擎214包含：詞彙索引234，該詞彙索引具有多個記錄，及記錄236包含：關於搜尋詞彙「食品雜貨(grocery)」的資訊。

步驟414包含以下步驟：重新檢視詞彙記錄，該詞彙記錄具有關於搜尋詞彙的資訊，其中關於搜尋詞彙的資訊包含：該文件的文件識別符，該文件的該文件識別符包含搜尋詞彙。舉例而言，重新檢視記錄236，該記錄包含：「文件M3(Doc M3)」的文件識別符，該「文件M3(Doc M3)」的文件識別符包含：在文件M3(Doc M3)內容間的詞彙「食品雜貨(grocery)」。

在步驟416中，文件識別符被使用以參照在每個-文件索引中的文件-排序資訊，其中該文件-排序資訊被使用 以指定搜尋-結果排序至該文件。舉例而言，箭頭248代表被使用以參照文件-排序資訊的文件識別符。如同前文所描述者，文件識別符在查找表格250中被映射至在每個-文件索引中的文件-排序資訊之位置。

按照步驟418，提供(serve)搜尋結果，其中該文件的列表被呈現為與搜尋-結果排序相一致。舉例而言，提供資訊220至客戶端212，該資訊包含搜尋-結果網頁。搜尋-結果網頁基於由排序器228決定的排序資訊來產生。

方法410描述：用於服務搜尋查詢的步驟。當使用多層搜尋-引擎索引時，如在此所描述者，查詢-服務流程可和與單一的索引一同使用的該流程維持為相類似，例如藉由從匹配於排序估計的文件移動至最後的排序。然而，當搜尋引擎利用分別的索引及固態硬碟的輸入/輸出效能能力，可增進查詢-服務效能，例如藉由平行地執行多個搜尋查詢。

目前參照至第5圖，另一流程圖描繪：一系列的步驟，該等步驟促進對在搜尋-引擎索引中的文件(例如由資訊集合256描述的文件167)進行索引而允許搜尋引擎以評定文件對搜尋查詢(例如「食品雜貨(grocery)」)的相關性之方法510。當描述第5圖時，亦可參照第2圖和第3圖以達到說明性目的。在一個實施例中，電腦-儲存媒體包含：體現於其上的電腦可執行指令，當該等指令被執行時，執行在第5圖中所識別的步驟。

方法510在步驟512包含以下步驟：指定文件識別符 至該文件。舉例而言，當第2圖的文件M3(Doc M3)進行處理，文件識別符被指定至文件M3及被儲存在每個-文件-索引查找表格中。步驟514包含以下步驟：決定詞彙被包含在文件的內容間所具有的頻率。舉例而言，計算詞彙「食品雜貨(grocery)」被包含在文件M3的次數。如同已描述者，搜尋-引擎索引包含：詞彙索引234，該詞彙索引包含：詞彙記錄236，該詞彙記錄具有與詞彙(意即「食品雜貨(grocery)」)相關的資訊。

按照步驟516，文件識別符與頻率一起被編碼以產生編碼的文件資訊。詞彙記錄經變換以包含編碼的文件資訊。此外，步驟518包含以下步驟：儲存集合的文件-排序資訊在每個-文件索引(分別於詞彙索引)中。當處理搜尋查詢時，文件-排序資訊被使用以排序該文件。舉例而言，詞彙記錄236被更新以包含在資訊集合242中的編碼的文件資訊。同樣地，包含在資訊256的每個-文件索引表格儲存：從文件M3取出的文件-排序資訊。

前述已描述：數個元件之系統，該等元件可使用於對文件進行索引及服務搜尋-引擎查詢。舉例而言，描繪在第2圖和第3圖的系統包含：多個索引(例如詞彙索引234及每個-文件索引310)，該等索引組織個別集合的資訊，該等索引對匹配器226、排序器228及其它的搜尋引擎元件為可獲得使用的。此外，已描述：可使用前文描述的搜尋-引擎元件來執行的方法，例如用於服務搜尋查詢的方法和用於對文件進行索引的方法。

所描繪的各種元件和未顯示的元件之許多不同的排置係可能的，而不偏離後文的申請專利範圍之範疇。已描述了吾人的技術之實施例，意欲作為示例說明性，而非限制性。替代性的實施例對此揭示的讀者而言在閱讀該揭示之後及因為進行了該揭示的閱讀而將變為顯明的。可完成：實施前述者的替代性構件(means)，而不偏離後文的申請專利範圍之範疇。特定的特徵和子組合係實用的及可不參照其它的特徵和子組合來運用，及特定的特徵和子組合被考慮在申請專利範圍的範疇內。

100‧‧‧計算裝置

110‧‧‧匯流排

112‧‧‧記憶體

114‧‧‧處理器

116‧‧‧呈現元件

118‧‧‧輸入/輸出埠

120‧‧‧輸入/輸出元件

122‧‧‧功率供應

210‧‧‧計算環境

212‧‧‧客戶端計算裝置

214‧‧‧搜尋引擎

216‧‧‧資訊

218‧‧‧分解示圖

220‧‧‧資訊

222‧‧‧分解示圖

224‧‧‧搜尋-查詢接收器

226‧‧‧匹配器

228‧‧‧排序器

230‧‧‧計算裝置2

232‧‧‧分解示圖

234‧‧‧詞彙索引

324‧‧‧箭頭

326‧‧‧箭頭

330‧‧‧溢位陣列

236‧‧‧記錄

238‧‧‧資訊集合

240‧‧‧資訊集合

242‧‧‧資訊集合

244‧‧‧詞彙-索引查找表格

246‧‧‧映射

248‧‧‧箭頭

250‧‧‧每個-文件-索引查找表格

252‧‧‧每個-文件索引

254‧‧‧方盒

256‧‧‧方盒

258‧‧‧方盒

260‧‧‧應用程式

262‧‧‧應用程式

306‧‧‧索引標頭

310‧‧‧每個-文件索引

312‧‧‧詞彙索引

314‧‧‧映射

318‧‧‧靜態映射表格

320‧‧‧雜湊函數

410‧‧‧方法/步驟

412‧‧‧方法/步驟

414‧‧‧方法/步驟

416‧‧‧方法/步驟

418‧‧‧方法/步驟

510‧‧‧方法/步驟

512‧‧‧方法/步驟

514‧‧‧方法/步驟

516‧‧‧方法/步驟

518‧‧‧方法/步驟

於後文中參照隨附圖式詳細地描述本發明的示例說明性實施例，其中：

第1圖和第2圖每一者描繪個別的示例性計算環境。

第3圖描繪在每個-文件索引(per-document index)中分類的資訊之實例；及第4圖和第5圖包含：描繪個別的方法之流程圖。

210‧‧‧計算環境

212‧‧‧客戶端計算裝置

214‧‧‧搜尋引擎

216‧‧‧資訊

218‧‧‧分解示圖

220‧‧‧資訊

222‧‧‧分解示圖

224‧‧‧搜尋-查詢接收器

226‧‧‧匹配器

228‧‧‧排序器

230‧‧‧計算裝置2

232‧‧‧分解示圖

234‧‧‧詞彙索引

236‧‧‧記錄

238‧‧‧資訊集合

240‧‧‧資訊集合

242‧‧‧資訊集合

244‧‧‧詞彙-索引查找表格

246‧‧‧映射

248‧‧‧箭頭

250‧‧‧每個-文件-索引查找表格

252‧‧‧每個-文件索引

254‧‧‧方盒

256‧‧‧方盒

258‧‧‧方盒

260‧‧‧應用程式

262‧‧‧應用程式

Claims (16)

1. 一種儲存有電腦可執行指令之電腦硬體記憶體裝置，當該等指令被執行時進行將一文件視為與一搜尋查詢相關的一方法，該方法包含以下步驟：藉由一搜尋引擎，來接收該搜尋查詢，該搜尋查詢包含一搜尋詞彙，其中該搜尋引擎包含複數個計算裝置，該等複數個計算裝置之每一者處理一組個別的文件，其中該等複數個計算裝置之每一計算裝置包含：一詞彙索引查找表格、一詞彙索引、一每個-文件索引查找表格及一每個-文件索引，其中該詞彙索引包含複數個詞彙記錄(posting)，而每一詞彙記錄包含：一個別的詞彙及視為與該個別的詞彙相關的每一文件的一文件識別符；及其中每一詞彙記錄忽略指示出在每一文件中發現該個別的詞彙之位置的資訊；藉由重新檢視該等複數個詞彙記錄及在該搜尋詞彙與該等個別的詞彙中之至少一者之間發現一匹配，來判斷出一或更多個文件是與該搜尋詞彙相關；(i)藉由使用每一文件的該文件識別符以存取一每個-文件索引查找表格及(ii)藉由將該一或更多個文件根據針對每一文件從該每個-文件索引所獲得的文件排序資訊進行排序，來決定出經判斷為相關的該一或更 多個文件的一搜尋結果排序，該每個-文件索引查找表格將每一文件識別符映射到在該每個-文件索引中的該文件排序資訊，其中該每個-文件索引將與一文件相關的該文件排序資訊組織成一每個-文件索引標頭、一詞彙至編號(ID)映射及一文件特定的詞彙索引；其中該詞彙至ID映射將該搜尋詞彙映射到一唯一識別符，該唯一識別符在該文件特定的詞彙索引中識別出該搜尋詞彙；及其中該文件特定的詞彙索引儲存位置資訊，該位置資訊(i)描述出在該文件中的該搜尋詞彙的一或更多個位置及(ii)用以決定出該文件的該搜尋結果排序；及提供(serving)搜尋結果，其中經排序的該一或更多個文件的一列表被呈現為與該搜尋結果排序相一致。
2. 如申請專利範圍第1項所述之電腦硬體記憶體裝置，其中該詞彙索引與該每個-文件索引二者被儲存在一固態硬碟(solid-state drive)中，該詞彙索引與該每個-文件索引代表分別的索引。
3. 如申請專利範圍第2項所述之電腦硬體記憶體裝置，其中該搜尋引擎利用該等分別的索引及該固態硬碟的輸入/輸出的效能能力二者，以平行地執行多個搜尋查詢。
4. 如申請專利範圍第1項所述之電腦硬體記憶體裝置，其中每一詞彙記錄包含針對每一文件的文件匹配資訊，該文件匹配資訊用以判斷出該文件是該搜尋詞彙的一匹配者。
5. 如申請專利範圍第1項所述之電腦硬體記憶體裝置，其中該每個-文件索引查找表格包含：一指標，該指標指向儲存在一固態硬碟中的該文件排序資訊。
6. 如申請專利範圍第1項所述之電腦硬體記憶體裝置，其中每一詞彙記錄包含針對每一文件的一詞彙頻率值，該詞彙頻率值指示出該搜尋詞彙在該文件中被發現的次數。
7. 如申請專利範圍第6項所述之電腦硬體記憶體裝置，其中詞彙頻率及該文件識別符是一起編碼的。
8. 如申請專利範圍第1項所述之電腦硬體記憶體裝置，其中該文件特定的詞彙索引包含複數個文件特定的詞彙記錄，及其中當在該文件的內容之間發現該搜尋詞彙的次數超過一閾值次數時，該搜尋詞彙的一文件特定的詞彙索引包含一溢位列表。
9. 一種包含耦合至電腦儲存媒體的一處理器和將一文件視為與一搜尋查詢相關的系統，該系統包含：一搜尋引擎，該搜尋引擎具有一搜尋-查詢接收器，該搜尋-查詢接收器接收該搜尋查詢，該搜尋查詢包含一搜尋詞彙，其中該搜尋引擎包含複數個計算裝置，該等複數個計算裝置之每一者處理一組個別的文件，其中該等複數個計算裝置之每一計算裝置包含：一詞彙索引查找表格、一詞彙索引、一每個-文件索引查找表格及一每個-文件索引，其中該詞彙索引包含複數個詞彙記錄，而每一詞彙記錄包含：一個別的詞彙及視為與該個別的詞彙相關的每一文件的一文件識別符；及其中每一詞彙記錄忽略指示出在每一文件中發現該個別的詞彙之位置的資訊；一匹配器，該匹配器藉由重新檢視該等複數個詞彙記錄及在該搜尋詞彙與該等個別的詞彙中之至少一者之間發現一匹配，來判斷出一或更多個文件是與該搜尋詞彙相關；及一排序器，該排序器(i)藉由使用每一文件的該文件識別符以存取一每個-文件索引查找表格及(ii)藉由將該一或更多個文件根據針對每一文件從該每個-文件索引所獲得的文件排序資訊進行排序，來決定出經判斷為相關的該一或更多個文件的一搜尋結果排序，該 每個-文件索引查找表格將每一文件識別符映射到在該每個-文件索引中的該文件排序資訊，其中該每個-文件索引將與一文件相關的該文件排序資訊組織成一每個-文件索引標頭、一詞彙至ID映射及一文件特定的詞彙索引；其中該詞彙至ID映射將該搜尋詞彙映射到一唯一識別符，該唯一識別符在該文件特定的詞彙索引中識別出該搜尋詞彙；其中該文件特定的詞彙索引儲存位置資訊，該位置資訊(i)描述出在該文件中的該搜尋詞彙的一或更多個位置及(ii)用以決定出該文件的該搜尋結果排序；及其中所提供的搜尋結果包含該一或更多個文件的一列表，該一或更多個文件的該列表被呈現為與該搜尋結果排序相一致。
10. 如申請專利範圍第9所述之系統，其中該詞彙索引與該每個-文件索引二者被儲存在一固態硬碟中，該詞彙索引與該每個-文件索引代表分別的索引。
11. 如申請專利範圍第10項所述之系統，其中該搜尋引擎利用該等分別的索引及該面態硬碟的輸入/輸出的效能能力，以平行地執行多個搜尋查詢。
12. 如申請專利範圍第9項所述之系統，其中該每個-文件索引查找表格將該文件識別符映射至在一固態硬碟中的該文件排序資訊。
13. 如申請專利範圍第9項所述之系統，其中該詞彙至ID映射將可搜尋詞彙映射至一個別的識別符，該識別符用以編碼一個別的可搜尋詞彙。
14. 如申請專利範圍第9項所述之系統，其中每一詞彙記錄包含針對每一文件的一詞彙頻率值，該詞彙頻率值指示出該搜尋詞彙在該文件中被發現的次數。
15. 如申請專利範圍第14項所述之系統，其中詞彙頻率及該文件識別符是一起編碼的。
16. 如申請專利範圍第9項所述之系統，其中該文件特定的詞彙索引包含複數個文件特定的詞彙記錄，及其中當在該文件的內容之間發現該搜尋詞彙的次數超過一閾值次數時，該搜尋詞彙的一文件特定的詞彙索引包含一溢位列表。