索引實體的方法和系統的製作方法
2023-05-03 05:09:51 5
專利名稱：索引實體的方法和系統的製作方法
技術領域：
本發明的實施例總的來說涉及信息檢索系統，更具體地說，涉及用於在全文倒排表(full text inverted list)信息檢索系統中的數據搜索的技術。
背景技術：
分類體系(taxonomy)是對事物的分類。例如，大多數作業系統中的公知目錄結構是用於將單獨的文件組織成組的方法。在全文索引中，索引利用的是許多文檔共享相同的標記(token)(例如，單詞或字符)的事實。儘管每個獨特的標記在文檔的原始集合中會出現多次，但是倒排表索引通常僅將該標記存儲一次。因此，通常，可將倒排表索引看作壓縮文檔的集合的一種形式。典型地，壓縮率依賴於索引的範圍。通常，基本的倒排索引僅記錄某個項(term)是否出現在文檔之內，而並不記錄它出現了多少次或者它出現在哪裡。全倒排索引通常記錄每個標記在每個文檔之內的每次出現(occurrence)。儘管基本的倒排索引在存儲方面更加緊湊，但是它通常不能支持搜索標記的序列，或在標記的特定窗之內搜索標記的存在。然而，全倒排索引通常允許這樣的複雜搜索。在基本的倒排索引和全倒排索引之間，存在可以存儲在某個項的倒排表之內的各種級別的信息。
關於倒排表，一種最眾所周知的索引形式是書本中的索引。幾乎每本書都在書的末尾具有單詞或單詞序列(例如，段落和章節標題)的通常按字母順序排列的列表，連同論述它們的頁碼。使用索引，人們可避免為了找到包含特定單詞的頁面而逐頁地瀏覽。類似地，在例如網絡搜尋引擎的信息檢索應用的情況下的倒排表索引所作的也正是上述內容。抽象地來說，可將網絡看作一本書，各個網絡文檔代表書中的頁面。通過掃描要被索引的所有文檔並將它們分成標記來執行建立倒排表索引的處理。這一處理稱作分析(parsing)或標記化(tokenization)，它產生可以是英文文檔中的單詞、中文字符、4位元組數字等的標記。
對全文索引的查詢與所有查詢項的倒排表的交集/結合(取決於查詢操作符，例如，OR、AND)相同。因此，查詢結果本身是一個倒排表。對於查詢的每個項，通常必須訪問倒排表。數據挖掘(mining)的處理涉及從較大的數據集合中提取諸如模式、關係等信息。數據挖掘者(所謂的註解者)通常逐文檔地操作所述集合，並將元數據添加到所述集合。可將實體(entity)理解為人們用許多名稱或描述來引用的內容。實體可以是個人、機構、組織、建築或國家。所有這些具有的共同點在於可以用不同的語言、不同的名稱或別名、或者其名稱的變化的簡稱來描述同一個事物。因此，通常也可將實體表示為搜索查詢。
上述概念允許用戶搜索多個單詞或挖掘的實體。然而，通常這是不夠的。計算機用戶通常趨於想要把事物組織和集中到一起。這種例子包括使用用於集中相關文件的目錄或將電子郵件地址集中到一起的寄送列表的文件系統。基本的想法在於可通過引用單個別名(alias)(即，目錄名稱或寄送列表的名稱)對一組事物執行操作。
在搜索應用中，期望相似的功能。並不是搜索包含一組特定項的文檔，使用別名來索引和搜索所述組通常更加高效。例如，可使用單個的項「政治家」將文檔中出現的所有政治家的名字集中。這樣，人們可以高效地搜索文檔的集合，而不必單獨地列出所有政治家。當搜索一組事物時，其通常不僅有助於找到匹配所述組的文檔，還有助於了解組名稱的出現的背後「隱藏」著哪個實體。
針對這一問題的第一種傳統解決方案為通過分別查詢例如「政治家」的組中的每個政治家來查詢該組。然而，由於該組會包含數千、數百萬或者某些情況下數億的條目(例如，所有人名的組)，並且在這種情況下的處理速度會從幾分之一秒到數日，所以這通常是不可接受的。
第二種傳統解決方案為創建與該組相對應的新標記。然而，這種解決方案通常無法提供重要的功能。用戶知道結果集合中的文檔涉及政治家，但是並不知道涉及哪個政治家。對於特定的分析應用，這一方法也是不可接受的。關係資料庫是用於存儲關係數據的比較成熟的工具。在組中包含實體也是一種關係。然而，關係資料庫通常不適於建立大規模的文本索引。因此，需要一種新型的索引技術，其能夠找到包含屬於組的實體的文檔，並且能夠找出在組名稱的出現的背後「隱藏」著哪個實體。
發明內容
考慮到以上內容，本發明的實施例提供一種索引位於分類體系中的多個實體的方法，所述實體包括項(term)的集合。在另一實施例中，由計算機可讀的計算機存儲設備，有形地包含由計算機可執行的指令的程序，所述程序用於執行索引位於分類體系中的多個實體的方法，其中，該方法包括在索引結構中接收項；為實體建立關於項的位置以及與從索引結構接收的項關聯的數據的記錄列表(postinglist)；以及將組的名稱索引到實體的位置，組的數據包括實體的名稱。優選的是，建立記錄列表的處理包括將所述實體的位置以及與所述實體關聯的數據存儲在用於該組的記錄列表的條目中。此外，該方法還包括使用倒排表索引將數據與索引項的每次出現相關聯，並搜索倒排表索引以允許在文檔命中的集合中進行統計聚集，其中，統計聚集指示哪些單獨的實體存在於文檔集合中。此外，該方法還包括對於索引器找到的每個文檔提取某個項的所有出現的數據欄位。
本發明的另一方面提供一種索引位於分類體系中的多個實體的系統，所述實體包括項的集合，其中，該系統包括適於接收項的索引結構；以及它們各自的記錄列表，所述記錄列表包括項的位置和與每個位置有關的數據，其中，索引結構包括組的名稱和它的各個記錄列表，所述記錄列表包括組內的所有實體的位置，每個數據欄位包括每個位置的相應實體的名稱。優選的是，記錄列表適於將項的位置以及與項關聯的數據存儲在用於該項的記錄列表的條目中。該系統還包括適於將數據與索引項的每個出現相關聯的倒排表索引結構。此外，該系統還包括查詢機制，其適於搜索倒排表索引結構以允許在文檔命中的集合中進行統計聚集(aggregation)，其中，統計聚集指示哪些單獨的實體存在於文檔集合中。此外，該系統還包括索引器，適於對於該索引器找到的每個文檔提取某個項的所有出現的數據欄位。
當結合下面的描述以及附圖進行考慮時，將更好地認識和理解本發明的實施例的這些和其它方面。然而，應理解，以下描述在表示本發明的優選實施例以及其許多特定細節的同時，僅作為示例示出，而並不是限制性的。在不脫離本發明的精神的情況下，在本發明的實施例的範圍之內可進行各種改變和修改，本發明的實施例包括所有這樣的修改。
通過下面參照附圖進行的詳細描述，將更好地理解本發明的實施例，其中圖1是示出本發明實施例的優選方法的流程圖；圖2示出分類體系順序的示意圖；圖3是根據本發明實施例的系統圖；以及圖4是根據本發明實施例的計算機結構圖。
具體實施例方式
參照在附圖中示出並在下面的描述中詳細說明的非限制性實施例，將更加全面地解釋本發明的實施例及其各種特徵和有利細節。應注意到，並不一定按照比例來繪製附圖所示的特徵。將公知部件和處理技術的描述省略，以便避免不必要地模糊本發明的實施例。這裡使用的示例僅僅是為了有助於理解可實施本發明實施例的方式，並進而使得本領域的技術人員能夠實施本發明的實施例，因此，不應將示例解釋為限制本發明實施例的範圍。
如上所述，需要一種新型的索引技術，其能夠找到包含屬於組的實體的文檔，並且能夠找出在組名稱的出現的背後「隱藏」著哪個實體。本發明的實施例通過提供一種在大規模全文索引中支持索引和搜索分類體系的方法和構架來實現上述目的。更具體地說，本發明的實施例提供一種用於索引包括多個成員的集合的技術，其中，索引提供允許對引用所述集合的成員的文檔的順序訪問的數據結構，其中，以用於確定引用了哪個特定成員的信息來擴充所述數據結構。現在參照附圖，特別是圖1到圖4，其示出了本發明的優選實施例。
圖1示出索引位於分類體系中的多個實體的方法的流程圖，所述實體包括項的集合，其中，該方法包括在索引結構中接收項(101)；為實體建立關於項的集合的位置以及與項有關的數據的記錄列表(103)；以及索引包括組內的實體的位置的組的名稱，每個位置的數據包括每個位置的相應實體的名稱(105)。優選的是，記錄列表的建立(103)包括將項的位置以及與項關聯的數據存儲在該項的記錄列表的條目中。此外，該方法還包括使用倒排表索引將數據與索引項的每次出現相關聯；以及搜索倒排表索引以允許在文檔命中的集合中進行統計聚集，其中，統計聚集指示哪些單獨的實體存在於文檔集合中。此外，該方法還包括對於由索引器發現的每個文檔提取某個項的所有出現的數據欄位。
總地來說，本發明的實施例提供一種實現分類體系的積累(roll-up)的索引建立處理，即，當索引文檔中某位置上的特定實體時，將組的名稱用作索引項，直接或間接(通過子組)地索引包含所述實體的所有組。接著，本發明的實施體提出一種允許將數據與索引項的每次出現關聯的倒排表索引格式。此後，如以下進一步所描述的，本發明的實施例提供一種搜索倒排表以允許在文檔命中的集合中進行統計聚集並向用戶提供關於哪些實體存在於頁面上的信息的方法。
在分類體系中定義實體，即，實體是關於何種文本序列表示這種實體的出現的描述。在圖1中示出簡單的一個分類體系。可將單獨的實體集中成組，並可將組進一步集中，這類似於文件系統中目錄的概念。諸如可擴展標記語言(XML)的樹狀文檔結構允許分類體系的表示。當索引實體，代表實體的項(別名)，以及包含所述實體的組的所有別名的出現時，每個組別名的出現與實際實體的名稱關聯。搜索文檔可使用單詞、實體別名或實體組別名的任意組合。此外，可通過返回帶有組別名的出現信息的實體名稱來使用組別名的關聯數據注釋搜索結果。這是基礎索引的功能。本發明的實施例支持使用組中的項的關聯數據提供關於文檔命中的組的統計信息的應用。返回帶有組別名的數據的能力可用於基於文檔命中的集合聚集信息並收集統計。例如，查找包含任何人的文檔(使用該人的組別名)，可以根據「人」的出現的數據欄位選擇使所有個人連同文檔被返回。所述應用隨後可使用這一數據並對其進行聚集，並顯示n個最頻繁的個人。
此外，本發明的實施例提供使用組別名以基礎搜地索項的集合的能力，這簡化了查詢結構，減少了查詢長度和查詢之內項的數量。允許使用組別名將用戶從必須知道組之內的所有條目以便搜索組中的所有條目的情況中解脫出來。通常，查詢中的每個單獨的項需要項查找並可能需要盤尋找(disk-seek)。在這種情況下，當以多個項(例如，單詞)進行查詢時，「項查找」是找出該項是否存在於索引中，即，任何被索引的文檔是否包含該給定的項至少一次的處理。術語「盤尋找」指的是在例如硬碟的輔助存儲設備上執行的任何操作。在這種情況下，當之前從未看到某個項和它的倒排表並且需要從盤上加載它們時，有必要進行盤尋找。因為CPU和內部存儲器(RAM)以及CPU和例如硬碟的外部存儲器之間的速度差為多個數量級，所以在進行較大集合中的搜索時減少盤尋找是主要目的之一。通過減少項查找和盤尋找的數量，輸入/輸出(I/O)操作更加連續，這對於實時性能起到積極作用。
根據本發明的實施例，因為增長的集合被自動處理，所以簡化了查詢再使用。換言之，在下一索引建立中獲得對分類體系的更新，即，將新的人添加到人的組中。如果將一個成員添加到組，則自動將其索引為組的一部分並隨著索引更新來獲得所述成員。因此，當組成員發生改變的時候，使用組別名的查詢不需要改變。此外，根據本發明的實施例，利用每個記錄(posting)存儲數據允許對於由查詢返回的結果集合的僅索引(index-only)數據分析。如果人們僅知道某個人存在於頁面上以及存在於哪裡(單詞或字節偏移)，則不得不加載所有滿足查詢的文檔，並從所述頁面提取信息，以得到實際名稱。使得數據可通過索引獲得對於實時性能是有利的。利用使用本發明的實施例建立的索引，僅訪問一個記錄列表，可以對於匹配該查詢的任何文檔，返回分類體系中任何實體的所有出現。因為組的倒排表包括它的孩子的所有出現，所以上述處理可以實現。這實現了僅索引數據檢索，其在傳統的解決方案中通常需要包含文檔的元數據的外部數據存儲。如先前所述，檢索文檔、分析文檔和提取數據的傳統技術方案是在運行時間方面是不可行的。由本發明的實施例提供的好處能夠減少網絡或盤往返。
通常，本發明的實施例如下工作。首先，進行索引建立處理。這裡，索引處理檢索項(單詞、實體別名等)。優選的是，將所述索引具體化為文件的集合，所述文件存儲在例如硬碟的輔助存儲介質上。某個項的每個出現可以具有與其關聯的數據。對於每個獨特的項建立記錄列表。記錄的格式是[位置|數據]。對於分類體系中的項，建立處理進行以下操作(1)利用其在文檔中出現的位置x插入實體葉；(2)對於包含(直接或間接)所述實體的每個組，本發明的實施例將組的名稱索引到相同的位置x，並將實體別名的名稱置於數據欄位中。例如，假設存在兩個實體，JohnKerry和GeorgeBush，它們在美國政治家的組中，而該組又包含在組「人」中。假設實體JohnKerry出現在某文檔的位置x，而實體GeorgeBush出現在某文檔的位置y。索引建立處理產生三個別名(一個用於實體，兩個用於組名稱)的三個記錄列表，如表1所示
表1記錄列表
處理的下一步驟涉及查詢處理。這裡，使用上述方法建立的索引隨後可用於搜索包含任何組成員的出現的文檔。通過搜尋引擎來促進搜索，所述搜尋引擎使用索引來查找項並訪問所述項的倒排表。所述查詢引擎逐個查詢記錄列表的所有出現。索引包括文件的集合，所述文件包括所有項和它們各自的記錄列表，搜尋引擎確定項是否存在，然後使用索引文件中的信息以找到所述項的倒排表(記錄)。使用如任何作業系統中使用的傳統文件訪問方法從盤加載記錄。將分類體系之內的實體的記錄列表當作普通索引項，並且所述記錄列表可與例如頁面上的單詞的常規索引項進行組合。接著，進行查詢項的數據欄位的提取。這裡，當處理尋找包含項的集合的文檔的查詢時，索引器對於它找到的每個文檔返回某個項的所有出現信息。由於對於每個查詢項能夠逐個查詢所述記錄，所以搜尋引擎從每個記錄返回信息，其為文檔之內的位置以及關聯的數據。通過提取落入文檔的所有出現的所有數據欄位來實現上述處理。
圖3示出根據本發明實施例的系統框圖。索引位於分類體系內的包括項的集合的多個實體的系統200包括索引結構201，適於接收項；以及記錄列表203，包括項的位置和與項的每個位置關聯的數據；其中，索引結構201包括組的名稱和它的記錄列表203，其包括所述組之內所有實體的位置，以及包括在每個位置的各個實體名稱的每個數據欄位。優選的是，記錄列表203適於將項的位置和與項關聯的數據存儲在項的記錄列表203的條目中。系統200還可包括倒排表索引結構205，其適於將數據與索引項的每個出現關聯。此外，系統200還可包括查詢機制207，其適於搜索倒排表索引結構205以允許在文檔命中的集合中進行統計聚集，其中，統計聚集指示哪些單獨的實體存在於文檔集合中。此外，系統200還可包括索引器209，其適於對於由索引器209找到的每個文檔提取某個項的所有出現的數據欄位。
本發明的實施例可採用全部硬體實施例、全部軟體實施例或包括硬體和軟體部件兩者的實施例的形式。在優選實施例中，以軟體來實現本發明，所述軟體包括但不限於固件、駐留軟體、微代碼等。
此外，本發明的實施例可採用通過計算機可用或計算機可讀介質可訪問的電腦程式產品的形式，所述計算機產品提供程序代碼以由計算機或任何指令執行系統使用或結合計算機或任何指令執行系統使用。為了描述的目的，計算機可用或計算機可讀介質可以是任何可包括、存儲、通信、傳播或傳輸程序以由指令執行系統、裝置或設備使用或結合指令執行系統、裝置或設備使用的裝置。
介質可以是電、磁、光、電磁、紅外或半導體系統(或裝置或設備)或傳播介質。計算機可讀介質的示例包括半導體或固態存儲器、磁帶、可移動計算機磁碟、隨機存取存儲器(RAM)、只讀存儲器(ROM)、剛性磁碟和光碟。光碟的當前示例包括壓縮盤-只讀存儲器(CD-ROM)、壓縮盤-讀/寫(CD-R/W)和DVD。
適於存儲和/或執行程序代碼的數據處理系統將包括至少一個直接或間接通過系統總線連接到存儲部件的處理器。存儲部件可包括在程序代碼的實際執行期間使用的本地存儲器、海量存儲器、提供至少某些程序代碼的臨時存儲以便減少必須在執行期間從海量存儲器檢索代碼的次數的高速緩衝存儲器。
輸入/輸出(I/O)設備(包括但不限於鍵盤、顯示器、指引設備等)可直接或通過中間I/O控制器連接到系統。也可將網絡適配器連接到系統以使得數據處理系統能夠通過中間的私用或公共網絡連接到其它數據處理系統或遠程印表機或存儲設備。數據機、有線數據機和乙太網卡僅是一些當前可用的網絡適配器。
在圖4中示出用於實施本發明的實施例的代表性硬體環境。這一示意圖示出根據本發明的實施例的信息處理/計算機系統的硬體配置。所述系統包括至少一個處理器或中央處理單元(CPU)10。CPU 10通過系統總線12與諸如隨機訪問存儲器(RAM)14、只讀存儲器(ROM)16和輸入/輸出(I/O)適配器18的各種設備相互連接。I/O適配器18可連接到外圍設備，諸如盤單元11和帶驅動器13、或系統可讀的其它程序存儲設備。所述系統可讀取程序存儲設備上的本發明指令，依照這些指令以執行本發明的實施例的方法。所述系統還包括用戶接口適配器19，其將鍵盤15、滑鼠17、揚聲器24、麥克風22和/或諸如觸控螢幕設備(未示出)的其它用戶接口設備連接到總線12以收集用戶輸入。此外，通信適配器20將總線12連接到數據處理網絡25，顯示器適配器21將總線連接到顯示設備23，所述顯示設備23可具體化為諸如以監視器、印表機或發送器為例的輸出設備。
以上對於特定實施例的描述將充分揭示本發明的總體特性，從而其他人可在不脫離總體概念的情況下，通過應用當前知識容易地修改和/或改變這些特定實施例的各種應用，因此，這種改變和修改應該並試圖理解為在公開的實施例的等同物的含義和範圍之內。要理解到，這裡使用的措辭或術語是為了描述的目的，而不是限制性的。因此，儘管以優選實施例描述了本發明的實施例，但是本領域的技術人員將認識到，在實施本發明的實施例時可以在所附權利要求的精神和範圍之內進行修改。
權利要求
1.一種索引位於分類體系中的多個實體的方法，所述實體包括項的集合，所述方法包括在索引結構中接收所述項的集合；為實體建立關於所述項的集合的位置和與所述項的集合關聯的數據的記錄列表；以及索引包括位於所述項的集合的所述位置的所述實體的組的名稱，所述組的數據包括所述實體的名稱。
2.如權利要求1所述的方法，其中，記錄列表的建立包括將所述實體的所述位置以及與所述實體關聯的數據存儲在所述實體的所述記錄列表的條目中。
3.如權利要求1所述的方法，還包括使用倒排表索引將數據與索引項的每次出現相關聯。
4.如權利要求3所述的方法，還包括搜索所述倒排表索引以允許在文檔命中的集合中進行統計聚集，其中，所述統計聚集指示哪些單獨的實體存在於文檔集合中。
5.如權利要求1所述的方法，還包括對於由索引器找到的每個文檔提取某個項的所有出現的數據欄位。
6.一種計算機可讀的程序存儲設備，其有形地包含可由所述計算機執行的指令的程序，以執行索引位於分類體系中的多個實體的方法，所述實體包括項的集合，所述方法包括根據先前方法權利要求的任何一種方法。
7.一種索引位於分類體系中的多個實體的系統，所述實體包括項的集合，所述系統包括適於接收項的索引結構；以及關於所述項的位置以及與所述項關聯的數據的、包括實體的多個記錄列表，其中，所述索引結構包括組的名稱，其包括所述實體在組內的所述位置，所述組的數據包括所述實體的名稱。
8.如權利要求7所述的系統，其中，所述記錄列表適於將所述項的位置以及與所述項關聯的數據存儲在所述項的所述記錄列表的條目中。
9.如權利要求7所述的系統，還包括倒排表索引結構，適於將數據與索引項的每次出現相關聯。
10.如權利要求9所述的系統，還包括查詢機制，適於搜索所述倒排表索引結構以允許在文檔命中的集合中進行統計聚集，其中，所述統計聚集指示哪些單獨的實體存在於文檔集合中。
11.如權利要求7所述的系統，還包括索引器，適於對於由所述索引器找到的每個文檔提取某個項的所有出現的數據欄位。
全文摘要
一種索引位於分類體系中的多個實體的系統和方法，所述實體包括項的集合，所述方法包括在索引結構中接收項；為實體建立關於定義實體的項的集合的位置和與各個項關聯的數據的記錄列表；以及索引包括組內的位於實體位置的實體的組的名稱，所述組的數據包括在每個位置的各個實體的名稱。記錄列表的建立包括將項的位置以及與項關聯的數據存儲在該項的記錄列表的條目中。該方法包括索引包括所述項的組的名稱的別名，並使用倒排表索引以將數據與索引項的每個出現關聯。
文檔編號G06F17/30GK1940930SQ20061014134
公開日2007年4月4日 申請日期2006年9月29日 優先權日2005年9月30日
發明者喬爾格·梅爾, 簡·H.·派博, 丹尼爾·H.·梅裡蒂斯, 安德魯·S.·託姆金斯, 納達維·埃洛恩 申請人:國際商業機器公司