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

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

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

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

　　排序搜索引擎的檢索結(jié)果往往過于龐大，用戶一般只會瀏覽前面的一部分結(jié)果。通過對檢索結(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)度高的頁面不一定是用戶普遍歡迎的頁面；另一方面，有些Web頁面的作者利用上述因素來欺騙搜索引擎（spamming），以提高其頁面的排序。

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

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

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

　　為了方便用戶的瀏覽，一些研究人員開始將聚類技術(shù)用于Web信息檢索結(jié)果的可視化輸出。聚類是指將文檔集合分成若干個(gè)簇，要求同一簇內(nèi)文檔內(nèi)容的相似度盡可能地大，而不同簇間的相似度盡可能地小。Hearst等人的研究已經(jīng)證明了“聚類假設(shè)”，即與用戶查詢相關(guān)的文檔通常會聚類得比較靠近，而遠(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í)，可以對該簇中的文檔再次聚類得到若干個(gè)子簇(Si，1，…，Si，j，…，Si，n)，直到用戶滿意為止[2]。。Etzioni等人的實(shí)驗(yàn)結(jié)果表明，使用一些改進(jìn)算法來對檢索結(jié)果進(jìn)行聯(lián)機(jī)聚類不但是可行的，而且十分有效。

　　3基于概念的檢索

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

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

　　1)手工建立詞典來存儲概念層次及詞條之間的交叉聯(lián)系，該工作通常由領(lǐng)域?qū)＜襾硗瓿伞?/p>

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

　　4相關(guān)度反饋

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

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

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

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

　　3)系統(tǒng)根據(jù)用戶的反饋對查詢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)。

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

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

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

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

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

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

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

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

　　Begin

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

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

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

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

　　從索引信息庫中刪除對應(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)，啟動機(jī)器人開始新一輪信息收集工作;

　　End[5]

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

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

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

　　參考文獻(xiàn)：

　　[1]鳳元杰,劉正春,王堅(jiān)毅.搜索引擎主要性能評價(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]CayS.HorstmannJAVA2核心技術(shù)卷II：高級特性[M].7版.北京:機(jī)械工業(yè)出版社,2006.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiwangluolw/23520.html