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

　　關鍵詞：搜索引擎,聚類,相關度

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

　　1基于超鏈的相關度排序

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

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

　　2檢索結果的聯(lián)機聚類

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

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

　　3基于概念的檢索

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

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

　　1)手工建立詞典來存儲概念層次及詞條之間的交叉聯(lián)系，該工作通常由領域專家來完成。

　　2)使用語法分析、統(tǒng)計等技術從文檔集合中自動學習。

　　4相關度反饋

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

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

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

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

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

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

　　一些研究和實驗結果表明，利用相關度反饋可以較好地改進檢索效果。但是，目前很少有搜索引擎支持該功能。其原因可能是因為相關度反饋需要用戶的參與，而普通用戶在使用搜索引擎時不太愿意花時間利用這些附加功能。

　　5分詞技術

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

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

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

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

　　一個文檔的變化周期就是它相鄰的兩次變化之間的時間間隔。

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

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

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

　　/*假設當前正在進行的是第k(k≥1)次信息更新過程。*/

　　Begin

　　While（索引信息庫中還有文檔信息的有效性沒有驗證時）{任取一個未驗證的文檔作為當前文檔;

　　If（當前文檔的變化周期f是k的因子）Then

　　{驗證當前文檔的有效性;

　　If（當前文檔已不能被訪問）Then

　　從索引信息庫中刪除對應的記錄

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

　　{把當前文檔URL加入到目標列表;

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

　　}

　　Else

　　把當前文檔的變化周期修改為2f;

　　}

　　以目標列表中的URL作為瀏覽起點，啟動機器人開始新一輪信息收集工作;

　　End[5]

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

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

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

　　參考文獻：

　　[1]鳳元杰,劉正春,王堅毅.搜索引擎主要性能評價指標體系研究[J].情報學報,2004,23(1).

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

　　[3]徐寶文.搜索引擎與信息獲取技術[M].北京:清華大學出版社,2003.

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

　　[5]CayS.HorstmannJAVA2核心技術卷II：高級特性[M].7版.北京:機械工業(yè)出版社,2006.

---

轉載請注明來自：http://www.jinnzone.com/jisuanjiwangluolw/23520.html