搜索引擎的體系結構與索引技術探析

王改香 (山西金融職業學院信息技術系,山西太原030008)

從20世紀末開始,經濟文化領域就迅速進入了信息時代,知識和信息的爆炸式發展與網絡的應用成為信息擴張的先鋒。面對著網絡中浩如星海的龐大知識信息庫,無法準確全面的找到所需要的信息成為制約網絡信息發展的枷鎖。信息檢索的索引技術發展彌補了這一缺陷,搜索引擎應運而生,成為海量網絡信息準確全面定位的應用技術。搜索引擎是網絡信息精準定位的應用,實現了龐大網絡信息量的查詢。而索引技術是搜索引擎的核心技術。下面,筆者對搜索引擎體系結構和索引技術進行分析。

1 搜索引擎的體系結構

搜索引擎的基本結構一般包括數據采集、數據分析、數據組織、數據檢索和信息挖掘5個功能模塊。數據采集是負責按照一定的方式和要求對網絡上的WWW站點等資源進行搜集,并將搜集到的WWW網頁信息經過網絡傳輸,存儲到搜索引擎的搜索端數據庫中;數據分析負責對收集到的網頁信息進行分析,按照特定的算法,從中提取有檢索或查詢價值的內容 (網頁關鍵詞、網頁的分類類別、被其他網頁鏈接次數等);數據組織是形成規范的索引數據庫或便于瀏覽的層次型分類目錄結構;數據檢索負責幫助用戶用一定的檢索方式來檢索索引數據庫或瀏覽分類目錄結構,以獲取用戶所需的信息;信息挖掘負責提取用戶相關信息,以利用這些信息來提高檢索服務的質量。如根據用戶以前檢索行為的學習統計及其登記的信息,可以實現個性化檢索[1]。這5個功能模塊構成了搜索引擎的基本體系結構,而不同的搜索引擎體系結構也有很多不同,下面筆者以幾個典型的搜索引擎為例來分析搜索引擎的體系結構。

1)獨立搜索引擎 實際中,獨立搜索引擎就是以搜索引擎的結構為基礎建立而成的。現在主流應用的第二代搜索引擎的構成具有結構上的統一和相似性:以搜集器完成廣域網中網頁信息和超鏈接信息的獲取;網頁數據庫儲存已經獲取的網頁信息與超鏈接結構的信息,做為備用等待分析器進行處理分析;分析器以網絡中數據信息的特點為依據,以一定的算法作為分析方法,對網頁數據庫中儲存的網絡與超鏈接信息進行處理分析,提取與用戶檢索內容相關的頁面描述信息,將分析后的信息傳送到索引器建立結構索引;索引器將分析器所處理分析的頁面抽象數據建立索引,分析器處理分析的頁面描述信息,是頁面與頁面之間數據描述的正派表;索引數據庫將與用戶檢索內容相關的信息進行存儲,其中包括頁面描述信息、各種索引數據、對檢索結果有影響的用戶信息等;檢索器對用戶檢索請求進行響應,并對用戶的檢索進行跟蹤;用戶信息庫將檢索用戶的相關信息進行存儲,包括用戶的IP地址、所有檢索串和用戶對檢索的不同響應;挖掘器用于用戶信息的獲取,并以這些信息為依據對檢索服務質量進行調整;用戶接口為搜索引擎在用戶端所顯示的界面,提供用戶的相關查詢、結果顯示與相關的反饋機制。

2)元搜索引擎 元搜索引擎的基本原理是調用各獨立搜索引擎進行檢索,并提供統一的用戶界面和結果輸出,因此,可將其按照功能分為3大部分:用戶接口、查詢代理和結果匯總。元搜索引擎采用統一的檢索界面,供用戶輸入查詢請求。用戶接口包括請求提交和檢索接口兩部分組成。其中,請求提交的功能是將用戶檢索請求發送至成員搜索引擎。通常情況下,元搜索引擎對所能調動的成員搜索引擎進行設定;也存在部分元搜索引擎提供成員搜索引擎給用戶進行選擇;還有部分元搜索引擎以用戶的搜索信息與網絡的及時狀況為用戶提供成員搜索引擎,對用戶的查詢的響應速度和準確率進行優化。

元搜索引擎的優點從元搜索引擎的結構可以看出,元搜索引擎的技術重點在于查詢前的處理 (檢索請求的分發和轉換)和檢索結果的集成。一般來說,元搜索引擎都是選擇那些比較典型的、性能優異的獨立搜索引擎作為其成員搜索引擎。這樣,與獨立搜索引擎相比,元搜索引擎具有如下主要優點:搜索信息的覆蓋面廣、搜索結果具有權威性、可靠性、易維護性。元搜索引擎的出現大大提高了用戶查詢信息的覆蓋面。由于它能夠在多個搜索引擎中搜索,必然能夠為檢索提供更多的機會。但它在查詢的準確度上卻不一定強于獨立搜索引擎。元搜索引擎的主要局限性體現在以下幾個方面:調用搜索引擎的局限性、查詢請求上的局限性、查詢結果數量上的局限性、查詢結果排序上的局限性。

3)分布式搜索引擎 以機器人為基礎的搜索引擎 (Alta Vista)與目錄式搜索引擎 (Yahoo!)在體系結構的角度皆為集中形式,工作方式都是通過自動搜索程序在廣域網中抓取Web頁面,在處理之后將信息集中存儲在站點中,用戶查詢中通過對站點的訪問實現查詢過程[2]。一般情況下,集中式搜索引擎各部分都是獨立對信息進行抓取和處理分析,沒有協作性,從而造成工作的無效重復,也是對網絡帶寬資源極大的浪費,也成為各Web站點中無謂的負擔。所以說,集中式搜索引擎的結構體系不能夠適應現在網絡規模不斷擴大的形式。

而分布式搜索引擎是針對這種先天不足的搜索引擎而產生的,建立的中心思想是將IP地址、所在地域和主題等劃分標準為依據,將廣域網絡劃分為不同的搜索域,在搜索域中分別設置不同的檢索服務器 (Index Server)。各個分域中的檢索服務器由代理 (Broker)、信息搜集軟件 (Gatherer)和索引數據庫 (Index Database)3個部分構成。代理的任務是為用戶提供查詢服務的借口,實現與其他代理之間的互通,完成不同檢索服務器之間的信息交換;信息搜索軟件的功能是對本域內的數據信息進行抓取,在索引信息的處理后將信息發送到索引數據庫。用戶的查詢要求通過代理完成定向的重置,在當前索引庫無法完成用戶的查詢任務請求時,將請求發送至其他檢索服務器,實現查詢的分布式搜索。

2 索引技術

Indexer模塊及Collection Analysis模塊為頁面集合創建了許多種類型的索引。Indexer模塊創建2種基本索引,即文本索引 (網頁的內容索引)及鏈接索引 (超鏈接結構)[3]。Collection Analysis模塊利用這2種索引創建許多其他的輔助索引。

1)文本索引 文本索是查找與用戶查詢詞相關頁面的主要方法。可以使用任何傳統索引方法為頁面內容建立索引,如倒排文件、倒排索引、后綴數組、簽名文件等。倒排索引方式是Web環境中最常用的索引方法。

2)鏈接索引 為了創建鏈接索引,可以將Web看做是一個巨大的圖,圖中的節點表示頁面。從頁面A到頁面B的超鏈接構成圖的邊。鏈接索引的目的是實現對圖的高效訪問。搜索算法最常用的訪問方式是找出與某一頁面鄰接的頁面。使用Web構成的圖及其補圖的鄰接鏈表可以有效地對這種鄰接信息進行訪問。其他類型的鏈接信息也可以通過鄰接鏈表方便地得到。例如,若要獲得某一頁面的 “兄弟”節點,可以通過2個鄰接矩陣得到。

3)輔助索引 輔助索引的數量及類型是Collection Analysis模塊根據搜索引擎的特色及搜索算法所利用的Web特性所決定的。例如,若需要在指定網站范圍內響應查詢,建立網站索引將會高效率地處理該查詢。同樣,采用鏈接索引包含的鄰接信息,可以比較容易地計算每個頁面的PageRank權值。

4)倒排索引 倒排索引由倒排列表構成。每個詞對應一個倒排列表。倒排列表是詞在頁面中的位置的有序列表。在最簡單情況下,位置信息包括頁面標識及詞在頁面中出現的位置。查詢算法通常還要用到詞的其他特征信息。例如,該詞是否被加粗,是否在標題中,是否是超鏈接的錨文本。評估算法可能對這樣的詞分配高的權重。為了實現這樣的功能,需要為每個詞配置一些額外的信息。除了倒排列表之外,許多文本索引還保存語匯信息。語匯信息列出所有在倒排索引中出現的詞及其統計信息,例如,某個詞在頁面集中出現的次數。這些統計信息同樣也被評估算法使用。

由于Web的數據規模龐大,為Web建立倒排索引是一個極具挑戰性的工作。一般地,建立倒排索引首先需要按詞排序,然后再按詞位置排序,最后將這些信息保存到磁盤中。對于小規模的數據集,例如,傳統的信息檢索 (IR)系統,建立索引的時間可以忽略不計[4]。但是對于Web上的中大規模數據集,這種簡單的建立索引的方案不可操作,需要耗費很大的資源及時間。例如,WebBase存儲了4百萬的頁面,只占可索引Web信息總量的4%,但這已經比最大的IR測試數據集TREC-7(100GB)大了許多。

此外,由于Web內容不斷變化,需要定時地對索引進行更新,以便保持數據的 “新鮮”程度。這樣,也需要不斷地重建索引。通常的增量式索引更新方法對于Web的情況不適用,因為通常相鄰時間采集的2個頁面集合差別很大。倒排索引的存儲格式必須仔細考慮。有效的壓縮方法對索引訪問性能的影響很大,因為在內存中同時可以保存更多的索引條目。此時,必須對性能上的收益與解壓縮的代價進行權衡。

3 搜索引擎的發展趨勢

隨著網絡信息的爆炸式增長和內容形式的不斷出新,搜索引擎越來越不能滿足客戶的各種信息需求,目前的搜索引擎仍然存在著不少的局限性:搜索引擎對信息的標引深度不夠,搜索引擎的信息量占有不足,搜索引擎的檢準率不高,檢索功能單一、缺乏靈活性,搜索引擎自身的技術局限。所以,搜索引擎發展的方向是以更先進、更高效的搜索技術為基礎,為用戶提供更精準、更適用的專業搜索工具,從而滿足用戶搜索查詢需求。

1)發展垂直化專業領域搜索 隨著社會分工的細化,不同領域的用戶所提出的查詢要求也更精細、更專業。以綜合門戶性質為特點的搜索引擎對不同方面、不同學科、不同行業的信息收錄過多,查詢的精準度受到了嚴重影響。垂直結構的專業搜索引擎面向特定的領域,對專業內的搜索需求和技術要求研究更為深入,能夠確保本領域內數據信息收錄的完全性和及時性。

2)搜索引擎的智能化 傳統搜索引擎的搜索模式是被動的,而搜索行為的準確性是對所收錄的信息和搜索請求有更精準的理解。以自然語言的理解技術為基礎的搜索引擎,能夠完成與客戶的自然語言溝通,對用戶的搜索請求理解更深入,所產生的結果更精準。智能代理是信息化的另一種機制,它使用自動獲得的領域模型、用戶模型知識進行信息搜集、索引、過濾,并自動將用戶感興趣的、對用戶有用的信息提交給用戶[5]。智能代理具有不斷學習、適應信息和用戶興趣動態變化的能力,可提供個性化的服務。智能代理可在用戶端進行,也可在服務器端進行。

3)開展搜索引擎的本地化服務 世界上許多著名的搜索引擎都在美國,這些綜合性的搜索引擎已不能滿足非美國網民的信息需求,因此搜索引擎必須本土化。Yahoo!、Lycos等著名公司已陸續推出適合不同國家、不同地區的本地搜索網站,搜索的本地化已勢不可擋。而中文搜索引擎自然成為搜索引擎本地化的最大潛在市場。

4)采用分布式并行處理技術提高系統規模和性能 當搜索引擎的規模達到一定程度 (網頁數達到億級)時,如何及時地獲取新網頁和刷新數據庫,保證查詢效率不會明顯降低,這就要依賴于設計合理的并行處理技術,采用某種分布式方法,以提高系統性能。

[1]徐舒.淺談搜索引擎的體系結構與索引技術 [J].中國新技術新產品,2010(1):43.

[2]禹喆.對于搜索引擎的體系結構與索引技術的研究 [J].中國農業會計,2010(18):190.

[3]王錚,胡永杰.元搜索引擎的設計與實現 [J].河北師范大學學報(自然科學版),2010,25(2):175-178.

[4]鄒海華.基于網站信息組織的搜索引擎優化策略[J].素質教育論壇,2010(18):5-7.

[5]梁靜,葛宇,洪潔.搜索引擎優化初探探 [J].河北師范大學學報(自然科學版),2010,25(5):194-197.