一種大規模數據搜索系統的製作方法

2023-04-29 17:00:46

專利名稱：一種大規模數據搜索系統的製作方法
技術領域：
本發明涉及搜尋引擎技術，尤其涉及一種大規模數據搜索系統。
背景技術：
眾所周知，搜尋引擎是用於從網際網路上搜尋信息的重要工具。隨著網際網路規模的不斷擴大和網上信息量的不斷增長，搜尋引擎的作用也就越來越重要。當前，網際網路上的搜尋引擎雖然大小不同，功能也各異，但它們都包含以下一些基本的功能模塊網頁收集模塊、頁面預處理模塊、索引模塊、頁面檢索模塊等。其中，可利用上述搜尋引擎的索引模塊生成倒排文件，被檢索模塊所使用。這裡，所述倒排文件是從關鍵詞到其出現位置(occurrence)的一種索引。對於搜尋引擎來說，關鍵詞的出現位置信息必須包括出現關鍵詞的文檔列表，以及關鍵詞在各文檔內的位置列表。一般而言，倒排文件由索引文件和記錄文件組成，索引文件每個記錄包含一個關鍵詞和一個指針，該指針指向記錄文件中存放關鍵詞信息的位置。其大致結構如圖 1所示，利用倒排文件，檢索系統可以快速的找到查詢詞對應的文檔列表。對由多個關鍵詞所組成的查詢，還可以根據各個詞在各個文檔中出現的位置，來計算查詢與文檔的相關度。 倒排索引是迄今為止發現的用於搜尋引擎最好的索引結構，既方便建立，又很好的支持各種查詢操作。在實際應用中的倒排文件遠比上圖的複雜為了更好的計算相關度，倒排文件中還要加入其它的一些信息，例如關鍵詞在文檔中的屬性信息；為了提高檢索效率，可能要調整倒排文件的結構，例如先存放出現關鍵詞的所有文檔列表，再存放所有的位置信息，把上圖中位置信息的形式變換為通過這種變換，當我們不關心詞在文檔中位置列表的時候，就可以一次地讀入詞對應的文檔列表，減少對外存的訪問次數。在後面我們還將詳細討論倒排文件的設計，我們會發現倒排文件結構的好壞直接影響檢索速度。現代搜尋引擎搜索的網頁都數量巨大，目前的北大天網(e. pku. edu. cn/)搜尋引擎搜索的網頁量就有1.2億，而一般的商業搜尋引擎搜索的網頁量至少都有數億，甚至是達到數十億。在這種情況下，一個單機的檢索系統顯然無法處理每秒成百上千的用戶查詢請求。此時，設計出一個結構良好的分布式檢索系統顯得尤為重要。一般成言，分布式檢索系統至少包括兩個部分一臺或多臺用於接收入用戶查詢請求的前臺伺服器，和多個用於實際數據檢索的後臺伺服器，其結構如圖2所示。當用戶在搜索框中填入一個查詢項，點擊搜索按鈕，其查詢請求就被隨機的發送到任意一臺前臺伺服器上。而前臺伺服器實際上並不保存網頁的索引信息，它將用戶的查詢通過廣播的方式發送到後臺的檢索機群上。後臺檢索機群中，每臺機器中都存放有部分網頁的倒排索引，當它收入到廣播過來的查詢，便在其索引中查找出與查詢其關的網頁，並根據一定的相關度算法計算出得分，把相關度最高的若干個網頁的文檔號與得分一起發送回前臺的伺服器。前臺伺服器收集幾個檢索機器上的結果，按得分歸併後把最相關的網頁返回給用戶。由於時間的關係本文必沒有詳細的研究檢索系統的分布式結構，而是更多的關注各個檢索節點上的效率。可以說，這兩方面共同決定了一個檢索系統的性能。但是，現在的大型搜索系統，仍然存在一些問題需要我們去改善，主要體現在如下幾個方面一、檢索效率不高。每個檢索節點檢索的網頁量大約在二百多萬，每秒只能處理十幾個的查詢請求。主要原因是沒有為倒排文件建立cache，每次查詢都要多次訪問外存，磁碟成了系統的瓶頸。此外，其分布式結構也不太好，前臺伺服器與檢索節之間基於同步的多進程的交互方式，也影響和整個系統的效率。二、倒排文件信息量不夠。現在的倒排文件中，關鍵詞在文檔中的屬性信息很少， 只用兩個bit分別表示詞是否在網頁title和摘要中，並且不能為關鍵詞在文檔中各個位置設立屬性信息。由於信息量的缺乏，在計算詞與文檔相關性的時候，往往不夠準確。三、系統的可擴展性和容錯性不足。系統現在運行在由一臺前臺伺服器，19個檢索節點構成的分布式環境中。對於增加檢索節點可能帶來的廣播風爆，以及增加前臺伺服器查詢策略的變化，都沒有考慮到。此外，數據沒有冗餘，當系統中部分機器出現故障，則會影響查詢結果。

發明內容
有鑑於此，本發明的主要目的在於提供一種大規模數據搜索系統，通過改進倒排文件結構、改進整數的壓縮算法，並增加倒排文件的信息量；能夠通過有效的cache策略， 讓索引儘量的在內存中可以找到，減少訪問磁碟的開銷；並通過一些有效的預處理，減少浮點運算的次數，也進一步的提高檢索效率。對於相關度計算，本文也做了一些改進，使得在最後的結果排序上更符合用戶需求。為達到上述目的，本發明的技術方案是這樣實現的一種大規模數據搜索系統，其主要包括倒排文件模塊、數據接口模塊、查詢模塊、 切詞模塊及記分函數模塊以及進程守護模塊，其中所述倒排文件模塊，用於搜索系統能夠快速找到查詢詞對應的文檔列表；所述數據接口模塊，是一組接口類，封裝了每個要公開的數據的訪問方法；所述查詢模塊，用於利用輸入端查詢條件進行搜索，將各個關鍵詞對應文檔列表求交集；所述切詞模塊，用於切詞並得到各個關鍵詞並形成一棵查詢樹；所述記分函數模塊，負責進行站點聚類，得到聚類好的查詢結果，排列並返回給守護進程模塊；以及，所述守護進程模塊，用於接受查詢請求，並根據查詢請求中指定的最大返回結果數，將部分結果返回。其中，所述倒排文件模塊，採用新的倒排文件格式，其包含描述文件、索引文件和記錄文件，支持程序的快速訪問。所述倒排文件模塊的描述文件，包括倒排文件自身的屬性信息，包括Byte-Order屬性表示倒排文件中使用整數的字節序，包含壓縮整數和非壓縮整數；Align-Bits屬性使用了 32位的偏移量，Align-bits屬性表示移動的位數；Attr-Size屬性在這個格式中，允許關鍵詞在每個出現它的文檔中，有0個或多個字節的屬性信息；這個屬性信息的意義在本格式中無定義，完全由應用程式決定； 該屬性信息必須是整字節的，並且所有的屬性信息必須等長；這個長度就是倒排文件的 Attr-size 屬性；Uint-Encoding屬性壓縮整數的編碼方式。本發明所提供的大規模數據搜索系統，具有以下優點通過定義新的倒排文件格式，其支持程序的快速訪問。改進了整數壓縮算法，使得倒排文件的規模變小，從而也就減少了檢索時從磁碟讀取的數據量。通過使用文檔列表cache，減少對磁碟的訪問次數。通過預先計算相關度，完全消除了檢索過程中的浮點運算，節省了 CPU計算時間，但代價是增大了倒排文件規模。充分的利用關鍵詞在文檔中的屬性信息，減少不必要的相對位置計算，既節省了 CPU時間，又減少了一些磁碟10。從而改進了站點聚類算法，降低了時間複雜度。


圖1為現有倒排文件結構示意圖；圖2為現有檢索系統的分布式結構示意圖；圖3為本發明的大規模數據搜索系統的整體結構及數據流示意圖；圖4為記錄文件和索引文件的示意圖；圖5為關鍵詞列表示意圖；圖6為文檔列表的cache組織結構示意圖；圖7為位置信息塊組織結構示意圖。
具體實施例方式下面結合附圖及本發明的實施例對本發明的搜索系統作進一步詳細的說明。本發明的基本思想搜尋引擎的檢索效率是評價搜尋引擎質量的一個重要指標， 面對網際網路上信息量的不斷增加以及搜尋引擎網頁庫的不斷增大，對檢索系統性能要求也越來越高。本發明詳細介紹一個搜尋引擎檢索系統即數據搜索系統的設計與實現，針對搜尋引擎檢索系統的性能進行了描述，討論了影響檢索性能的幾個因素，並分別提出改進的方法和途徑。這些方法包括設計出結構更加良好的倒排文件結構，改進整數壓縮編碼，引入倒排文件cache，預先計算關鍵詞與文檔相關度，減少關鍵詞相對位置計算開銷，改進站點聚類算法等。圖3為本發明的大規模數據搜索系統的整體結構及數據流示意圖，如圖3所示，該系統主要由如下6個部分構成倒排文件模塊、數據接口模塊、查詢模塊、切詞模塊及記分函數模塊以及進程守護模塊。其中，數據接口模塊，是一組接口類，封裝了每個要公開的數據的訪問方法。查詢模塊，用於利用輸入端查詢條件進行搜索。切詞模塊與現有搜尋引擎系統相同。記分函數模塊，負責進行站點聚類。進程守護模塊用於接受查詢請求。該系統的工作流程是，守護進程從internet或本地接收到原始查詢，調用切詞模塊得到各個關鍵詞並形成一棵查詢樹，再調用查詢模塊。查詢模塊簡單的把各個關鍵詞對應文檔列表求交集，每得到一個結果則調用一次計分函數，最終得到一個聚類好的查詢結果，排序並返回給守護進程。守護進程再根據請求中指定的最大返回結果數，將部分結果返回。下面對本發明的大規模搜索系統的各個部分分別作詳細說明。1、針對倒排文件模塊為了讓應用程式進行高效檢索，並改進結果的排序，我們設計了新的倒排文件結構。在系統的開發過程中，這個結構被修改了很多次，每個設計都各有利弊，最終確定的結構也不是在各方面都最優。但倒排文件的設計都必須遵循幾個基本的原則文件必須是沒有二義性，可以正確的還原出數據。例如當我們保存記錄〈doclXp OSlpOS2XdOC2XpOSr pos2』... >，在讀取的時候就無法確定處保存的是出現該關鍵詞的新的一個文檔號，還是該關鍵詞在docl中的下一個出現位置。因此必須多保存一個詞頻信息，例如 。tfl 和 tf2 分別表示詞在docl和doc2中的出現次數。這樣才可正確的還原出信息。文件的規模應當儘量小，記錄文件中每條記錄應該佔用儘可能小的空間，以減少讀取記錄時傳輸的數據量。方法是進行索引壓縮技術[Scholer，et al. ,2002]使用變長的整數編碼，用較少的空間保存較小的整數；整數使用差值存放，例如把文檔號按升序排列， 第一個文檔號保存實際值，之後的都保存與前一個文檔號的差值。關鍵詞在文檔中的位置也用類似的保存方法。差值表示法的另一個好處就是可以更方便的求多個文檔列表的交集，並且更方便的計算多個關鍵詞在同一文檔中的相對位置，在後面我們還會介紹。雖然對索引進行壓縮會帶來額外的數據解壓開銷，但相對於它帶來的好處，這種開銷完全是值得的。索引壓縮減少了讀取數據時從磁碟傳輸的數據量，但在檢索時平均每個查詢對磁碟的訪問次數，更大的影響了檢索效率。因此，設計倒排文件時，應當支持程序在最少次數內讀取到需要的信息。例如在上一章中提到的，把文檔列表連續的保存。倒排文件的設計還必須考慮方便索引模塊的建立，以及方便檢索模塊的操作，因此結構不應該太複雜。例如，在設計過程中參考了現有技術中的倒排文件分塊組織技術，把文檔根據屬性的不同分塊保存。表面上看查詢時可以先讀重要的文檔列表，但在實現過程中卻發現對於多個關鍵詞組成的查詢，操作起來異常的複雜，最終不得不放棄。2、整數壓縮編碼方法變長的整數編碼可分為兩類，字節對齊整數編碼和非字節對齊整數編碼。前者優勢有較高的壓縮比率，後者則有更高的壓縮與解壓效率。在搜尋引擎的應用中，檢索效率比索引數據佔用的空間更為重要。文中對比了字節對齊編碼ByteCode和非字節對齊編碼 Golomb [ffitten,et al.，1994]，其壓縮比率分別為0. 3359和0. 2635，解碼時間比為1 6。 目前天網系統中使用的ByteCode編碼在現有技術中有描述，它可對數值從O至230_1的正整數進行壓縮編碼。用第一個字節的最高兩位表示整數所佔的字節數，則1位元組的壓縮整數包含6個有效位，可表示整數O至63 ;2位元組的壓縮整數包含14個有效位，表示整數範圍從64至214-1。3位元組可表示從214至222-1，4位元組可表示從222至230-1。在新的系統設計依然使用字節對齊的整數編碼方式，用ByteCodeEx表示，但與 ByteCode不同，ByteCodeEx使用了可變長的位數來表示壓縮整數的所佔字節數，並且根據計算機的字節序(Byte Order)使用不相同的編碼方式，加快解碼速度。以Big Endian的字節序為例，第一字節的最高位開始，如果連續η個位為1，則表示壓縮整數長度為η+1個字節，有效位從第一個為0的位開始。例如第一個字節110001101，從最高位開始連續出現 2個1，則說明整數佔3個字節；又例如第一個字節01100101，最高一位就是0，說明整數佔 1個字節，該整數為的值為99。由此我們可以得出，m個字節的壓縮整數可表示的整數最大值為^Xm-(m-2)-l。這種方法比ByteCode的優勢是只需一個字節就可表示從0至127， 對於小整數佔多數的倒排文件來說，壓縮率比較高，可以為每個從64至127的整數節省去一個字節的空間。但當整數的範圍從221到222-1時，則會多佔用一個字節。ByteCodeEx 可擴展到無限大的正整數。以下是為2576933個文檔建立倒排索引，對整數的使用情況統計
權利要求
1.一種大規模數據搜索系統，其特徵在於，其主要包括倒排文件模塊、數據接口模塊、 查詢模塊、切詞模塊及記分函數模塊以及進程守護模塊，其中所述倒排文件模塊，用於搜索系統能夠快速找到查詢詞對應的文檔列表； 所述數據接口模塊，是一組接口類，封裝了每個要公開的數據的訪問方法； 所述查詢模塊，用於利用輸入端查詢條件進行搜索，將各個關鍵詞對應文檔列表求交集；所述切詞模塊，用於切詞並得到各個關鍵詞並形成一棵查詢樹； 所述記分函數模塊，負責進行站點聚類，得到聚類好的查詢結果，排列並返回給守護進程模塊；以及，所述守護進程模塊，用於接受查詢請求，並根據查詢請求中指定的最大返回結果數，將部分結果返回。
2.根據權利要求1所述的大規模數據搜索系統，其特徵在於，所述倒排文件模塊，採用新的倒排文件格式，其包含描述文件、索引文件和記錄文件，支持程序的快速訪問。
3.根據權利要求1或2所述的大規模數據搜索系統，其特徵在於，所述倒排文件模塊的描述文件，包括倒排文件自身的屬性信息，包括Byte-Order屬性表示倒排文件中使用整數的字節序，包含壓縮整數和非壓縮整數； Align-Bits屬性使用了 32位的偏移量，Align-bits屬性表示移動的位數； Attr-Size屬性在這個格式中，允許關鍵詞在每個出現它的文檔中，有0個或多個字節的屬性信息；這個屬性信息的意義在本格式中無定義，完全由應用程式決定；該屬性信息必須是整字節的，並且所有的屬性信息必須等長；這個長度就是倒排文件的Attr-size 屬性；Uint-Encoding屬性壓縮整數的編碼方式。
全文摘要
本發明公開了一種大規模數據搜索系統，主要包括倒排文件模塊、數據接口模塊、查詢模塊、切詞模塊及記分函數模塊以及進程守護模塊，倒排文件模塊用於搜索系統能夠快速找到查詢詞對應的文檔列表；數據接口模塊封裝了每個要公開的數據的訪問方法；查詢模塊用於利用輸入端查詢條件進行搜索，將各個關鍵詞對應文檔列表求交集；切詞模塊用於切詞並得到各個關鍵詞並形成一棵查詢樹；記分函數模塊負責進行站點聚類，得到聚類好的查詢結果；守護進程模塊用於接受查詢請求並根據查詢請求中指定的最大返回結果數。利用該系統，能夠減少訪問磁碟的開銷；並通過一些有效的預處理，減少浮點運算的次數，進一步提高檢索效率。
文檔編號G06F17/30GK102201007SQ20111015955
公開日2011年9月28日 申請日期2011年6月14日 優先權日2011年6月14日
發明者劉奎飛, 張 傑 申請人:悠易互通(北京)廣告有限公司