用於記號空間資料庫的多級查詢處理系統與方法
2023-09-20 00:01:10
專利名稱：用於記號空間資料庫的多級查詢處理系統與方法
技術領域：
總體上講，所公開的實施例涉及數據處理系統與方法，具體地講，涉及用於具有相關索引的文檔集合(以下，將其稱為「記號(token)空間資料庫」)的多級查詢處理系統與方法。
背景技術：
信息檢索系統(例如，搜尋引擎)使得查詢與根據文檔集(例如全球資訊網)所生成的文檔的索引相匹配。典型的逆索引(inverse index)包括每個文檔中的單詞，以及指向它們在文檔中的部位的指針。文檔處理系統通過使用自動的或手動進程處理從文檔集所檢索到的文檔、頁或地址的內容，來製備倒排索引(inverted index)。文檔處理系統還可以把文檔的內容或內容的各部分存儲在資料庫中，以供查詢處理器在響應查詢時使用。
一直存在著對更複雜的搜索和記分技術(scoring technique)的需求，以確保查詢結果與查詢相關聯。某些記分技術可能要求對候選文檔進行部分重構，例如確定文檔中所發現的查詢項或關鍵字的上下文。令人感到遺憾的是，引入這樣複雜的技術可能會由於所涉及的額外的處理和開銷而導致搜索性能的降低。
發明內容
所公開的實施例包括與一種用於記號空間資料庫的多級查詢處理系統與方法。所述多級查詢處理系統與方法通過由多層映射方案所簡化的遞增文檔重構而能夠多級查詢記分，包括「片段(snippet)」生成。在多級查詢處理系統的一或多級，使用相關性得分集合，選擇作文檔子集作為有序列表呈現給用戶。該相關性得分集合可以部分地從所述多級查詢處理系統的先前級中所確定的一個或多個相關性得分集合中導出。在某些實施例中，多級查詢處理系統能夠對用戶查詢執行一或多遍，並且能夠使用來自每個遍的信息，擴展用於後一遍中的用戶查詢，以改進有序列表中的文檔的相關性。
圖1為信息檢索系統的實施例的方框圖。
圖2為圖1的詞典生成器的實施例的概念性方框圖。
圖3A為用於記號空間資料庫的、對文檔進行編碼的編碼系統的實施例的方框圖。
圖3B為用於記號空間資料庫中的、對文檔進行解碼的解碼系統的實施例的方框圖。
圖3C為用於對文檔屬性進行編碼/解碼的屬性編碼/解碼系統的實施例的方框圖。
圖4為用於記號空間資料庫的查詢處理系統的實施例的方框圖。
圖5為用於記號空間資料庫的多級查詢處理系統的實施例的方框圖。
圖6為記號空間資料庫伺服器的實施例的方框圖。
圖7為查詢處理伺服器的實施例的方框圖。
圖8A為記號化文檔資料庫的第二實施例的方框圖；以及圖8B為圖1的詞典生成器的第二實施例的概念方框圖。
圖9A為用於詞典生成器的實施例中的編碼進程的概念圖，以及圖9B描述了用於表示編碼的記號的示例性數據結構。
在這些圖中的多個圖中，相同的參照標記指示相應的部分。
具體實施例方式
系統概述圖1為信息檢索系統100的實施例的方框圖。信息檢索系統100包括文檔處理系統102和查詢處理系統104。信息檢索系統100可以為任何一種能夠響應查詢而檢索信息(例如，文件、電子郵件、應用程式等)的系統，包括但不局限於，用於在諸如Internet(例如，經由全球資訊網)或者內部網(Intranet)的一個或多個網絡上或在本地的用戶的計算機上執行明確的或隱含的文檔搜索的一個或多個計算機系統。注意，項「文檔」意指文檔、網頁、電子郵件、專用(application specific)文檔和數據結構、即時消息處理(IM)消息、音頻文件、視頻文件、以及可以駐留在一個或多個計算機系統上的任何其它數據或應用程式。
文檔處理系統文檔處理系統102通常包括一個或多個文檔資料庫106、詞典生成器108、編碼/解碼系統110以及記號空間資料庫112。編碼/解碼系統110從一個或多個文檔資料庫106中檢索文檔，將文檔解析為記號，使用來自詞典生成器108的映射，把記號編碼為一種壓縮的格式，然後把編碼的記號存儲在記號空間資料庫112中。
「記號」可以為通常在文檔中所發現的任何對象，包括但不局限於，項、短語、標點、HTML標籤等。在解析之後，文檔的集合表示為記號序列。而且，該記號序列中的每個記號都具有記號位置，該記號位置也代表該記號在文檔集合中的位置。例如，該文檔集合中的第一個記號可以被賦予位置0，該文檔集合中的第二個記號可以被賦予位置1，等等。
需要注意的是，在某些實施方式中，採用與用於對文檔進行解碼的計算機完全不同的計算機集合來對文檔進行編碼。例如，網蠕動(crawling)系統可以包括對文檔進行編碼的文檔處理系統102，而查詢處理系統104可以對編碼文檔的所選擇部分進行解碼。在這樣的實施方式中，由文檔處理系統102所編制的文檔逆索引和記號空間資料庫112或其拷貝，由查詢處理系統104使用。
詞典生成器108通過對文檔進行解析，生成用於對文檔集合進行編碼的映射(mapping)。此處，把詞典生成器108所產生的第一映射稱為全局詞典，全局詞典標識文檔集合中的所有不同的記號(此處，稱為唯一記號)，並且把全局記號標識符賦予每個唯一記號。由詞典生成器108所產生的第二映射實際上為映射的序列，此處，將其中的每個映射稱為小詞典。每個相應的小詞典僅用於對文檔集合中位置的相應範圍進行編碼和解碼。以下將更詳細地解釋全局詞典和小詞典的生成和使用。
查詢處理系統查詢處理系統104包括耦接於編碼/解碼系統110的一個或多個查詢處理器114以及記號空間逆索引116。記號空間逆索引116把文檔集合中的所有GTokenID映射到它們在文檔中的位置。從概念上講，逆索引116包括針對每個GTokenID的記號位置的列表。為有效起見，對每個GTokenID的記號位置的列表進行編碼，以減小逆索引所佔空間量。
在某些實施例中，一個或多個查詢處理器114把一個查詢進行解析為多個查詢項(terms)，這些查詢項被一個或多個查詢處理器114變換成查詢表達式(例如，布爾樹表達式)。使用查詢項對記號空間逆索引116編索引，以檢索記號位置，以下將參照圖4更全面地對此加以描述。在某些實施例中，把記號位置用於多級查詢處理系統，該多級查詢處理系統用於對與查詢相關的文檔進行記分，如針對圖5所描述的。相應於查詢項，查詢處理器114生成經由一個或多個通信模式(例如顯示設備、音頻等)呈現給用戶的文檔的有序列表。
詞典生成器圖2為圖1的詞典生成器108的實施例的概念性方框圖。詞典生成器108包括全局詞典編制器(builder)202和小詞典編制器204。
全局詞典編制器全局詞典編制器202從文檔資料庫106中檢索文檔，並且通過把唯一全局記號標識符(GTokenID)賦予包含在文檔中的每個唯一記號，生成全局詞典206。在某些實施例中，文檔資料庫106被邏輯地或物理地劃分成多個部分，有時將它們稱為分區(partition)，並且針對每個分區生成獨立的全局詞典206。在一個實施例中，數十億個文檔的集合劃被分成數千個分區，對每個分區進行處理，以生成全局詞典206。典型的全局詞典206可以包括數百萬個唯一記號。
在某些實施例中，在把文檔解析成記號以及對記號進行處理之前，要被編碼的文檔集合(例如，一個分區中的文檔)根據一個或多個準則進行分類。對文檔的這種分類有助於對記號化的文檔進行有效的編碼，因為使用了類似的單詞集合的文檔將被彼此相近地放置在文檔集合中。因此，與相反的情況相比，，每個小詞典(以下所描述的)將平均覆蓋文檔集合的一個較大的部分，而且，文檔的編碼將佔用較少的空間。在一個實施例中，首先根據語言對文檔集合進行分類，然後，針對每種語言，根據URL對文檔進行分類，其中URL的主機名部分的欄位依次反轉。例如，在根據語言進行分類之後，把所有的法語文檔集合在一起，然後將根據URL對法語文檔進行分類。當根據URL進行分類時，每個URL最初包括一個h1.h2...hy.hz/n1/n2...的模式，其中，h1.h2...hy.hz包括URL的主機名部分，而/n1/n2代表URL的餘留部分。在根據URL進行分類之前，把URL重新映射到模式hy.hz...hy.hz/n1/n2...。例如，把URL「www.google.com/about.html」重新映射到「com.google.www/about.html」。通過在根據URL進行分類之前反轉URL的主機名欄位，可以根據文檔相互間的邏輯接近性對文檔進行分類。因此，可以把相似類型的文檔(在針對某一具體語言的文檔組中)集合在一起；在針對每個文檔類型的文檔組中，把每個網點上的文檔集合在一起；在針對每個網點的文檔中，把針對網點的不同分支的文檔集合在一起；等等。
在某些實施例中，使用一種或多種群集技術對文檔進行排序。可以使用包含在文檔中的項(term)、單詞或短語，把文檔組織成與各種概念相關的群集。例如，可以把關於文檔的一般信息(例如，嵌入所標識的文檔或與所標識的文檔相關的元數據)、從所標識的文檔所取樣的內容、和/或關於文檔的類別信息用於對文檔排序。
在某些實施例中，當對文檔進解析時，全局詞典編制器202存儲有關每個所標識的唯一記號的信息(未在圖2中加以描述)，例如，文檔集合中的每個唯一記號的出現的次數，以及與所述唯一記號相關的語言(如果存在的話)。可以根據與其中發現所述唯一記號的文檔相關的語言，來確定與該記號相關的語言。當在與一種以上的語言相關的文檔中發現特定記號時，可以使用任何適當的方法確定與該記號相關的語言。一種適當的方法是統計方法，該方法在解析文檔集合以便標識唯一記號時使用。最初，把每個記號賦予其中發現該記號的第一文檔的語言，然後，針對出現在與賦予該記號的當前語言不同的一種語言的文檔中的記號的每次相繼的出現，僅當在0和1之間隨機(偽隨機)選擇的數小於1/N時，該記號都被重新賦予另一種語言，其中，N為所述記號的出現的當前次數。在其它一些實施例中，可以使用任何類似或適當的語言賦予機制，使得語言與每個唯一記號相關聯。在某些實施例中，不把語言與代表標點符號的唯一記號相關聯。在又一個實施例中，當可以把語言與每個唯一記號相關聯時，當處理N個(例如256個)最頻繁出現的記號時，忽略語言關聯。因此，有效地忽略了與標點記號相關的語言。
在某些實施例中，根據唯一記號出現的頻度，對唯一記號的列表、以及相關的頻度和語言信息進行分類。作為選擇，接下來，還可以對條目進行分類，以有助於對文檔集合進行節省空間的編碼。例如，在一個實施例中，首先根據出現頻度對所有唯一記號進行分類。然後把唯一記號的所得到的分類列表劃分成頻帶(band)。例如，頂級頻帶，即，頻帶0，可以包括最多255或256個記號(即，那些具有最高頻度的記號)。第二個頻帶，即頻帶1，可以包括最多214個(即65536個)記號，不含頻帶0中的記號。第三個頻帶，即頻帶2，可以包括所分類的唯一記號的列表中接下來的214個(即65536個)記號。當然，在其它一些實施例中，每個頻帶中的記號的數目可以不同。接下來，根據第二準則集合，對每個頻帶中的記號進行分類。例如，在一個實施例中，按字母順序、即按數字和字母的值，對第一頻帶中的記號進行分類。首先，按語言對每個其它頻帶中的記號進行分類，然後按字母順對它們進行分類。因此，除頻帶0之外，根據語言，對每個頻帶中所分類的記號進行了分組，而且在每個語言組中，按字母順對記號進行了分類。在其它一些實施例中，可以使用其它分類準則，對每個頻帶中的唯一記號的分類。
分類過程產生了唯一記號的分類的列表，每個唯一記號在列表中具有相應的位置。然後，向每個所分類的唯一記號賦予唯一的全局記號標識符(以下，也將其稱為「GTokenID」)。GTokenID根據用於實現文檔處理系統102的平臺可以包括任何適當的數據類型與寬度(例如，32個比特的無符號整數)。在某些實施例中，按遞增次序把GTokenID賦予所分類的唯一記號，以致可以向高頻度記號賦予小值的GTokenID，以及向低頻度記號賦予大值的GTokenID。更具體地講，在一個實施例中，向所分類的記號列表中的每個記號賦予等於其在唯一記號的分類列表中的數值位置的32個比特的全局記號標識符。於是，向列表中的第一個記號賦予等於0(即，十六進位格式的00000000)的GtokenID，向列表中的第二個記號賦予等於1的GtokenID，等等。此處，把GTokenID映射到唯一記號值的結果集合稱為全局詞典206。在某些實施例中，全局詞典206實際上包括兩個映射結構，一個把GTokenID映射到記號，另一個把記號映射到GTokenID。在編碼過程期間使用記號向GTokenID的映射，而在對文檔的一些部分進行解碼時，使用GTokenID向記號的映射。
如以下將更全面地加以解釋的，根據頻度對唯一記號進行排序，有助於減小存儲小詞典208所需的空間量。在那些其中根據除出現頻度之外的其它準則對唯一記號的區進行分類的實施例中，情況更是如此，因為賦予較低GTokenID的頻帶中的記號比賦予較高GTokenID的頻帶中的記號具有更高的出現頻度。
在某些實施例中，向那些比普通記號更頻繁出現的「特殊」記號，例如HTML標籤和標點，賦予佔據了全局詞典206中的GtokenID的前綴205部分(例如，GTokenID0-GTokenIDN-1)的GtokenID。可以把所有其它的GTokenID位移分配給前綴205的最後特殊的GTokenID。
在以上的討論中，把GTokenID描述為固定長度值，例如32個比特的無符號整數值。然而，也可以把這些同樣的GTokenID視為可變長度標識符，因為當為了存儲對GTokenID進行編碼時，可以在編碼期間截斷或屏蔽等於0的最高有效字節(或比特)。例如，在某些實施例中，把具有小於28的值的所有GTokenID編碼為單字節值，把具有小於216的值的所有GTokenID編碼為二字節值，以及把具有小於224的值的所有GTokenID編碼為三字節值。在這一方式下，與具有低出現頻度的記號相比，用較短長度的GTokenID表示文檔集合中具有最高出現頻度的記號。
在以下所描述的實施例中，記號空間資料庫中填充了有固定長度的LTokenID，而不是可變長度的GTokenID。然而，把記號空間資料庫中的LTokenID映射回原始記號(當然，它們也為可變長度的)，需要存儲大量的「小詞典」，而且小詞典內容包括GTokenID。為了有效存儲小詞典，可以把每個小詞典中的GtokenID當作可變長度值。作為選擇，每個小詞典中的GtokenID也可以被作為這樣列表首先對其進行Delta編碼，然後使用可變長度的編碼方案對所得到的Delta值進行編碼。
小詞典編制器在生成了全局詞典206之後，由小詞典編制器204生成小詞典集合208，供編碼/解碼系統110使用。小詞典208中的每個條目包括GTokenID和相應的局部記號標識符(LTokenID)。小詞典208中的條目的位置暗示了每個條目的LTokenID，因此不需要顯式地存儲。每個相應的小詞典208僅用於對記號化文檔中的記號位置的不同的、相應的具體範圍進行編碼和解碼，從而允許每個小詞典208使用相同的LTokenID集合。例如，當小詞典編制器204對整個文檔進行解析時，針對小詞典編制器204所遇到的前P個唯一記號，生成具有P個(例如256個)條目的第一小詞典208(即，小詞典A)。一旦已經遇到前P個唯一記號，則針對第一小詞典208對於其為有效的記號位置的範圍，產生包括開始記號位置Start_PosA的「有效範圍映射」210中的第一條目。把第一小詞典208中P個LTokenID中的每個LTokenID賦予唯一的GTokenID。當已經把所有LTokenID賦予GTokenID時，針對小詞典編制器204所有遇到的下P個唯一記號，生成第二小詞典208(例如，小詞典B)，並且在有效範圍映射210中產生第二條目，其中有效範圍映射210包括第二小詞典208對於其為有效的位置範圍的開始記號位置Start_PosB。因此，可以使用小詞典B對具有落入範圍Start_PosB～Start_PosC-1中的記號化的文檔中的一個位置的記號進行解碼，如圖2中所示。
為了提供具體的例子，在一個實施例中，每個小詞典中的LTokenID具有值0～255，每個值均由8個比特的無符號整數加以表示，而GTokenID為32個比特的無符號整數。通過從記號位置0開始，直至標識了預先規定數目的P個(例如256個)不同的記號，掃描文檔集合，生成第一小詞典。把這P個不同記號的GTokenID彙編(assemble)於列表中。在某些實施例中，根據數值值對列表中的GTokenID進行分類，其中，最小的GTokenID處於列表的頂部。然後，根據列表中GTokenID的位置，把LTokenID賦予列表中的GTokenID。例如，把一個為0的LTokenID賦予列表中的第一GTokenID，把一個為1的LTokenID賦予列表中的下一個GTokenID，等等。把所得到的從LTokenID至GTokenID的映射稱為小詞典208。從Start_PosA～Start_PosB的記號位置的範圍與該小詞典相關聯。通過從緊隨與第一小詞典相關聯的最後位置的位置Start_PosB開始掃描文檔集合，生成第二小詞典。這一掃描繼續，直至識別出了預定數目的P個不同的記號，在這一位置，使用與以上所描述的相同的過程，生成第二小詞典。小詞典編制器204繼續針對文檔集合中的相繼的記號位置範圍生成小詞典208的序列，直至文檔中的所有記號都被映射到小詞典208。
在一個可選的實施例中，每個小詞典208中的前F個LTokenID保留給文檔集合中F個最流行(popular)的記號。對於這F個LTokenID，LTokenID總是等於GTokenID。該賦值方案有助於對文檔的快速解碼。凡當對具有F-1或小於F-1的值的LTokenID(在記號空間資料庫中)進行解碼時，可以根據全局詞典將其直接映射到記號，而無需首先把LTokenID映射到相應的GTokenID。
在每個小詞典208使用相同的LTokenID集合(例如0～255個)。為了有助於壓縮文檔，與GTokenID(例如4個字節)相比，LTokenID具有較小的寬度(例如1個字節)。該寬度差(3個字節)表明用於把記號化的文檔存儲於記號空間資料庫112中的每記號的字節數據的減少。在一個其中每個LtokenID佔用一個字節的實施例中，在忽略其它支持數據結構所佔空間(本文獻中，以下將對它們加以描述)的情況下，具有10億個記號的文檔集合將佔用記號空間資料庫112中10億個字節(1GB)。
當完成了生成小詞典208的過程時，根據每個記號在記號化的文檔中的位置，把記號化的文檔中的每個記號與小詞典208相關聯。注意，如果記號化的文檔中的每個唯一記號出現在一個以上的位置範圍中，則可以把該記號與一個以上的小詞典208相關聯。在一個實施例中，一般的文檔具有大約1100個記號，一般的小詞典208囊括大約1000個記號。
在生成了每個小詞典208之後，編碼/解碼系統110把文檔集合的相應部分中的記號映射到LTokenID，並且將它們存儲在記號空間資料庫112中，以用於相繼的檢索。通過這一映射，把文檔資料庫106中的每個記號映射到記號空間資料庫112中的固定長度(例如一個字節)的LTokenID。於是，在解碼/解壓縮期間，在記號空間資料庫112中，從一個記號位置跳至另一個記號位置，而無需可能減慢解碼過程的跳躍表或等效的數據結構，是可能的。
在某些實施例中，在需要進行文檔重構之前，以壓縮的格式對小詞典208進行編碼，並且將其加以存儲。在一個實施例中，對每個小詞典208中所分類的GTokenID列表進行Delta編碼，然後按壓縮的格式，較佳的做法是按有助於對小詞典的快速與有效的解碼和重構的格式，對所得到的Delta值的列表進行編碼。2004年8月13日提出的、序號為10/917,745的、名為「System andMethod for Encoding and Decoding Variable-Length Data」(「用於對可變長度數據進行編碼和解碼的系統和方法」)的待審美國專利申請中，描述了一種適當的數據結構和編碼/解碼方法。
為了對特定文檔進行解壓縮，把與該文檔的記號位置範圍相關的小詞典208解壓縮成把LTokenID轉換成相應GTokenID的轉換表或根據小詞典208的條目所編制(build)的映射。於是，可以通過讀取存儲在針對該文檔的記號空間資料庫112中的固定長度的LTokenID，以及訪問該文檔中針對每個記號位置的小詞典以便把LTokenID轉換成相應的GTokenID，來完成對記號空間資料庫112中的記號化的文檔的解碼。然後，使用全局詞典206把GTokenID映射成相應的記號(例如，文本和標點)，從而重構了整個文檔或文檔的某一部分。
編碼系統圖3A為對記號空間資料庫的文檔進行編碼的編碼系統300的實施例的方框圖。編碼系統300包括可選的前置處理器302、可選的Delta編碼器304以及可變長度數據編碼器306。例如，可變長度數據類型可以包括各種數據類型，但不局限於整數、字符串、浮點數、定點數等。可變長度數據包括，但不局限於文本、圖像、圖形、音頻樣本等。
在某些實施例中，前置處理器302接收信息的列表，該前置處理器為了進行有效編碼對信息進行排序。前置處理器302可以使用一種或多種分類算法，把數據排序為單調序列。例如，如果根據值對整數集合進行分類，則就大小而言相鄰的整數將互相靠近，於是，可以使Delta編碼器304生成用於編碼的、為小數值整數的Delta值。Delta編碼器304接收排序的數據，Delta編碼器304計算排序的數據的相鄰對兒之間的差，以得到小數值的整數。可變長度數據編碼器306接收小數值的整數，並且把這些數據編碼為一種可以有效加以解碼的壓縮格式。2004年8月13日提出的、序號為10/917,745的、名為「System and Method for Encoding and Decoding Variable-Length Data」的待審美國專利申請中，描述了適當的可變長度數據編碼器306的一個例子。
可以使用編碼系統300的全部或一部分，對文檔處理系統102所生成的各種信息進行編碼。在某些實施例中，使用前置處理器302對每個小詞典208中的GTokenID進行分類，以確保將對大小上最接近的整數值進行Delta編碼。然後，由Delta編碼器304對所排序的GTokenID進行Delta編碼，以提供差值或餘值。然後，使用可變長度數據編碼器306，按組(例如，4個值的組)把差值編碼為一個壓縮格式。在某些實施例中，按一個逆索引，對記號位置的列表進行類似的編碼，以有助於對位置的快速與有效的解碼，如參照圖4更全面加以描述的。
儘管可變長度數據編碼器306提供了一種有助於快速和有效解碼的壓縮的格式，但也可以把其它已知的編碼方案用於文檔處理系統102，以壓縮信息的列表(例如，CCITT-G4、LZW等)。
解碼系統圖3B為對記號空間資料庫中的文檔進行解碼的解碼系統308的實施例的方框圖。解碼系統308包括可變長度數據解碼器310和可選的Delta解碼器312。在某些實施例中，由可變長度數據解碼器310接收所編碼的數據組，可變長度數據解碼器310藉助一個或多個位移/屏蔽表對各組進行解碼。Delta解碼器312接收所解碼的數據，Delta解碼器312計算運行和，從而產生Delta解碼的數據，這等效於原始的信息列表。2004年8月13日提出的、序號為10/917,745的、名為「System and Method for Encoding and DecodingVariable-Length Data」的待審美國專利申請中，更全面地描述了在對組編碼的可變長度整數值進行解碼的過程中對位移/屏蔽表的使用。
屬性編碼/解碼系統圖3C為用於對文檔屬性進行編碼/解碼的屬性編碼/解碼系統314的實施例的方框圖。屬性編碼/解碼系統314包括編碼/解碼系統320，編碼/解碼系統320把屬性信息322編碼為屬性記錄318，以存儲在屬性表316中。逐個記號地確定文檔的屬性，其中採用0或1的比特值來表示給定記號的每個屬性的存在或不存在。例如，可以把屬性表中的屬性記錄318概念性地表示為A×K個比特的映射，其中，A為所編碼的屬性的數目，K為其屬性由屬性記錄318表示的記號的數目。如果A為8，K為32，那麼每個屬性記錄318可以針對32個記號的每個存儲8個屬性。可以對每個屬性記錄318進行編碼，以壓縮屬性表所佔的空間量，同時能夠在查詢處理期間非常快地對所選擇的屬性記錄進行解碼。2004年8月13日提出的、序號為10/917,745的、名為「System and Method for Encoding and Decoding Variable-Length Data」的待審美國專利申請中，描述了一種用於對屬性記錄318進行編碼和解碼的適當的方法。作為選擇，也可以對每個屬性記錄中的信息進行運行長度編碼。
記錄在屬性表316中的屬性集合，可以包括一個或多個字體屬性(例如，粗體、下劃線等)、一個或多個文檔位置屬性(例如，題目、標題等)、元數據以及可用於對文檔集合中的記號之間加以區別的任何其它特性或特徵。在某些實施例中，在對記號化的文檔進行編碼，並且將它們存儲在記號空間資料庫中的同時，對文檔集合中的記號的屬性進行標識，並且對它們加以編碼，如以上所描述的。把所編碼的屬性用於一個或多個相關性得分的級別，如參照圖5更全面地加以描述的。
文檔資料庫編碼與解碼系統--第二實施例圖8A和8B為一個實施例的方框圖，其中，按與以上所描述的方式略有不同的方式對一組記號化的文檔(「記號空間資料庫」)進行編碼。如以上所描述的，全局詞典編制器202對文檔集合106進行記號化、標識所有唯一記號、以及把全局記號標識符賦予所有唯一記號。結果為全局詞典206。接下來，區域詞典編制器804處理該文檔集合(已被記號化)。概念地把文檔集合劃分為區域820，然後把每個區域820劃分成塊822。區域詞典編制器804針對每個區域編制「詞典」，即字典830，編碼系統810為每個區域生成被編碼的記號832的集合以及用於每個區域的塊位移834的集合。區域詞典830、編碼的記號832以及塊位移834(以下，將更詳細地對它們分別加以描述)，共同形成文檔集合的各個區域820的編碼表示法。
在一個實施例中，文檔集合被劃分成區域820，每個區域820(或許除了最後區域之外)具有預定的固定大小，諸如8192個記號(或任何其它適當的大小)。區域820的每個塊822也具有一個預定義的固定大小，諸如64個記號(或任何其它適當的大小)。
在一個實施例中，針對相應區域820的「詞典」830為具有最高重複率的最長記號序列的有序列表，或任何類似的結構。可以通過在所述區域中編制候選記號串的表，確定它們在所述區域中的重複次數，然後選擇最佳候選，直至達到最大詞典大小，編制詞典830。在示例性實施例中，最大詞典大小為64個記號，然而，在其它實施例中，也可以使用任何其它適當的大小限制。如以下將加以描述的，詞典830用作對相應區域820的每個塊822進行編碼的上下文，從而能夠高度壓縮區域的表示。在某些實施例中，可以按一種壓縮的格式對一個或多個區域詞典830進行編碼，例如，使用本文獻中先前所參照的2004年8月13日提出的、序號為10/917,745的、名為「System andMethod for Encoding and Decoding Variable-Length Data」的美國專利申請中所描述的編碼方法。
參照圖9A和9B，在一個實施例中，編碼系統810按如下方式對記號的每個塊822進行編碼。把針對相應區域的詞典830作為緊在所述塊的記號之前的一個記號集合加以對待。從第一個到最後一個，順序地處理所述塊的記號，把每個記號，並且儘可能多地把相繼的記號與先前記號序列中的最長匹配記號序列，包括區域詞典830，相匹配。如果發現匹配的先前序列，則生成「拷貝代碼」。否則，生成「文字代碼」，以表示記號。然後把當前代碼所覆蓋的所有記號作為先前記號加以對待，以用於塊中下一個記號(如果存在的話)的相繼處理。如圖9B中所示，每個代表塊中的記號集合的「代碼」可以包括一個類型欄位902。如果代碼為「文字代碼」，則代碼的第二部分904代表全局記號標識符。在某些實施例中，這一類型欄位902表示代表全局記號標識符所需的比特的數目。例如，在一個實施例中，類型代碼902可以最多表示7種不同的文字代碼，每個種都具有相應的全局記號標識符長度。在其它一些實施例中，不同類型代碼的數目可以多於或少於8個(例如，一個表示拷貝代碼，其餘的表示文字代碼)。如果文字代碼為「拷貝代碼」，則代碼的第二部分906可以包括指針908和長度910，其中，指針908指出從先前文本的哪一個地方開始，長度910指出匹配的序列的長度(即，在解碼期間將加以拷貝的記號的數目)。於是，比如，如果編碼系統810發現了4個從當前位置之前的31個記號的部位開始的記號的一個匹配序列，則針對這一序列的代碼將為type＝copy，ptr＝31，length＝4
拷貝代碼的長度(按比特加以測量)將依賴於區域詞典830的最大記號長度和塊的最大記號長度、匹配的序列的最大允許長度、以及不同代碼的數目。在一個例子中，類型欄位902為3個比特(允許8個類型代碼)、指針欄位908為7個比特，以及長度欄位910為2個比特，總共12個比特。在其它一些實施例中，也可以使用針對拷貝代碼的每個欄位的其它比特長度。由文字代碼的類型指出每個文字代碼的長度(按比特加以測量)。
回過頭來參照圖8B，當編碼系統810對區域的塊進行編碼時，編碼系統810生成指示針對該區域的每個塊的編碼的記號的部位的塊位移834的集合。在一個實施例中，該區域的第一個塊的塊位移為進入記號空間資料庫的指針，而且針對該區域的每個其它塊位移為相對該區域中的第一塊的開始位置的相對位移。在一個實施例中，把區域詞典830和塊位移834存儲在根據按固定區域大小所劃分的區域820的開始位置加以索引的表或等效的數據結構中。從另一個角度來看，向每個區域820賦予了區域號碼，該區域號碼包括其按固定區域大小所劃分的開始位置，並且按區域號碼對其中存儲了區域詞典830和塊位移834的一個或多個數據結構加以索引。
通過對相應區域的區域詞典830的定位，使用針對區域820的塊位移834對編碼的塊進行定位，然後對針對所述塊的代碼集合進行解碼，以產生全局記號標識符的序列，實現對該區域的塊822的解碼。接下來，可以使用全局詞典206，把所得到的全局記號標識符的序列或其任何子集轉換成相應的符號或項集合。
查詢處理系統圖4為用於記號空間資料庫的查詢處理系統104的第一級的實施例的方框圖。查詢處理系統104包括全局詞典402、記號空間逆索引408、第一級查找表406以及第二級查找表410。全局詞典402接收查詢項或串，全局詞典402使用根據全局詞典402的條目所編制的表或映射，把查詢項轉換成GTokenID。逆索引408接收GTokenID，逆索引408包括映射404，映射404把GTokenID映射到存儲在逆索引408中的索引記錄412。使用映射404所標識的每個索引記錄412包括記號位置的列表，該列表直接對應於記號空間資料庫112中的記號位置。在某些實施例中，在生成全局詞典之後，生成逆索引408，並且可以在與用於生成小詞典而遍歷文檔的同一遍期間，生成逆索引408。
在某些實施例中，逆索引408提供了位置列表，該位置列表可用作進入第一級查找表406的索引。當查詢包含多個項時，逆索引408產生多個位置列表。為了避免必須針對相應於一個或多個位置列表中的每個位置的一個條目搜索整個DocID映象圖410，第一級查找表406具有針對記號空間資料庫中每個位置塊的條目。例如，每個塊可以具有32768個位置的大小，而且每個條目可以具有指向針對相應位置塊的DocID查找表410中的第一條目的指針。於是，第一級查找表406可以把一個或多個位置列錶轉換成第二級查找表410中的文檔標識符(DocID條目)412的開始點位置。作為選擇，也可以把表406和410統稱為DocID查找表。第二級查找表410中的每個條目412包括DocID(文檔標識符)以及相應文檔的開始資料庫位置。在第二級查找表410中，任何文檔中的最後一個記號均處於緊在下一個標目412所標識的開始位置之前的位置。第二級查找表410接收針對DocID的開始點位置Start_PosA-Z，第二級查找表410把開始點位置轉換成針對每個查詢項的一個DocID的列表。
在某些實施例中，第一級查詢處理器416包括用於產生結果集合的邏輯416。邏輯416根據查詢或查詢樹所指定的布爾邏輯合併DocID的列表，以形成DocID的結果集合。邏輯416還可以有選擇地過濾記號位置的列表，以消除沒有位於相應於結果集合中的DocID的文檔中的記號位置。而且，還可以使用DocID的所標識的每個文檔中的DocID和記號位置，將記分功能施加到結果集合，以使得得分(有時將其稱為查詢得分)與結果集合中的每個DocID相關聯。
多級查詢處理圖5為利用記號空間資料庫524的多級查詢處理系統500的實施例的方框圖。在某些實施例中，查詢處理系統500包括4個查詢處理和相關性得分生成級，即包括第一級查詢處理器510、第二級查詢處理器514、第三級查詢處理器518以及第四查詢級處理器520。注意，在系統500中，可以使用或多或少的查詢處理器級，取決於具體的應用。根據應用場合，每級計算一個或多個可以返回給用戶的相關性得分集合與/或把它們與先前級中所生成的相關性得分加以組合。
查詢處理--級1已針對圖4一般性地描述了第一級查詢處理器510。查詢解析器504對查詢串502進行記號化，並且將其解析成查詢項(即，把查詢中的每個不同的項作為記號加以對待)。記號化的查詢項被全局詞典映射508使用轉換表或映射轉換成相應的GTokenID，如先前參照圖2和4所描述的。由於用戶可以在他們的查詢串中使用特定的操作符(operator)，包括布爾、鄰接、或相近性操作符，所以系統500可以將查詢解析成查詢項和操作符。操作符可以按特定化格式(例如，AND、OR)，以保留的標點(例如，問號)或者保留的項(term)的形式出現。在自然語言處理(NLP)系統的情況下，無論可以如何表達操作符，都能夠在所使用的語言中隱含地識別操作符(例如，介詞、連接詞、次序關係等)。第一級查詢處理器510中也可以包括其它的查詢處理，例如刪除結束單詞(例如「a」、「the」等)以及項幹(即，去除單詞前綴)。
接下來，查詢擴展器506處理GTokenID的列表，查詢擴展器506生成查詢樹或其它的查詢表示，並且考慮到查詢串中所使用的任何操作符(例如布爾表達式)。作為選擇，查詢擴展器506還可以按各種方式擴展查詢。例如，可以把查詢項轉換成子樹，該子樹包含所述項和一個或多個同義詞項，或者與查詢項相關的其它項，子樹中的項通過OR操作符或者父結點而彼此相關。
如以下將更詳細地加以描述的，在某些實施例中，根據圖5中所示的查詢處理級的序列，一次或多次地處理查詢。在每個遍(除最後一遍)中，生成附加查詢擴展項(以下將對此加以解釋)，然後，把這些附加項添加到查詢樹。也可以把查詢樹用作記分樹，記分樹具有與查詢樹中的項相關的權重。所擴展的查詢樹還可以包括不要求出現在相應於查詢的文檔中，但將它們用於對相應於查詢的文檔的相關性的記分的補充的項和項的子樹。如果存在一個以上的查詢項，則在第一遍期間，可以針對查詢項計算權重，以改進搜索結果。
在某些實施例中，遍歷系統500的第一遍處理來自文檔集的文檔的隨機樣本。可以根據能夠由系統500使用的一個或多個較小的隨機樣本，選擇隨機樣本的大小，以估計整個文檔集中匹配查詢的文檔的數目。在其它一些實施例中，在遍歷系統500的第一遍中，使用第一文檔集(例如，查詢對話期的一個集合)，以及在遍歷系統500的第二或相繼的遍，使用第二、不同的文檔集。使用先前的查詢對話期集合，可以使系統500能夠確定通常共同出現在類似查詢中的其它相關的項。查詢擴展器506可以使用這些相關項擴展相繼各遍的查詢。
第一級查詢處理器510使用查詢項搜索一個記號空間逆索引512，並且標識與查詢相匹配的文檔。第一級查詢處理器510訪問記號空間逆索引512，以產生查詢樹中項的記號位置(也稱為記號空間資料庫位置)的列表，並且訪問DocID映象圖516，以產生針對相應於記號位置的文檔的DocID的集合。另外，第一級處理器510還執行由查詢或查詢樹所指出的布爾邏輯，以生成相應於查詢的DocID的集合。在某些實施例中，第一級查詢處理器510還根據一個或多個記分算法，計算查詢和每個文檔之間的相關性得分的第一集合S1。總之，記分算法根據一個或多個查詢特性向每個匹配的文檔提供相關性，所述查詢特性包括，但不局限於一個或多個查詢項的存在或不存在、項頻度、布爾邏輯實現、查詢項權重、文檔的流行性(例如，一個獨立於文檔的重要性、或流行性、或互連性的得分)、查詢項相互間的相近性、上下文、屬性等。在一個實施例中，相關性得分S1的第一集合基於包括查詢項的存在性、項頻度以及文檔流行性的一組因素。
在某些實施例中，相關性得分的第一集合S1可用於選擇作為有序列表呈現給用戶的文檔，然後，用戶可以簡單地點擊和跟隨指向所選擇的文檔的內部指針。在其它一些實施例中，把相關性得分的第一集合S1以及DocID和相應的位置提供於第二級查詢處理器514，以進行進一步的處理。
查詢處理--級2第二級查詢處理器514從第一級查詢處理器510接收DocID的集合、針對相應文檔的記號空間資料庫位置的列表、以及相關性得分的第一集合S1。第二級查詢處理器514使用所述位置列表，根據文檔中所發現的查詢項的相近性或相對位置，生成相關性得分的第二集合S2。當在一個文檔中，查詢中的項相互靠近地出現時，與各項按較大距離出現時相比，所述文檔更可能與所述查詢相關。因此，與其中項按某一距離出現的文檔相比，如果查詢項互相相鄰地出現，即相近地出現，則相關性得分的第二集合S2被用於將文檔的等級排得較高。在某些實施例中，相關性得分的第二集合S2可用於選擇作為有序列表用於呈現給用戶的頂部的X文檔，然後，用戶可以簡單地點擊和跟隨指向所選擇的文檔的內部指針。在某些實施例中，部分地根據相關性得分的第一集合S1導出相關性得分的第二集合S2(例如，通過根據第二級查詢處理器514所使用的附加的得分因素，調整S1得分)，以生成一個向用戶提交的、與/或由第三級查詢處理器518進一步處理的文檔的有序列表。
查詢處理--級3在某些實施例中，把第二級查詢處理器514耦接於第三級查詢處理器518，以處理已經在一個屬性表522中加以編碼的項屬性(例如字體屬性、題目、標題、元數據等)，如以上參照圖3C所描述的。第三級查詢處理器518從第二級查詢處理器514接收DocID的集合、針對相應文檔的記號空間資料庫位置的列表，以及相關性得分的第二集合S2。作為選擇，第三級查詢處理器也可以接收相關性得分的第一集合S1以及相關性得分的第二集合S2。
某些研究表明，文檔中的項的部位表示其對文檔的重要性。例如，在權重方面，出現在與某一查詢相匹配的文檔的題目中的項，可能重於出現在該文檔的體中的查詢項。相類似，出現在章節標題或文檔第一段中的查詢項與出現在文檔中的不太重要位置中的項相比，很可能更能說明文檔與所述查詢的相關性。可以用於指示相關性的其它屬性包括粗體文本、下劃線文本以及字體大小。因此，使用與所述查詢項相匹配的文檔中的記號的屬性，確定相關性得分的第三集合S3。參照圖3C，為了訪問文檔中的查詢項的屬性(即，與查詢項相匹配或相關聯的記號的屬性)，使用該文檔中的查詢項的記號位置，執行進入屬性表316(圖5中的522)的索引操作。更具體地講，如果由每個屬性記錄318對其屬性進行編碼的記號的數目為K，則把除以K的記號位置用於進入屬性表316的索引。在某些實施例中，把所標識的屬性一個或多個記錄318以編碼的、壓縮的格式加以存儲，因此，為了確定與每個查詢項相關的屬性，必須對其進行解碼。
在某些實施例中，相關性得分的第三集合S3可用於選擇作為有序列表向用戶提交的頂部的Y個文檔，然後，用戶可以簡單地點擊和跟隨指向所選擇的文檔的內部指針。在某些實施例中，部分地根據一個或多個相關性得分的第一和第二集合S1和S2導出相關性得分的第三集合S3，以生成呈現給用戶的、與/或由第四查詢級處理器520進一步處理的文檔的有序列表。在某些實施例中，通過根據第三級查詢處理器518所產生的附加的得分因素，調整S2得分，產生S3得分。
查詢處理--級4第四查詢級處理器520從第三級查詢處理器518接收DocID的集合、相應於所述DocID的文檔中的位置的列表、以及相關性得分的第三集合S3。第四查詢級處理器520還可以有選擇地接收相關性得分的第一與/或第二集合S1和S2。第四查詢級處理器520耦接於解碼系統527，接著解碼系統527耦接於一個或多個小詞典映射523、記號空間資料庫524以及一個或多個全局詞典映射508。以上，針對圖1和圖2，描述了小詞典映射523、記號空間資料庫524以及全局詞典映射508。
第四查詢級處理器520根據上下文生成相關性得分的第四集合S4，並且還可以為結果集合中所列的一個或多個文檔生成「片段」。片段來自文檔的小部分文本，通常包括出現在將加以搜索的關鍵字周圍的文本。在一個實施例中，為了生成針對結果集合中所列的文檔的片段，查詢處理器對位於出現在文檔中的每個查詢項第一次出現之前和之後的預確定數目的記號進行解碼，從而重構了文檔的一個或多個文本部分，然後選擇將包括在片段中的文本部分的子集。使用結果集合中的位置列表，解碼系統527可以選擇對文檔的一些部分進行解碼所需的小詞典523，其中文檔的所述一些部分為文檔中查詢項出現之前和之後的一些部分。所選擇的小詞典523和全局詞典508用於把記號空間資料庫中的LTokenID轉換成GTokenID，然後用於把GTokenID轉換成記號，如以上針對圖2所描述的。
在某些實施例中，相關性得分的第四集合S4可用於選擇作為有序列表向用戶提交的頂部的Z個文檔，然後，用戶可以簡單地點擊和跟隨指向所選擇的文檔的內部指針。在某些實施例中，部分地根據一個或多個相關性得分的第一、第二以及第三集合S1、S2以及S3導出相關性得分的第四集合S4，以生成向用戶提交的、與/或由相關性反饋模塊517進一步加以處理的文檔的有序列表。在一個可選的實施例中，最後級查詢處理器為那些在先前查詢處理器級所產生的相關性得分方面具有最高得分的文檔生成片段，但不生成相關性得分的一個新的集合S4。
在某些實施例中，把相關性得分的最終集合提供於一個相關性反饋模塊517，相關性反饋模塊517根據最後查詢級所產生的結果集合中的文檔，生成一個或多個新的查詢擴展項。例如，相關性反饋模塊517可以實現一個或多個已知的相關性反饋算法，包括，但不局限於基於一個全文檔方案的偽相關性反饋算法(基於某一完整Web頁的偽相關性反饋算法)，文檔對象模型(DOM)分段、基於頁分段的顯示(VIPS)、使用概念點陣的概念相關反饋等。相關性反饋算法可以分析根據先前查詢處理級所核實(vet)的文檔，並且可以根據分析結果生成查詢擴展項。把新的查詢擴展項提供於查詢擴展器506，查詢擴展器506生成將由一個或多個查詢處理器510、514、518以及520所處理的新的查詢表達式。於是，多級查詢處理系統500能夠針對一個查詢執行兩遍或兩遍以上，並且使用來自每個遍的信息，生成改進了的查詢，從而將最終致使用戶可以接收更多相關的文檔。
在一個實施例中，當執行查詢的第一遍處理時，最後查詢級處理器520產生一些長的片段，例如包括文檔中查詢項每次出現之前和之後的N個(例如10～40個)記號。如果片段超過一個預先定義的長度，則可以截斷該片段。把查詢和最後查詢級520所產生的片段與相關性得分一起提供於相關性反饋模塊517，以生成查詢擴展項的集合，而且作為選擇，也可生成查詢項權重的集合。在擴展的查詢的第二遍處理期間，最後查詢級520產生一些長度適當的短的片段，以及用於隨具有最高，即最佳得分的結果集合中的文檔列表一起顯示的內容。
在一個實施例中，查詢處理系統包括L個並行的查詢處理子系統，每個查詢處理子系統包括針對一組文檔的相應子集的逆索引512和記號空間資料庫524。例如，查詢處理系統可以包括1000多個並行查詢處理子系統。所有查詢處理子系統可以共享相關性反饋模塊517(圖5)。在遍歷查詢處理系統的第一遍期間，由並行查詢處理子系統的一小部分處理查詢，而在第二遍期間，由整個查詢處理系統處理查詢。例如，可以把查詢處理系統劃分成S個子集(例如32個子集)，並且根據把雜湊函數施加到查詢的正常化的版本的結果，把每個查詢賦予這些子集之一，然後把取模函數施加到雜湊函數所產生的結果。可以把查詢處理系統的每個子集稱為查詢處理系統的「分區」，並且可以把每個查詢處理子系統稱為「子分區」。
查詢的第一遍處理的主要目的是，產生查詢擴展項的集合，以及查詢項權重，以改進由查詢的第二遍處理所產生的查詢結果的質量。只要在查詢處理系統中把文檔適當、隨機地在所有查詢處理子系統之間加以分布，則查詢僅需少數子系統加以處理，就可以產生查詢擴展項的一個集合。查詢擴展器506使用查詢擴展項產生擴展的查詢樹或查詢表達式，然後由查詢處理級(在查詢的一個第二遍處理中)對它們加以處理，如以上所描述的。例如，可以把查詢「紐約的照片」擴展為「紐約(照片或圖像，或者圖像或照片)」。可以對第二遍期間最後查詢級所產生的結果集合和片段進行格式化，以由從其處接收查詢的計算機或設備加以顯示(或者更一般地講，加以提交)。
在一個實施例中，在與相繼遍不同的數據資料庫上執行查詢的第一遍處理。例如，針對第一遍的初始數據資料庫，可以為先前處理過的查詢的一個數據資料庫，而用於相繼遍的數據資料庫可以為具有用於把查詢映射到該數據資料庫中的文檔的一個逆索引的文檔集合。
文檔處理伺服器圖6為記號空間資料庫伺服器600的實施例的方框圖。伺服器600可以為獨立的計算機系統或是包括多個計算機系統的分布式處理系統的一部分。通常，伺服器600包括一個或多個處理單元(CPU)604、一個或多個網絡或其它通信接口608、存儲器602、以及用於互連這些部件的一條或多條通信總線606。伺服器600可以有選擇地包括用戶接口，例如，顯示器和鍵盤。存儲器602可以包括高速隨機存取存儲器，還可以包括非易失存儲器，例如一個或多個磁碟存儲設備。存儲器602可以包括遠離一個或多個中央處理器604的海量存儲器。
存儲器602存儲作業系統610(例如，Linux或者Unix)、網絡通信模塊612、詞典生成器614(例如詞典生成器108)、編碼系統616(例如，編碼系統300)、一個或多個全局詞典618(例如，全局詞典206)、一個或多個小詞典620(例如，小詞典208)、記號空間資料庫622(例如，記號空間資料庫112)、屬性記錄624(例如，屬性記錄表316)、以及有效範圍映射626(例如，有效範圍映射210)。以上已經針對圖1～5描述了這些部件中每個部件的操作。
查詢處理伺服器圖7為查詢處理伺服器700的實施例的方框圖。伺服器700可以為獨立的計算機系統或為包括多個計算機系統的分布式處理系統的一部分。通常，伺服器700包括一個或多個處理單元(CPU)704、一個或多個網絡或其它通信接口708、存儲器702、用於互連這些部件的一條或多條通信總線706。伺服器700可以有選擇地包括用戶接口，例如，顯示器和鍵盤。存儲器702可以包括高速隨機存取存儲器，還可以包括非易失存儲器，例如一個或多個磁碟存儲設備。存儲器702可以包括遠離一個或多個中央處理器704的海量存儲器。
存儲器702存儲作業系統710(例如，Linux或者Unix)、網絡通信模塊712、記號空間逆索引714(例如，記號空間逆索引408)、解碼系統716(例如，解碼系統308)、一個或多個詞典轉換表或映射718(例如，從全局詞典206和小詞典小詞典208所導出的)、有效範圍映射720(例如，有效範圍映射210)、DocID映射722(例如，DocID映射410)、查詢解析器724(例如，查詢解析器504)、查詢樹726、一個或多個查詢處理器728(例如，查詢處理器510、514、518以及520)、屬性記錄730(例如，屬性記錄表316)、以及記號空間資料庫732(例如，記號空間資料庫112)。以上已經針對圖1～5描述了這些部件中每個部件的操作。
已參照具體的實施例，解釋性地進行以上的描述。然而，這些說明性的討論，不旨在窮舉性地描述本發明，也不旨在把本發明限制於所公開的精確形式。鑑於以上的描述，對本發明的許多修改與改變是可能的。這些實施例的選擇與描述，旨在充分地解釋本發明的原理及其實際的應用，從而可使這一技術領域中的其他熟練技術人員能夠對本發明和不同的實施例進行多方面的修改，以適應所考慮的具體應用，從而可充分利用本發明和不同的實施例。
權利要求
1.一種用於在多級查詢處理系統中處理查詢的方法，包括響應一個或多個查詢項，從索引檢索第一文檔標識符集合；針對相應於第一文檔標識符集合的至少一個子集的壓縮文檔集合，生成相關性得分的第一集合；解壓縮所述壓縮文檔集合的至少一部分，以恢復第一記號集合，其中，所恢復的第一記號集合與所述相應於第一文檔標識符集合的壓縮文檔集合中的位置相關聯；以及根據所恢復的記號集合的第一集合，生成附加查詢項；使用所述附加查詢項，制定新查詢；以及處理所述新查詢，以從所述索引檢索第二文檔標識符集合，並且至少部分基於所述附加查詢項生成相關性得分的第二集合。
2.根據權利要求1所述的方法，還包括解壓縮所述壓縮文檔集合的至少一部分，以恢復第二記號集合，其中，所恢復的第二記號集合與所述相應於第二文檔標識符集合的壓縮文檔集合中的位置相關聯；以及使用所恢復的第二記號集合，重構所述壓縮文檔集合的一個或多個部分。
3.根據權利要求1所述的方法，還包括把所重構的部分隨至少部分地基於所述相關性得分的第二集合從所述壓縮文檔集合中選擇的文檔的有序列表一起呈現給用戶。
4.根據權利要求1所述的方法，其中，所述相關性得分的第二集合基於相應於第二文檔標識符集合的所述壓縮文檔集合中的查詢項的一個或多個位置。
5.根據權利要求1所述的方法，其中，所述相關性得分的第二集合基於相應於第二文檔標識符集合的所述壓縮文檔集合中查詢項之間的距離。
6.根據權利要求3所述的方法，其中，所述相關性得分的第二集合基於其中在相應於第二文檔標識符集合的所述壓縮文檔集合中使用查詢項的上下文。
7.一種在多級查詢處理系統中處理查詢的方法，包括響應一個或多個查詢項，檢索第一信息集合；根據第一信息集合，生成至少一個附加查詢項；使用所述至少一個附加查詢項，制定新查詢，該新查詢具有多個查詢項；以及處理所述新查詢，從索引檢索文檔標識符集合；針對相應於所述文檔標識符集合的至少一個子集的壓縮文檔集合，生成相關性得分集合；解壓縮所述壓縮文檔集合的至少一部分，以恢復記號集合，其中，所恢復的記號集合與相應於所述文檔標識符集合的所述壓縮文檔集合中的所述多個查詢項的一個或多個查詢項的位置相關聯；以及根據所述文檔標識符集合的至少一部分，生成文檔列表，該列表包括相應於所恢復的記號集合的至少一部分的信息。
8.一種其上存儲指令的計算機可讀介質，當多級查詢處理系統中的處理器執行所述指令時，導致處理器執行下列操作響應一個或多個查詢項，從索引檢索第一文檔標識符集合；針對相應於第一文檔標識符集合的至少一個子集的壓縮文檔集合，生成相關性得分的第一集合；解壓縮所述壓縮文檔集合的至少一部分，以恢復第一記號集合，其中，所恢復的第一記號集合與相應於第一文檔標識符集合的所述壓縮文檔集合中的位置相關聯；以及根據所恢復的記號集合的第一集合，生成附加查詢項；使用所述附加查詢項，制定新查詢；以及處理所述新查詢，以從所述索引檢索第二文檔標識符集合，並且至少部分基於所述附加查詢項生成相關性得分的第二集合。
9.一種多級查詢處理系統，包括用於響應一個或多個查詢項，從索引檢索第一文檔標識符集合的部件；用於針對相應於第一文檔標識符集合的至少一個子集的壓縮文檔集合，生成相關性得分的第一集合的部件；用於解壓縮所述壓縮文檔集合的至少一部分，以恢復第一記號集合的部件，其中，所恢復的第一記號集合與相應於第一文檔標識符集合的所述壓縮文檔集合中的位置相關聯；以及用於根據所恢復的記號集合的第一集合，生成附加查詢項的部件；用於使用所述附加查詢項，制定新查詢的部件；以及用於處理所述新查詢，從所述索引檢索第二文檔標識符集合，並且至少部分基於所述附加查詢項生成相關性得分的第二集合的部件。
全文摘要
一種多級查詢處理系統與方法，該多級查詢處理系統與方法通過一個多層映射方案所簡化的遞增的文檔重構，允許多級查詢記分，包括「片段」生成。在多級查詢處理系統的一個或多個級，使用一個相關性得分集合，選擇作為一個有序列表向用戶提交的文檔的一個子集。可以部分地從多級查詢處理系統的先前級中所確定的相關性得分的一個或多個集合中導出相關性得分集合。在某些實施例中，多級查詢處理系統能夠一或多遍地執行一個用戶查詢，並且能夠使用來自每個遍的信息，擴展用戶查詢，以在相繼遍中用於改進有序列表中的文檔的相關性。
文檔編號G06F17/30GK101036143SQ200580034128
公開日2007年9月12日 申請日期2005年8月8日 優先權日2004年8月13日
發明者傑弗裡·A·迪安, 保羅·G·哈爾, 奧爾坎·瑟齊諾格魯, 阿米塔布·K·辛加爾 申請人:谷歌股份有限公司