淺談提高搜索引擎效率和精度的關(guān)鍵技術(shù)

摘要：為了使用戶快速地從網(wǎng)頁(yè)中找到所需要的內(nèi)容，在設(shè)計(jì)搜索引擎時(shí)，需要更好地提高搜索引擎效率和精度，該文闡述了六種提高搜索引擎效率和精度的技術(shù)。

關(guān)鍵詞：搜索引擎；聚類；相關(guān)度

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)27-1929-02

The Key Technology to Improve the Efficiency and Precision of Search Engine

XIE Jian-guo

(Computer Department，Minxi Vocational Technical College，Longyan 364021，China)

Abstract: In order to make users to quickly find the contents what they wanted in web page， when design search engine， need to improve the efficiency and precision of search engine， this paper expatiates 6 technologies which can improve the efficiency and precision of search engine.

Key words: search engine; clustering; degree of association

互聯(lián)網(wǎng)自誕生以來(lái)不斷成長(zhǎng)，其內(nèi)容不斷豐富，整個(gè)網(wǎng)絡(luò)逐漸堆積成一個(gè)前所未有的超大型信息庫(kù)。Internet作為一個(gè)信息平臺(tái)在人們的日常生活和工作中發(fā)揮著越來(lái)越重要的作用，人們?cè)絹?lái)越多地通過(guò)Internet獲取信息。然而伴隨互聯(lián)網(wǎng)的飛速發(fā)展，普通網(wǎng)絡(luò)用戶想找到所需的資料簡(jiǎn)直如同大海撈針，以至于迷失在信息的海洋中不知所措。搜索引擎的出現(xiàn)正好緩解了人們面對(duì)互聯(lián)網(wǎng)信息爆炸帶來(lái)的壓力，但是盡管如此，搜索引擎搜索得到的結(jié)果中仍然包含了與用戶查詢請(qǐng)求不相關(guān)的文檔，用戶必須逐個(gè)地瀏覽以找到相關(guān)文檔，花費(fèi)了大量的精力。當(dāng)返回的結(jié)果數(shù)目眾多時(shí)，這個(gè)問(wèn)題更為突出。因此如何更好地提高搜索引擎效率和精度，成為搜索引擎重點(diǎn)需要解決的問(wèn)題。目前提高搜索引擎效率和精度的方法主要有如下六個(gè)關(guān)鍵技術(shù)。

1 基于超鏈的相關(guān)度排序

排序搜索引擎的檢索結(jié)果往往過(guò)于龐大，用戶一般只會(huì)瀏覽前面的一部分結(jié)果。通過(guò)對(duì)檢索結(jié)果進(jìn)行相關(guān)度排序，搜索引擎試圖使相關(guān)的文檔盡可能地出現(xiàn)在結(jié)果的前面部分，以改進(jìn)檢索結(jié)果的輸出。雖然各個(gè)搜索引擎中相關(guān)度排序的具體實(shí)現(xiàn)各不相同，但是基本上都采用了基于Web文檔內(nèi)容的方法，即考慮用戶所查詢的詞條在文檔中的出現(xiàn)情況，包括：詞條頻率、逆文檔頻率、詞條位置等因素。這種方法有很大的局限性。一方面，相關(guān)度高的頁(yè)面不一定是用戶普遍歡迎的頁(yè)面；另一方面，有些Web頁(yè)面的作者利用上述因素來(lái)欺騙搜索引擎（spamming），以提高其頁(yè)面的排序。

事實(shí)上，Web中還蘊(yùn)含了豐富的結(jié)構(gòu)信息。頁(yè)面之間的超鏈反映了頁(yè)面間的引用關(guān)系，一個(gè)頁(yè)面被其它站點(diǎn)引用的次數(shù)基本上反映了該頁(yè)面的受歡迎程度（重要性）。超鏈中的標(biāo)記文本（anchor）對(duì)鏈宿頁(yè)面也起到了概括作用，這種概括在一定程度上比鏈宿頁(yè)面作者所作的概括（頁(yè)面的標(biāo)題、關(guān)鍵字、摘要）要更為客觀、準(zhǔn)確。因此，近年來(lái)出現(xiàn)了一些基于超鏈的相關(guān)度排序方法，作為基于內(nèi)容方法的補(bǔ)充，例如，Stanford大學(xué)研究的PageRank算法等。這類方法通過(guò)為Web頁(yè)面構(gòu)造引用圖，并綜合考慮頁(yè)面的被引用次數(shù)以及鏈源頁(yè)面的重要性來(lái)判斷鏈宿頁(yè)面的重要性。一些搜索引擎已經(jīng)開始使用基于超鏈的相關(guān)度排序方法。例如，以PageRank為核心技術(shù)的搜索引擎Google能夠查詢與用戶請(qǐng)求相關(guān)的“權(quán)威”頁(yè)面[1]。此外，Google通過(guò)分析超鏈中包含的文本，可以對(duì)鏈宿頁(yè)面進(jìn)行非全文索引，而不需要下載和分析實(shí)際的頁(yè)面。目前，Google已經(jīng)發(fā)展成為一個(gè)主要的搜索引擎，實(shí)際下載并索引了近100000000的Web頁(yè)面。但是通過(guò)超鏈分析，其覆蓋度達(dá)到了300000000，超過(guò)了其它任何搜索引擎。

2 檢索結(jié)果的聯(lián)機(jī)聚類

盡管搜索引擎采用了各種方法來(lái)提高檢索結(jié)果的精度，但是結(jié)果中仍然包含了與用戶查詢請(qǐng)求不相關(guān)的文檔，其比例高達(dá)75%以上。此外，搜索引擎返回給用戶的通常是一個(gè)線性的文檔列表，雖然經(jīng)過(guò)了相關(guān)度排序，但是相關(guān)文檔和不相關(guān)文檔仍然混雜于其中。用戶必須逐個(gè)地瀏覽以找到相關(guān)文檔，花費(fèi)了大量的精力。當(dāng)返回的結(jié)果數(shù)目眾多時(shí)，這個(gè)問(wèn)題更為突出。

為了方便用戶的瀏覽，一些研究人員開始將聚類技術(shù)用于Web信息檢索結(jié)果的可視化輸出。聚類是指將文檔集合分成若干個(gè)簇，要求同一簇內(nèi)文檔內(nèi)容的相似度盡可能地大，而不同簇間的相似度盡可能地小。Hearst等人的研究已經(jīng)證明了“聚類假設(shè)”，即與用戶查詢相關(guān)的文檔通常會(huì)聚類得比較靠近，而遠(yuǎn)離與用戶查詢不相關(guān)的文檔。因此，我們可以利用聚類技術(shù)將搜索引擎的檢索結(jié)果集合S劃分為若干個(gè)簇(S1，…，Si，…，Sm)，并以簇Si的質(zhì)心averaged∈Si(d)作為簇Si的描述。這樣，用戶只需要考慮那些相關(guān)的簇，大大縮小了所需要瀏覽的結(jié)果數(shù)量。當(dāng)一次聚類生成的簇Si中仍然包含大量文檔時(shí)，可以對(duì)該簇中的文檔再次聚類得到若干個(gè)子簇(Si，1，…，Si，j， …，Si，n)，直到用戶滿意為止[2]。。Etzioni等人的實(shí)驗(yàn)結(jié)果表明，使用一些改進(jìn)算法來(lái)對(duì)檢索結(jié)果進(jìn)行聯(lián)機(jī)聚類不但是可行的，而且十分有效。

3 基于概念的檢索

大多數(shù)搜索引擎提供的檢索服務(wù)是一種關(guān)鍵字檢索（KeywordSearch），即檢索出那些顯式地包含用戶指定詞條的文檔。由于自然語(yǔ)言中廣泛存在同義和多義現(xiàn)象，關(guān)鍵字檢索顯然是不夠的。一些搜索引擎，例如Magellan，開始在關(guān)鍵字檢索的基礎(chǔ)上引入基于概念的檢索（ConceptSearch）。該方法利用了詞條在概念上的相關(guān)性，因此可以檢索出那些并不顯式地包含用戶指定的詞條，但是卻包含其同義詞或者下位詞的文檔。例如，用戶向Magellan查詢“robot”時(shí)，Magellan除了返回包含“robot”的結(jié)果，還會(huì)找到提及“crawler”，“spider”，“wander”等詞條的結(jié)果。這樣，既方便了用戶請(qǐng)求的輸入，也提高了信息檢索的召回率。

搜索引擎在實(shí)現(xiàn)基于概念的檢索時(shí)，一般通過(guò)對(duì)用戶的查詢進(jìn)行概念/詞條擴(kuò)展，然后轉(zhuǎn)化為關(guān)鍵字檢索。概念/詞條關(guān)系的獲得可以有以下兩種方法。

1) 手工建立詞典來(lái)存儲(chǔ)概念層次及詞條之間的交叉聯(lián)系，該工作通常由領(lǐng)域?qū)＜襾?lái)完成。

2) 使用語(yǔ)法分析、統(tǒng)計(jì)等技術(shù)從文檔集合中自動(dòng)學(xué)習(xí)。

4 相關(guān)度反饋

在很多情況下，用戶難以提出查詢，其初始的查詢請(qǐng)求q通常是不精確、不完全的。與基于概念的檢索類似，相關(guān)度反饋技術(shù)也可以幫助用戶形成查詢請(qǐng)求。但是，基于概念檢索的目的是通過(guò)擴(kuò)展查詢請(qǐng)求來(lái)提高系統(tǒng)的召回率，而相關(guān)度反饋技術(shù)則是通過(guò)對(duì)查詢請(qǐng)求不斷地進(jìn)行修正以提高系統(tǒng)的精確度。。

具有相關(guān)度反饋功能的系統(tǒng)中，系統(tǒng)按照下述過(guò)程對(duì)用戶的查詢請(qǐng)求進(jìn)行逐步求精。

1) 索引器給出查詢q的檢索結(jié)果集合S。

2) 用戶對(duì)S中文檔的相關(guān)度進(jìn)行評(píng)估，并反饋給系統(tǒng)。所有被用戶標(biāo)記為“相關(guān)”的結(jié)果組成了正反饋集合S+，標(biāo)記為“不相關(guān)”的結(jié)果組成了負(fù)反饋集合S-。

3) 系統(tǒng)根據(jù)用戶的反饋對(duì)查詢q進(jìn)行修正。例如，在矢量空間索引模型中，可以將正反饋集合中的文檔矢量加到查詢矢量上，同時(shí)減去負(fù)反饋集合中的最不相關(guān)的若干文檔矢量，即V(q)←V(q)+∑d∈S+V(d)-∑d∈argmax(S-)V(d)。

4) 重復(fù)步驟1)，2)，3)，直到用戶得到滿意的結(jié)果為止[3]。

一些研究和實(shí)驗(yàn)結(jié)果表明，利用相關(guān)度反饋可以較好地改進(jìn)檢索效果。但是，目前很少有搜索引擎支持該功能。其原因可能是因?yàn)橄嚓P(guān)度反饋需要用戶的參與，而普通用戶在使用搜索引擎時(shí)不太愿意花時(shí)間利用這些附加功能。

5 分詞技術(shù)

網(wǎng)上的中文信息具有分詞復(fù)雜、多內(nèi)碼轉(zhuǎn)換等特點(diǎn)。因此，中文智能搜索有其獨(dú)有的特點(diǎn)。

對(duì)中文信息的訪問(wèn)，不可避免的會(huì)遇到分詞，這也是中文搜索引擎要解決的主要問(wèn)題。現(xiàn)有的漢語(yǔ)分詞算法有很多，如基于詞庫(kù)的最大匹配法、逆向最大匹配法、最佳匹配法、高頻優(yōu)先分詞法；基于語(yǔ)法和規(guī)則的分詞法；基于頻度和統(tǒng)計(jì)的分詞法；基于神經(jīng)網(wǎng)絡(luò)的分詞法和專家系統(tǒng)分詞法等[4]。這些算法適用于不同要求的場(chǎng)合但又存在各自的缺陷，在具體應(yīng)用時(shí)一般使用幾種算法相結(jié)合的方式來(lái)彌補(bǔ)單純使用一種分詞法所帶來(lái)的不足。分詞技術(shù)中的基于詞庫(kù)的算法日前使用較廣，也較為成熟。這類算法分詞的正確性很大程度上取決于所建的詞庫(kù)。一個(gè)詞庫(kù)應(yīng)具備完備性和完全性兩方面。詞庫(kù)的完備性，簡(jiǎn)單來(lái)說(shuō)就是對(duì)任意一個(gè)字串，總能按詞庫(kù)找到對(duì)它進(jìn)行切分的方法。詞庫(kù)的完全性，意味著詞庫(kù)應(yīng)包含所有的詞。通常先構(gòu)造一個(gè)最小完備詞庫(kù)，然后在此基礎(chǔ)上進(jìn)行擴(kuò)展，建立一個(gè)完全詞庫(kù)。

6 數(shù)據(jù)庫(kù)中增量式信息更新方法

增量式信息更新方法的基本思路是：在WWW中包含大量的文檔資源，這些資源的變化周期是不一致的：有的變化無(wú)常，有的十分穩(wěn)定。因此應(yīng)該以文檔的變化周期作為進(jìn)行有效性驗(yàn)證的依據(jù)，在每一次索引信息庫(kù)的更新過(guò)程中，只對(duì)那些最可能發(fā)生變化的（部分）文檔進(jìn)行驗(yàn)證。

一個(gè)文檔的變化周期就是它相鄰的兩次變化之間的時(shí)間間隔。

值得注意的是，一個(gè)文檔的變化周期可能是不固定的。在某個(gè)時(shí)期內(nèi)，它可能變化得比較頻繁，而在另一個(gè)時(shí)期內(nèi)，它則可能比較穩(wěn)定。一般地說(shuō)，無(wú)法準(zhǔn)確地計(jì)算一個(gè)文檔變化周期，只能根據(jù)文檔在一個(gè)時(shí)期內(nèi)的變化情況來(lái)估算它的變化周期。下面給出一個(gè)啟發(fā)式規(guī)則，作為估算文檔變化周期的一個(gè)依據(jù)。

如果在一個(gè)時(shí)間間隔內(nèi)一個(gè)文檔的內(nèi)容沒有發(fā)生變化，那么可以認(rèn)為它處在一個(gè)穩(wěn)定期，在下一個(gè)相同的時(shí)間間隔內(nèi)它也很可能不會(huì)發(fā)生變化。反之，如果在一個(gè)時(shí)間間隔內(nèi)一個(gè)文檔的內(nèi)容發(fā)生了變化，那么在這個(gè)時(shí)間間隔內(nèi)它就很可能發(fā)生了多次變化。

從實(shí)用的角度出發(fā)，通常以索引信息系統(tǒng)的信息更新周期作為度量文檔變化周期的時(shí)間單位，也就是說(shuō)，一個(gè)文檔變化周期的取值只能是系統(tǒng)信息更新周期的倍數(shù)。給出如下的增量式信息更新算法：

/*假設(shè)當(dāng)前正在進(jìn)行的是第k(k≥1)次信息更新過(guò)程。*/

Begin

While（索引信息庫(kù)中還有文檔信息的有效性沒有驗(yàn)證時(shí)）{任取一個(gè)未驗(yàn)證的文檔作為當(dāng)前文檔;

If（當(dāng)前文檔的變化周期f是k的因子）Then

{驗(yàn)證當(dāng)前文檔的有效性;

If（當(dāng)前文檔已不能被訪問(wèn)）Then

從索引信息庫(kù)中刪除對(duì)應(yīng)的記錄

If（當(dāng)前文檔已經(jīng)發(fā)生了變化）Then

{把當(dāng)前文檔URL加入到目標(biāo)列表;

把當(dāng)前文檔的變化周期修改為Max(1，f/2);

}

Else

把當(dāng)前文檔的變化周期修改為2f;

}

以目標(biāo)列表中的URL作為瀏覽起點(diǎn)，啟動(dòng)機(jī)器人開始新一輪信息收集工作;

End[5]

當(dāng)一個(gè)文檔第一次進(jìn)入系統(tǒng)時(shí)，它的變化周期被假定為1。也就是說(shuō)，假定它會(huì)在系統(tǒng)更新周期內(nèi)發(fā)生變化。隨著信息更新過(guò)程的不斷進(jìn)行，將根據(jù)文檔的實(shí)際變化情況，不斷地調(diào)整它們的變化周期。如果一個(gè)文檔的索引信息在一次信息更新過(guò)程需要予以更新，也就是說(shuō)，文檔的內(nèi)容發(fā)生了變化，我們認(rèn)為它很可能會(huì)在近期內(nèi)再發(fā)生變化，因此，把它的變化周期縮短為原來(lái)的一半。如果在預(yù)計(jì)的變化周期內(nèi)文檔沒有改變，那么就認(rèn)為它在近期是比較穩(wěn)定的，因此把它的變化周期擴(kuò)展為原來(lái)的兩倍。

增量式信息更新方法可以極大地減輕搜索引擎進(jìn)行索引信息庫(kù)維護(hù)的負(fù)擔(dān)。由于我們以系統(tǒng)信息更新周期作為度量文檔變化周期的基本時(shí)間單位，而且文檔變化周期只能是系統(tǒng)信息更新周期的2的冪次，因此可能會(huì)影響少量文檔索引信息的時(shí)效性。但是，考慮到WWW龐大的規(guī)模，從整體上看，增量式信息更新方法是一個(gè)能夠提高搜索引擎工作效率的有效手段。

總的說(shuō)來(lái)，在搜索引擎的發(fā)展過(guò)程中，雖然出現(xiàn)了上述眾多的技術(shù)來(lái)提高引擎工作效率，但不管是那種技術(shù)，短期內(nèi)，要完全使搜索引擎在實(shí)現(xiàn)技術(shù)上都超過(guò)人腦仍然是難以達(dá)到的。因此，人腦和電腦的分工和配合依然會(huì)是產(chǎn)生一個(gè)高質(zhì)量搜索引擎的最好保證，這也是今后搜索引擎的發(fā)展所必須要注意的重要事情。

參考文獻(xiàn)：

[1] 鳳元杰，劉正春，王堅(jiān)毅.搜索引擎主要性能評(píng)價(jià)指標(biāo)體系研究[J].情報(bào)學(xué)報(bào)，2004，23(1).

[2] 梁斌.走進(jìn)搜索引擎[M].北京:電子工業(yè)出版社，2007.10

[3] 徐寶文.搜索引擎與信息獲取技術(shù)[M].北京:清華大學(xué)出版社，2003.

[4] 邱哲，符滔滔.開發(fā)自己的搜索引擎[M].北京:人民郵電出版社，2007.

[5] Cay S.Horstmann JAVA2核心技術(shù) 卷II：高級(jí)特性[M].7版.北京:機(jī)械工業(yè)出版社，2006.