搜索引擎的體系結(jié)構(gòu)與索引技術(shù)探析

王改香 (山西金融職業(yè)學(xué)院信息技術(shù)系,山西太原030008)

從20世紀(jì)末開(kāi)始,經(jīng)濟(jì)文化領(lǐng)域就迅速進(jìn)入了信息時(shí)代,知識(shí)和信息的爆炸式發(fā)展與網(wǎng)絡(luò)的應(yīng)用成為信息擴(kuò)張的先鋒。面對(duì)著網(wǎng)絡(luò)中浩如星海的龐大知識(shí)信息庫(kù),無(wú)法準(zhǔn)確全面的找到所需要的信息成為制約網(wǎng)絡(luò)信息發(fā)展的枷鎖。信息檢索的索引技術(shù)發(fā)展彌補(bǔ)了這一缺陷,搜索引擎應(yīng)運(yùn)而生,成為海量網(wǎng)絡(luò)信息準(zhǔn)確全面定位的應(yīng)用技術(shù)。搜索引擎是網(wǎng)絡(luò)信息精準(zhǔn)定位的應(yīng)用,實(shí)現(xiàn)了龐大網(wǎng)絡(luò)信息量的查詢(xún)。而索引技術(shù)是搜索引擎的核心技術(shù)。下面,筆者對(duì)搜索引擎體系結(jié)構(gòu)和索引技術(shù)進(jìn)行分析。

1 搜索引擎的體系結(jié)構(gòu)

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

1)獨(dú)立搜索引擎 實(shí)際中,獨(dú)立搜索引擎就是以搜索引擎的結(jié)構(gòu)為基礎(chǔ)建立而成的?，F(xiàn)在主流應(yīng)用的第二代搜索引擎的構(gòu)成具有結(jié)構(gòu)上的統(tǒng)一和相似性:以搜集器完成廣域網(wǎng)中網(wǎng)頁(yè)信息和超鏈接信息的獲取;網(wǎng)頁(yè)數(shù)據(jù)庫(kù)儲(chǔ)存已經(jīng)獲取的網(wǎng)頁(yè)信息與超鏈接結(jié)構(gòu)的信息,做為備用等待分析器進(jìn)行處理分析;分析器以網(wǎng)絡(luò)中數(shù)據(jù)信息的特點(diǎn)為依據(jù),以一定的算法作為分析方法,對(duì)網(wǎng)頁(yè)數(shù)據(jù)庫(kù)中儲(chǔ)存的網(wǎng)絡(luò)與超鏈接信息進(jìn)行處理分析,提取與用戶(hù)檢索內(nèi)容相關(guān)的頁(yè)面描述信息,將分析后的信息傳送到索引器建立結(jié)構(gòu)索引;索引器將分析器所處理分析的頁(yè)面抽象數(shù)據(jù)建立索引,分析器處理分析的頁(yè)面描述信息,是頁(yè)面與頁(yè)面之間數(shù)據(jù)描述的正派表;索引數(shù)據(jù)庫(kù)將與用戶(hù)檢索內(nèi)容相關(guān)的信息進(jìn)行存儲(chǔ),其中包括頁(yè)面描述信息、各種索引數(shù)據(jù)、對(duì)檢索結(jié)果有影響的用戶(hù)信息等;檢索器對(duì)用戶(hù)檢索請(qǐng)求進(jìn)行響應(yīng),并對(duì)用戶(hù)的檢索進(jìn)行跟蹤;用戶(hù)信息庫(kù)將檢索用戶(hù)的相關(guān)信息進(jìn)行存儲(chǔ),包括用戶(hù)的IP地址、所有檢索串和用戶(hù)對(duì)檢索的不同響應(yīng);挖掘器用于用戶(hù)信息的獲取,并以這些信息為依據(jù)對(duì)檢索服務(wù)質(zhì)量進(jìn)行調(diào)整;用戶(hù)接口為搜索引擎在用戶(hù)端所顯示的界面,提供用戶(hù)的相關(guān)查詢(xún)、結(jié)果顯示與相關(guān)的反饋機(jī)制。

2)元搜索引擎 元搜索引擎的基本原理是調(diào)用各獨(dú)立搜索引擎進(jìn)行檢索,并提供統(tǒng)一的用戶(hù)界面和結(jié)果輸出,因此,可將其按照功能分為3大部分:用戶(hù)接口、查詢(xún)代理和結(jié)果匯總。元搜索引擎采用統(tǒng)一的檢索界面,供用戶(hù)輸入查詢(xún)請(qǐng)求。用戶(hù)接口包括請(qǐng)求提交和檢索接口兩部分組成。其中,請(qǐng)求提交的功能是將用戶(hù)檢索請(qǐng)求發(fā)送至成員搜索引擎。通常情況下,元搜索引擎對(duì)所能調(diào)動(dòng)的成員搜索引擎進(jìn)行設(shè)定;也存在部分元搜索引擎提供成員搜索引擎給用戶(hù)進(jìn)行選擇;還有部分元搜索引擎以用戶(hù)的搜索信息與網(wǎng)絡(luò)的及時(shí)狀況為用戶(hù)提供成員搜索引擎,對(duì)用戶(hù)的查詢(xún)的響應(yīng)速度和準(zhǔn)確率進(jìn)行優(yōu)化。

元搜索引擎的優(yōu)點(diǎn)從元搜索引擎的結(jié)構(gòu)可以看出,元搜索引擎的技術(shù)重點(diǎn)在于查詢(xún)前的處理 (檢索請(qǐng)求的分發(fā)和轉(zhuǎn)換)和檢索結(jié)果的集成。一般來(lái)說(shuō),元搜索引擎都是選擇那些比較典型的、性能優(yōu)異的獨(dú)立搜索引擎作為其成員搜索引擎。這樣,與獨(dú)立搜索引擎相比,元搜索引擎具有如下主要優(yōu)點(diǎn):搜索信息的覆蓋面廣、搜索結(jié)果具有權(quán)威性、可靠性、易維護(hù)性。元搜索引擎的出現(xiàn)大大提高了用戶(hù)查詢(xún)信息的覆蓋面。由于它能夠在多個(gè)搜索引擎中搜索,必然能夠?yàn)闄z索提供更多的機(jī)會(huì)。但它在查詢(xún)的準(zhǔn)確度上卻不一定強(qiáng)于獨(dú)立搜索引擎。元搜索引擎的主要局限性體現(xiàn)在以下幾個(gè)方面:調(diào)用搜索引擎的局限性、查詢(xún)請(qǐng)求上的局限性、查詢(xún)結(jié)果數(shù)量上的局限性、查詢(xún)結(jié)果排序上的局限性。

3)分布式搜索引擎 以機(jī)器人為基礎(chǔ)的搜索引擎 (Alta Vista)與目錄式搜索引擎 (Yahoo!)在體系結(jié)構(gòu)的角度皆為集中形式,工作方式都是通過(guò)自動(dòng)搜索程序在廣域網(wǎng)中抓取Web頁(yè)面,在處理之后將信息集中存儲(chǔ)在站點(diǎn)中,用戶(hù)查詢(xún)中通過(guò)對(duì)站點(diǎn)的訪(fǎng)問(wèn)實(shí)現(xiàn)查詢(xún)過(guò)程[2]。一般情況下,集中式搜索引擎各部分都是獨(dú)立對(duì)信息進(jìn)行抓取和處理分析,沒(méi)有協(xié)作性,從而造成工作的無(wú)效重復(fù),也是對(duì)網(wǎng)絡(luò)帶寬資源極大的浪費(fèi),也成為各Web站點(diǎn)中無(wú)謂的負(fù)擔(dān)。所以說(shuō),集中式搜索引擎的結(jié)構(gòu)體系不能夠適應(yīng)現(xiàn)在網(wǎng)絡(luò)規(guī)模不斷擴(kuò)大的形式。

而分布式搜索引擎是針對(duì)這種先天不足的搜索引擎而產(chǎn)生的,建立的中心思想是將IP地址、所在地域和主題等劃分標(biāo)準(zhǔn)為依據(jù),將廣域網(wǎng)絡(luò)劃分為不同的搜索域,在搜索域中分別設(shè)置不同的檢索服務(wù)器 (Index Server)。各個(gè)分域中的檢索服務(wù)器由代理 (Broker)、信息搜集軟件 (Gatherer)和索引數(shù)據(jù)庫(kù) (Index Database)3個(gè)部分構(gòu)成。代理的任務(wù)是為用戶(hù)提供查詢(xún)服務(wù)的借口,實(shí)現(xiàn)與其他代理之間的互通,完成不同檢索服務(wù)器之間的信息交換;信息搜索軟件的功能是對(duì)本域內(nèi)的數(shù)據(jù)信息進(jìn)行抓取,在索引信息的處理后將信息發(fā)送到索引數(shù)據(jù)庫(kù)。用戶(hù)的查詢(xún)要求通過(guò)代理完成定向的重置,在當(dāng)前索引庫(kù)無(wú)法完成用戶(hù)的查詢(xún)?nèi)蝿?wù)請(qǐng)求時(shí),將請(qǐng)求發(fā)送至其他檢索服務(wù)器,實(shí)現(xiàn)查詢(xún)的分布式搜索。

2 索引技術(shù)

Indexer模塊及Collection Analysis模塊為頁(yè)面集合創(chuàng)建了許多種類(lèi)型的索引。Indexer模塊創(chuàng)建2種基本索引,即文本索引 (網(wǎng)頁(yè)的內(nèi)容索引)及鏈接索引 (超鏈接結(jié)構(gòu))[3]。Collection Analysis模塊利用這2種索引創(chuàng)建許多其他的輔助索引。

1)文本索引 文本索是查找與用戶(hù)查詢(xún)?cè)~相關(guān)頁(yè)面的主要方法?？梢允褂萌魏蝹鹘y(tǒng)索引方法為頁(yè)面內(nèi)容建立索引,如倒排文件、倒排索引、后綴數(shù)組、簽名文件等。倒排索引方式是Web環(huán)境中最常用的索引方法。

2)鏈接索引 為了創(chuàng)建鏈接索引,可以將Web看做是一個(gè)巨大的圖,圖中的節(jié)點(diǎn)表示頁(yè)面。從頁(yè)面A到頁(yè)面B的超鏈接構(gòu)成圖的邊。鏈接索引的目的是實(shí)現(xiàn)對(duì)圖的高效訪(fǎng)問(wèn)。搜索算法最常用的訪(fǎng)問(wèn)方式是找出與某一頁(yè)面鄰接的頁(yè)面。使用Web構(gòu)成的圖及其補(bǔ)圖的鄰接鏈表可以有效地對(duì)這種鄰接信息進(jìn)行訪(fǎng)問(wèn)。其他類(lèi)型的鏈接信息也可以通過(guò)鄰接鏈表方便地得到。例如,若要獲得某一頁(yè)面的 “兄弟”節(jié)點(diǎn),可以通過(guò)2個(gè)鄰接矩陣得到。

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

4)倒排索引 倒排索引由倒排列表構(gòu)成。每個(gè)詞對(duì)應(yīng)一個(gè)倒排列表。倒排列表是詞在頁(yè)面中的位置的有序列表。在最簡(jiǎn)單情況下,位置信息包括頁(yè)面標(biāo)識(shí)及詞在頁(yè)面中出現(xiàn)的位置。查詢(xún)算法通常還要用到詞的其他特征信息。例如,該詞是否被加粗,是否在標(biāo)題中,是否是超鏈接的錨文本。評(píng)估算法可能對(duì)這樣的詞分配高的權(quán)重。為了實(shí)現(xiàn)這樣的功能,需要為每個(gè)詞配置一些額外的信息。除了倒排列表之外,許多文本索引還保存語(yǔ)匯信息。語(yǔ)匯信息列出所有在倒排索引中出現(xiàn)的詞及其統(tǒng)計(jì)信息,例如,某個(gè)詞在頁(yè)面集中出現(xiàn)的次數(shù)。這些統(tǒng)計(jì)信息同樣也被評(píng)估算法使用。

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

此外,由于Web內(nèi)容不斷變化,需要定時(shí)地對(duì)索引進(jìn)行更新,以便保持?jǐn)?shù)據(jù)的 “新鮮”程度。這樣,也需要不斷地重建索引。通常的增量式索引更新方法對(duì)于Web的情況不適用,因?yàn)橥ǔＯ噜彆r(shí)間采集的2個(gè)頁(yè)面集合差別很大。倒排索引的存儲(chǔ)格式必須仔細(xì)考慮。有效的壓縮方法對(duì)索引訪(fǎng)問(wèn)性能的影響很大,因?yàn)樵趦?nèi)存中同時(shí)可以保存更多的索引條目。此時(shí),必須對(duì)性能上的收益與解壓縮的代價(jià)進(jìn)行權(quán)衡。

3 搜索引擎的發(fā)展趨勢(shì)

隨著網(wǎng)絡(luò)信息的爆炸式增長(zhǎng)和內(nèi)容形式的不斷出新,搜索引擎越來(lái)越不能滿(mǎn)足客戶(hù)的各種信息需求,目前的搜索引擎仍然存在著不少的局限性:搜索引擎對(duì)信息的標(biāo)引深度不夠,搜索引擎的信息量占有不足,搜索引擎的檢準(zhǔn)率不高,檢索功能單一、缺乏靈活性,搜索引擎自身的技術(shù)局限。所以,搜索引擎發(fā)展的方向是以更先進(jìn)、更高效的搜索技術(shù)為基礎(chǔ),為用戶(hù)提供更精準(zhǔn)、更適用的專(zhuān)業(yè)搜索工具,從而滿(mǎn)足用戶(hù)搜索查詢(xún)需求。

1)發(fā)展垂直化專(zhuān)業(yè)領(lǐng)域搜索 隨著社會(huì)分工的細(xì)化,不同領(lǐng)域的用戶(hù)所提出的查詢(xún)要求也更精細(xì)、更專(zhuān)業(yè)。以綜合門(mén)戶(hù)性質(zhì)為特點(diǎn)的搜索引擎對(duì)不同方面、不同學(xué)科、不同行業(yè)的信息收錄過(guò)多,查詢(xún)的精準(zhǔn)度受到了嚴(yán)重影響。垂直結(jié)構(gòu)的專(zhuān)業(yè)搜索引擎面向特定的領(lǐng)域,對(duì)專(zhuān)業(yè)內(nèi)的搜索需求和技術(shù)要求研究更為深入,能夠確保本領(lǐng)域內(nèi)數(shù)據(jù)信息收錄的完全性和及時(shí)性。

2)搜索引擎的智能化 傳統(tǒng)搜索引擎的搜索模式是被動(dòng)的,而搜索行為的準(zhǔn)確性是對(duì)所收錄的信息和搜索請(qǐng)求有更精準(zhǔn)的理解。以自然語(yǔ)言的理解技術(shù)為基礎(chǔ)的搜索引擎,能夠完成與客戶(hù)的自然語(yǔ)言溝通,對(duì)用戶(hù)的搜索請(qǐng)求理解更深入,所產(chǎn)生的結(jié)果更精準(zhǔn)。智能代理是信息化的另一種機(jī)制,它使用自動(dòng)獲得的領(lǐng)域模型、用戶(hù)模型知識(shí)進(jìn)行信息搜集、索引、過(guò)濾,并自動(dòng)將用戶(hù)感興趣的、對(duì)用戶(hù)有用的信息提交給用戶(hù)[5]。智能代理具有不斷學(xué)習(xí)、適應(yīng)信息和用戶(hù)興趣動(dòng)態(tài)變化的能力,可提供個(gè)性化的服務(wù)。智能代理可在用戶(hù)端進(jìn)行,也可在服務(wù)器端進(jìn)行。

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

4)采用分布式并行處理技術(shù)提高系統(tǒng)規(guī)模和性能 當(dāng)搜索引擎的規(guī)模達(dá)到一定程度 (網(wǎng)頁(yè)數(shù)達(dá)到億級(jí))時(shí),如何及時(shí)地獲取新網(wǎng)頁(yè)和刷新數(shù)據(jù)庫(kù),保證查詢(xún)效率不會(huì)明顯降低,這就要依賴(lài)于設(shè)計(jì)合理的并行處理技術(shù),采用某種分布式方法,以提高系統(tǒng)性能。

[1]徐舒.淺談搜索引擎的體系結(jié)構(gòu)與索引技術(shù) [J].中國(guó)新技術(shù)新產(chǎn)品,2010(1):43.

[2]禹喆.對(duì)于搜索引擎的體系結(jié)構(gòu)與索引技術(shù)的研究 [J].中國(guó)農(nóng)業(yè)會(huì)計(jì),2010(18):190.

[3]王錚,胡永杰.元搜索引擎的設(shè)計(jì)與實(shí)現(xiàn) [J].河北師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2010,25(2):175-178.

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

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