- 相關推薦
搜索引擎技術及趨勢
搜索引擎技術及趨勢隨著因特網的迅猛發展、WEB信息的增加,用戶要在信息海洋里查找信息,就象大海撈針一樣, 搜索引擎技術恰好解決了這一難題(它可以為用戶提供信息檢索服務)。目前,搜索引擎技術正成為計算機工業界和學術界爭相研究、開發的對象。
李曉明:1982年畢業于哈爾濱工業大學,1986年畢業于美國史蒂文斯理工學院計算機系,獲博士學位。現任北京大學計算機科學技術系教授,博士生導師,系主任. 研究方向為計算機并行與分布處理。
劉建國:北京大學計算機系副教授。
搜索引擎(Search Engine)是隨著WEB信息的迅速增加,從1995年開始逐漸發展起來的技術。據發表在《科學》雜志1999年7月的文章《WEB信息的可訪問性》估計,全球目前的網頁超過8億,有效數據超過9T,并且仍以每4個月翻一番的速度增長。用戶要在如此浩瀚的信息海洋里尋找信息,必然會"大海撈針"無功而返。搜索引擎正是為了解決這個"迷航"問題而出現的技術。搜索引擎以一定的策略在互聯網中搜集、發現信息,對信息進行理解、提取、組織和處理,并為用戶提供檢索服務,從而起到信息導航的目的。搜索引擎提供的導航服務已經成為互聯網上非常重要的網絡服務,搜索引擎站點也被美譽為"網絡門戶"。搜索引擎技術因而成為計算機工業界和學術界爭相研究、開發的對象。本文旨在對搜索引擎的關鍵技術進行簡單的介紹,以起到拋磚引玉的作用。
分 類
按照信息搜集方法和服務提供方式的不同,搜索引擎系統可以分為三大類:
1.目錄式搜索引擎:以人工方式或半自動方式搜集信息,由編輯員查看信息之后,人工形成信息摘要,并將信息置于事先確定的分類框架中。信息大多面向網站,提供目錄瀏覽服務和直接檢索服務。該類搜索引擎因為加入了人的智能,所以信息準確、導航質量高,缺點是需要人工介入、維護量大、信息量少、信息更新不及時。這類搜索引擎的代表是: YAHOO、Open Directory、Go Guide等。
2.機器人搜索引擎:由一個稱為蜘蛛(Spider)的機器人程序以某種策略自動地在互聯網中搜集和發現信息,由索引器為搜集到的信息建立索引,由檢索器根據用戶的查詢輸入檢索索引庫,并將查詢結果返回給用戶。服務方式是面向網頁的全文檢索服務。該類搜索引擎的優點是信息量大、更新及時、毋需人工干預,缺點是返回信息過多,有很多無關信息,用戶必須從結果中進行篩選。這類搜索引擎的代表是: 、Northern Light、Excite、Infoseek、FAST、 Lycos、GOOGLE;國內代表為:"天網"、悠游、OpenFind等。
3.元搜索引擎:這類搜索引擎沒有自己的數據,而是將用戶的查詢請求同時向多個搜索引擎遞交,將返回的結果進行重復排除、重新排序等處理后,作為自己的結果返回給用戶。服務方式為面向網頁的全文檢索。這類搜索引擎的優點是返回結果的信息量更大、更全,缺點是不能夠充分使用所使用搜索引擎的功能,用戶需要做更多的篩選。這類搜索引擎的代表是WebCrawler、InfoMarket等。
性 能 指 標
我們可以將WEB信息的搜索看作一個信息檢索問題,即在由WEB網頁組成的文檔庫中檢索出與用戶查詢相關的文檔。所以我們可以用衡量傳統信息檢索系統的性能參數-召回率(Recall)和精度(Pricision)衡量一個搜索引擎的性能。
召回率是檢索出的相關文檔數和文檔庫中所有的相關文檔數的比率,衡量的是檢索系統(搜索引擎)的查全率;精度是檢索出的相關文檔數與檢索出的文檔總數的比率,衡量的是檢索系統(搜索引擎)的查準率。對于一個檢索系統來講,召回率和精度不可能兩全其美:召回率高時,精度低,精度高時,召回率低。所以常常用11種召回率下11種精度的平均值(即11點平均精度)來衡量一個檢索系統的精度。對于搜索引擎系統來講,因為沒有一個搜索引擎系統能夠搜集到所有的WEB網頁,所以召回率很難計算。目前的搜索引擎系統都非常關心精度。
影響一個搜索引擎系統的性能有很多因素,最主要的是信息檢索模型,包括文檔和查詢的表示方法、評價文檔和用戶查詢相關性的匹配策略、查詢結果的排序方法和用戶進行相關度反饋的機制。
主 要 技 術
一個搜索引擎由搜索器、索引器、檢索器和用戶接口等四個部分組成。
1.搜索器
搜索器的功能是在互聯網中漫游,發現和搜集信息。它常常是一個計算機程序,日夜不停地運行。它要盡可能多、盡可能快地搜集各種類型的新信息,同時因為互聯網上的信息更新很快,所以還要定期更新已經搜集過的舊信息,以避免死連接和無效連接。目前有兩種搜集信息的策略:
● 從一個起始URL集合開始,順著這些URL中的超鏈(Hyperlink),以寬度優先、深度優先或啟發式方式循環地在互聯網中發現信息。這些起始URL可以是任意的URL,但常常是一些非常流行、包含很多鏈接的站點(如Yahoo。。
● 將Web空間按照域名、IP地址或國家域名劃分,每個搜索器負責一個子空間的窮盡搜索。
搜索器搜集的信息類型多種多樣,包括HTML、XML、Newsgroup文章、FTP文件、字處理文檔、多媒體信息。
搜索器的實現常常用分布式、并行計算技術,以提高信息發現和更新的速度。商業搜索引擎的信息發現可以達到每天幾百萬網頁。
2.索引器
索引器的功能是理解搜索器所搜索的信息,從中抽取出索引項,用于表示文檔以及生成文檔庫的索引表。
索引項有客觀索引項和內容索引項兩種:客觀項與文檔的語意內容無關,如作者名、URL、更新時間、編碼、長度、鏈接流行度(Link Popularity)等等;內容索引項是用來反映文檔內容的,如關鍵詞及其權重、短語、單字等等。內容索引項可以分為單索引項和多索引項(或稱短語索引項)兩種。單索引項對于英文來講是英語單詞,比較容易提取,因為單詞之間有天然的分隔符(空格);對于中文等連續書寫的語言,必須進行詞語的切分。
在搜索引擎中,一般要給單索引項賦與一個權值,以表示該索引項對文檔的區分度,同時用來計算查詢結果的相關度。使用的方法一般有統計法、信息論法和概率法。短語索引項的提取方法有統計法、概率法和語言學法。
索引表一般使用某種形式的倒排表(Inversion List),即由索引項查找相應的文檔。索引表也可能要記錄索引項在文檔中出現的位置,以便檢索器計算索引項之間的相鄰或接近關系(proximity)。
索引器可以使用集中式索引算法或分布式索引算法。當數據量很大時,必須實現即時索引(Instant Indexing),否則不能夠跟上信息量急劇增加的速度。索引算法對索引器的性能(如大規模峰值查詢時的響應速度)有很大的影響。一個搜索引擎的有效性在很大程度上取決于索引的質量。
3.檢索器
檢索器的功能是根據用戶的查詢在索引庫中快速檢出文檔,進行文檔與查詢的相關度評價,對將要輸出的結果進行排序,并實現某種用戶相關性反饋機制。
檢索器常用的信息檢索模型有集合理論模型、代數模型、概率模型和混合模型四種。
4.用戶接口
用戶接口的作用是輸入用戶查詢、顯示查詢結果、提供用戶相關性反饋機制。主要的目的是方便用戶使用搜索引擎,高效率、多方式地從搜索引擎中得到有效、及時的信息。用戶接口的設計和實現使用人機交互的理論和方法,以充分適應人類的思維習慣。 用戶輸入接口可以分為簡單接口和復雜接口兩種。
簡單接口只提供用戶輸入查詢串的文本框;復雜接口可以讓用戶對查詢進行限制,如邏輯運算(與、或、非;+、-)、相近關系(相鄰、NEAR)、域名范圍(如.edu、.com)、出現位置(如標題、內容)、信息時間、長度等等。目前一些公司和機構正在考慮制定查詢選項的標準。
未 來 動 向
搜索引擎已成為一個新的研究、開發領域。因為它要用到信息檢索、人工智能、計算機網絡、分布式處理、數據庫、數據挖掘、數字圖書館、自然語言處理等多領域的理論和技術,所以具有綜合性和挑戰性。又由于搜索引擎有大量的用戶,有很好的經濟價值,所以引起了世界各國計算機科學界和信息產業界的高度關注,目前的研究、開發十分活躍,并出現了很多值得注意的動向。
1.十分注意提高信息查詢結果的精度,提高檢索的有效性
用戶在搜索引擎上進行信息查詢時,并不十分關注返回結果的多少,而是看結果是否和自己的需求吻合。對于一個查詢,傳統的搜索引擎動輒返回幾十萬、幾百萬篇文檔,用戶不得不在結果中篩選。解決查詢結果過多的現象目前出現了幾種方法:一是通過各種方法獲得用戶沒有在查詢語句中表達出來的真正用途,包括使用智能代理跟蹤用戶檢索行為,分析用戶模型;使用相關度反饋機制,使用戶告訴搜索引擎哪些文檔和自己的需求相關(及其相關的程度),哪些不相關,通過多次交互逐步求精。二是用正文分類(Text Categorization)技術將結果分類,使用可視化技術顯示分類結構,用戶可以只瀏覽自己感興趣的類別。三是進行站點類聚或內容類聚,減少信息的總量。
2.基于智能代理的信息過濾和個性化服務
信息智能代理是另外一種利用互聯網信息的機制。它使用自動獲得的領域模型(如Web知識、信息處理、與用戶興趣相關的信息資源、領域組織結構)、用戶模型(如用戶背景、興趣、行為、風格)知識進行信息搜集、索引、過濾(包括興趣過濾和不良信息過濾),并自動地將用戶感興趣的、對用戶有用的信息提交給用戶。智能代理具有不斷學習、適應信息和用戶興趣動態變化的能力,從而提供個性化的服務。智能代理可以在用戶端進行,也可以在服務器端運行。
3.采用分布式體系結構提高系統規模和性能
搜索引擎的實現可以采用集中式體系結構和分布式體系結構,兩種方法各有千秋。但當系統規模到達一定程度(如網頁數達到億級)時,必然要采用某種分布式方法,以提高系統性能。搜索引擎的各個組成部分,除了用戶接口之外,都可以進行分布:搜索器可以在多臺機器上相互合作、相互分工進行信息發現,以提高信息發現和更新速度;索引器可以將索引分布在不同的機器上,以減小索引對機器的要求;檢索器可以在不同的機器上進行文檔的并行檢索,以提高檢索的速度和性能。
4.重視交叉語言檢索的研究和開發
交叉語言信息檢索是指用戶用母語提交查詢,搜索引擎在多種語言的數據庫中進行信息檢索,返回能夠回答用戶問題的所有語言的文檔。如果再加上機器翻譯,返回結果可以用母語顯示。該技術目前還處于初步研究階段,主要的困難在于語言之間在表達方式和語義對應上的不確定性。但對于經濟全球化、互聯網跨越國界的今天,無疑具有很重要的意義。
學 術 研 究
目前搜索引擎領域的商業開發非常活躍,各大搜索引擎公司都在投巨資研制搜索引擎系統,同時也不斷地涌現出新的具有鮮明特色的搜索引擎產品,搜索引擎已經成為信息領域的產業之一。在這種情況下,對搜索引擎技術相關領域的學術研究得到了大學和科研機構的重視。如Stanford大學在其數字圖書館項目中開發了Google搜索引擎,在Web信息的高效搜索、文檔的相關度評價、大規模索引等方面作了深入的研究,取得了很好的成果。NEC美國研究所的Steve Lawrence和C. Lee Giles 1998年和1999年連續兩年在《自然》和《科學》雜志上撰文對搜索引擎技術的研究進行評述。著名的信息檢索會議TREC也從1998年開始增加了Web Track課題,以考察Web文檔與其它類型文檔在檢索性質上的不同之處,并將測試在大規模的Web庫(如100G字節)上進行信息檢索的算法性能。由美國Infornotics公司主辦的搜索引擎國際會議從1996年開始,每年舉行一次,對搜索引擎技術進行總結、討論和展望,參加者有著名的搜索引擎公司、大學和研究機構的學者,對搜索引擎技術起到了很好的推動作用。另外象IEEE主辦的國際萬維網會議、人機交互會議已有越來越多關于搜索引擎技術研究的文章發表。
國內先后有北京大學、清華大學、國家智能研究中心等高校和研究單位對搜索引擎技術開展研究,并開發出了幾個較好的系統。如由北京大學計算機系網絡研究室開發的"天網"中英文搜索引擎http://pccms.pku.edu.cn:8000/gbindex.htm),在系統規模及系統性能方面達到了國外中型搜索引擎系統的技術水平,為國內用戶提供了很好的互聯網搜索服務,受到了用戶的好評。
【搜索引擎技術及趨勢】相關文章:
搜索引擎中的網絡蜘蛛技術探析03-22
審計技術與方法發展的新趨勢03-22
移動通信技術的發展趨勢03-28
論數控技術的發展趨勢03-22
探析移動通信技術的發展趨勢03-20
指紋采集技術及其產品發展趨勢03-18
程控交換機的特點與技術趨勢分析03-14
關于電影放映技術更新及其發展趨勢03-15
淺析光纖通信技術的特點和發展趨勢03-20