Web搜索引擎技術研究

申 健，柴艷娜

(長安大學 教育技術與網絡中心，陜西 西安 710064)

Web搜索引擎技術研究

申 健，柴艷娜

(長安大學 教育技術與網絡中心，陜西 西安 710064)

科技的進步導致了互聯網中的信息以指數級速度增長。如何有效地管理和組織信息，幫助用戶在海量的信息里獲取有用的信息，并快速定位和索引，既是搜索引擎的目標，也是搜索引擎能夠成為網絡用戶不可或缺的基礎工具的原因。對搜索引擎技術進行了研究，討論其內在原理和運行機制，分析其技術架構和信息抓取方法，并從工作原理上對其采用的算法和策略進行了分析。同時，對實際中Google搜索引擎所采用的核心技術和算法進行研究并與傳統技術進行了對比，分析其所具備的先進性。另外，對搜索引擎工作流程涉及到的索引問題、SEO等都分別進行了探討。指出信息檢索工具對于海量信息數據處理的重要性，以及在信息檢索方面搜索引擎體現的優越性，它的不斷發展必將帶動信息科學的進步。

搜索引擎；蜘蛛；檢索排序；SEO

0 引 言

全球互連網革命所引發的的信息浪潮已經使互聯網成為海量信息的重要來源地。搜索引擎作為互聯網用戶必不可少的信息獲取工具，其主要作用是運用專門的策略和程序從網絡上尋找、收集、提取、匯總、排序和處理信息，向用戶提供數據信息檢索服務和導航服務，將最終內容顯示給用戶的系統。經過調查，網絡信息搜索在互聯網服務中已經成為繼E-mail后的第二大應用[1]。

目前，常用的搜索引擎有全文索引、目錄索引、元搜索引擎等，其中Google、Bing、Yahoo和Baidu等則是搜索引擎的代表。

1 搜索引擎架構

搜索引擎(Search Engines)是指在互聯網環境中能夠響應用戶提交的搜索請求，通過已經制定好的策略和程序從互聯網上搜集信息，對信息進行處理和歸納，并將檢索相關的結果展示給用戶的提供檢索服務的系統。這類系統一般由搜集、整理和查詢三個模塊組成[2]。

在搜索引擎的結構和執行模式的設計中，將信息檢索系統內許多有價值的經驗吸收進來，并且通過兩種系統使用用戶的不同，針對他們的特點進行了許多修改。搜索引擎系統的內容處理功能和查詢功能同一般信息檢索系統類似，在對繁雜數據對象的處理方面搜索引擎對系統結構進行了針對性的調整，以適應處理數據和用戶查詢的需要[3]。圖1為搜索引擎系統架構。

圖1 搜索引擎架構

1.1 搜索引擎的工作原理

搜索引擎的工作原理如圖2所示。

圖2 搜索引擎工作原理示意圖

首先，利用網絡蜘蛛進行全網搜索，自動抓取網頁；其次，對獲取到的網頁信息進行索引，同時記錄與檢索有關的信息(如果是中文搜索引擎就需要中文分詞)；最后，接收用戶查詢請求，按照設定好的參數對索引文件進行計算，并將結果向用戶顯示。簡單概括為：抓取網頁→建立索引數據庫→在數據庫中排序→結果反饋。搜索引擎抓取數據與分析過程如圖3所示。

1.2 網絡蜘蛛

它是按照一定的規則，自動抓取萬維網信息的程序或者腳本的半自動化資源獲取方式[4]，因為尚未對獲取的數據進行處理，所以只能稱作是一種半自動化的資源而不是信息。半自動化是指需要人工指定起始網絡資源(Uniform Resource Locator，URL)進行搜索，并按照URL的結果指向獲取網絡資源，然后分析、獲取與該資源有關的所有其他資源。例如Google，它利用蜘蛛程序獲取資源，先由一個管理程序進行任務分配并處理結果，然后由多個分布式的蜘蛛程序接受任務，最后將獲取的資源作為結果返回，再重新獲得任務。

圖3 搜索引擎的數據與分析過程

搜索引擎的蜘蛛抓取網頁有一定的規律，主要有以下幾種策略：

(1)深度優先搜索策略。網絡蜘蛛通過頁面發現的一個鏈接，順著鏈接的頁面又發現一個鏈接，并且將發現的頁面全部抓取。

(2)寬度優先搜索策略。先搜索完一個Web頁面中所有的超級鏈接，然后再繼續搜索下一層,直到底層為止并進行抓取。

(3)權重優先策略。即深度優先+寬度優先。參照鏈接的權重進行網絡抓取，對權重高的鏈接采用深度優先策略，而對權重低的鏈接則采用寬度優先策略。也就是綜合層次的多與少以及這個鏈接的外鏈多少與質量等因素獲取鏈接的權重。

(4)重訪抓取策略。包括全部重訪與單個重訪。

1.3 建立索引

建立索引數據庫的過程是利用索引器從搜索器搜索到的資源中抽取信息，建立檢索所需的索引表[5]。

通常情況下，網絡蜘蛛抓獲的資源需要去掉控制代碼和其他不相關信息，提取有用信息并通過模型將信息表示出來，這樣能夠使查詢結果更為準確。就像網頁上的信息是以Web形式進行表現，在查詢結果的頁面中網頁要生成摘要，摘要會向用戶顯示網頁的大概內容，并將模型化的信息存放在臨時數據庫中。網頁上的數據量非常巨大，為提高檢索效率，搜索引擎會按照設定好的規則對資源建立索引。不同的搜索引擎會分別按照全文索引、無用詞匯過濾，或者根據meta信息建立索引。在該過程中，需要進行的資源分析處理可概括為以下幾個方面：

(1)網頁結構化。即將html代碼全部刪掉，提取出內容。

(2)消噪。留下網頁的主題內容，刪掉沒用的內容。

(3)查重。由搜索引擎查找重復的網頁與內容，如果找到重復的頁面與內容，即刪除。

(4)分詞。提取出正文的內容，將其分成N個詞語，并排列出來，存入索引庫，同時計算該詞在頁面出現的頻率。

(5)鏈接分析。分析頁面的反向鏈接數、導出鏈接數以及內鏈數，然后鏈接加上權重等。

(6)用戶查詢(Query)解析。最大可能地分析 出用戶想要表達的查詢目的，然后將用戶的需求轉化成信息模型供數據庫檢索使用；根據用戶的需求模型，在索引數據庫中找出結果；對結果進行排序。由于Web數據的內容量大、結果模糊性高，檢索結果通常很多，如何將用戶感興趣的結果排在前面去設計結果集的排序算法十分重要。

2 搜索索引

搜索索引的核心結構是倒排索引，如圖4所示。

倒排索引實際應用中需要根據非主屬性(也叫副鍵)值來查找記錄，其特殊性在于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，帶有倒排索引的文件稱作倒排文件，即次索引。文檔的關鍵詞作為索引(就像普通書籍中索引是關鍵詞，頁面符號是目標)，文檔就是索引目標的一種結構。

圖4 倒排索引

倒排索引是以倒排索引包括所有副鍵值，并列出相關的記錄主鍵值，它主要應用于復雜查詢。與通常的結構化查詢語言(SQL)的差別在于，搜索引擎收集完數據后在預處理的步驟，通常利用高效的數據結構來提供檢索服務，而現階段“倒排索引”就是效率最高的數據結構。

2.1 構建索引

1)簡單法。

構建索引就是從正排表到倒排表的建立過程。首先對網頁進行分析，建立以網頁為主碼的索引表[6]；其次在索引建立完成后得到倒排表。構建倒排索引的具體流程如圖5所示。

圖5 倒排索引構建示意圖

流程描述如下：

(1)將文檔分析用term標記；

(2)利用hash去重單詞term；

(3)生成倒排列表。

倒排列表就是文檔編號DocID，不包含其他信息(詞語的頻率、位置等)，這就是簡單索引。簡單索引的功能可以用在數據量小的內容，例如對幾千個文檔進行索引。不過它有兩點限制：

(1)需要足夠大的內存空間存儲倒排表。對于搜索引擎來說，都是以G為單位的數據量，在其規模不斷擴大的同時不能確保內存的空間能夠得到相應的增長。

(2)算法是按照一定順序來執行，對于并行處理造成不便。

2)合并法。

即歸并法。每一次內存數據在寫入磁盤的時候，包括詞典在內的所有中間結果信息都被寫入磁盤，這樣內存中的所有內容都被清空，之后建立的索引可以使用全部的內存空間。合并流程如下：

(1)頁面分析。首先生成臨時倒排數據索引A和B，一旦索引A和B占滿內存空間后，將索引A和B寫入臨時文件來生成臨時倒排文件。

(2)多路歸并。對已經生成的臨時文件來執行多路歸并，得到最終的倒排文件(invertedfile)。

在創建索引的過程中，頁面分析特別是中文分詞是消耗時間的主要步驟，而第二步就快得多了，對創建算法進行優化重點在于提高中文分詞的效率。

2.2 更新策略

包括四個方面：完全重建策略、再合并策略、原地更新策略以及混合策略。

(1)完全重建策略。一旦新增文檔滿足一定數量標準，就對新增文檔和原文檔進行整合，再對生成的文檔創建靜態索引，保留新建索引并刪除原索引。此法代價高，但是主流商業搜索引擎一般采用此方式來維護索引的更新[7]。

(2)再合并策略。對進入系統的新文檔進行解析，更新內存中保留的臨時索引，在文檔中每個單詞的倒排列表末尾追加倒排表列表項；當臨時索引占消耗完指定內存后，進行索引合并，這里需要倒排文件里的倒排列表存放順序是按照索引單詞字典順序由低到高排序，這樣按順序可以直接掃描合并。其缺點是：在生成新的倒排索引文件時，會將老索引倒排列表中很多未發生變化的單詞也取出并寫入新索引中，這樣增加了對磁盤的消耗。

(3)原地更新策略。基本出發點，可以認為是試圖改進再合并策略的缺點，在原地合并倒排表，這需要預留空間給未來插入，如果預留的空間不夠就要進行遷移。遷移的過程中會破壞老索引中某些單詞的連續性，不能順序進行讀取，并且需要足夠大的磁盤連續存儲。實際操作中表明，其原地更新的效率比再合并策略要低。

(4)混合策略：其目地是將不同策略的優勢結合到一起，混合其他索引更新策略，形成一種更加高效的方法。

3 Google搜索引擎

3.1 Google技術

“完美的搜索引擎”是Google堅持的開發目標。正如公司創始人之一Larry Page所定義的那樣，可以“確解用戶之意，切返用戶之需”。為了能夠達到這個目標，Google堅持“不受現有模型限制，不斷追求創新”，通過開發具有自身特色和突破性的服務基礎結構和Page Rank技術，從而根本性地改變基于互聯網的信息搜索方式。

為此，Google開發人員采用了一種全新的服務器設置，利用相互鏈接的PC來快速查找每個搜索答案，以最快的速度為用戶提供最精確的搜索結果的設計理念，從而避免了因使用少量大型服務器導致搜索引擎在訪問高峰期相應速度會減慢的缺陷。應用這種技術能夠降低成本、縮短響應時間、提高可擴展性。與此同時，Google對其內部技術的持續改進使得該技術的效率得到不斷提升。

Google搜索技術的特點是利用的軟件能夠在同一時間進行一系列運算，且都能在很短的時間內完成；Page Rank技術通過對整個網絡鏈接進行檢查，依據每個網頁的重要性進行排序；進行超文本匹配分析，判斷出預指定搜索有關聯的網頁；綜合考慮特定查詢與整體重要性的相關性，將關系最密切并且可靠性最強的結果放在首位。與此不同的是，普通搜索引擎一般都是以網頁上文字的出現頻率高低作為排序的重要依據。

3.2 Google搜索關鍵技術

1)Page Rank技術。

Page Rank(網頁排名)是根據網頁之間相互的超鏈接計算的技術，讓鏈接來“投票”。其特點是：

(1)不計算直接鏈接的數量，而是將從網頁A指向網頁B的鏈接解釋為由網頁A對網頁B所投的一票[8]，頁面的超鏈接就表示對該頁面投一票，頁面的重要性由它的“得票數”來決定；

(2)通過對投票價值的評估，擁有較高投票價值的網頁可以獲得較高的評價；

(3)重要網頁的網頁排名高，顯示在搜索結果的較高處；

(4)利用反饋的綜合信息確定單個網頁的重要性；

(5)沒有人為因素干擾到搜索結果。

Google能夠成為一個公正的、得到用戶信任的、不受付費排名影響的客觀信息來源，這個技術起到了重要的推動作用。

GooglePageRank技術的PR值算法如式(1)所示[9]：

PR(A)=

(1)

其中，PR(A)指網頁A的佩奇等級(PR值)；PR(B)，PR(C)，…，PR(N)表示鏈接網頁A的網頁N的佩奇等級(PR)；N是鏈接總數，這個鏈接可以是來自任何網站的導入鏈接(反向鏈接)；L(N)是網頁N往其他網站鏈接的數量(網頁N的導出鏈接數量)；q是阻尼系數，介于0～1之間，Google設為0.85[10]。

2)超文本匹配分析。

Google的搜索引擎也對網頁文本內容進行分析。它并不僅僅只局限于網頁文本的掃描方式，還對包括本網頁和相鄰網頁的字體、分區和文字精確位置等等內容進行分析，以確保向用戶反饋查詢最匹配的結果[11]。

對于通過便攜式終端訪問網絡的用戶，Google推出了行業內第一款無線搜索技術，將HTML即時轉換為針對WAP、I-mode、J-SKY和EZWeb優化的格式[12]，保障用戶能夠快速獲得精確的搜索結果，這是一項并不限于臺式機的創新。

3)查詢的全過程。

Google查詢過程需要在短時間內(一般不超過0.5s)完成多個步驟，而后將搜索結果向用戶顯示。

(1)服務器將查詢內容發送給索引服務器。索引服務器所包含的內容與索引目錄相似，即顯示與查詢內容匹配的都有哪些網頁。

(2)查詢內容傳輸到文檔服務器，后者檢索存儲的文檔，然后生成描述結果的摘錄。

(3)返回用戶需要的搜索結果。

4 SEO優化

SEO(Search Engine Optimization，搜索引擎優化)是指在了解搜索引擎自然排名機制的基礎上，利用搜索引擎的搜索規則來提高目前網站在有關搜索引擎內的自然排名，以獲得更多流量，實現網絡營銷及品牌建設的目標[13]。它能夠使網站更適合搜索引擎的索引原則，這樣不僅在用戶面前提高了搜索引擎的效果，還會使顯示的網站相關信息對用戶來說更具有吸引力。

搜索引擎SEO的搜索方法如圖6所示。

圖6 SEO搜索方法

5 結束語

Internet提供了多種不同的檢索工具，它們有各自的語言、數據庫、檢索功能和顯示方式，對于用戶來說了解這些工具的性能，掌握檢索技巧，提高檢索命中率是最重要的。掌握了方法與技巧并且經常進行實踐操作，就能夠方便快捷地利用搜索引擎獲取更多符合需求的有價值的信息。

目前，搜索引擎在擴大覆蓋范圍的同時，正在趨向個性化、智能化、專業化、多媒體、多語言搜索和實用性的模糊檢索方面發展，并已取得了較大技術進步。隨著需求的提高和互聯網技術的發展，不斷應用新的技術和策略，搜索將會向著更加方便、快速、準確的目標前進，這已成為搜索引擎的發展方向[14]。

[1] 梁 斌.走進搜索引擎[M].北京:電子工業出版社,2007.

[2] 吳澤欣.搜索引擎優化入門與進階[M].北京:人民郵電出版社,2008.

[3] 盧 亮.搜索引擎原理、實踐與應用[M].北京:電子工業出版社,2007.

[4] Lawrence S,Giles C L.Accessibility of information on the web[J].Nature,1999,400(6740):107-109.

[5] Lawrence S,Giles C L.Searching the World Wide Web[J].Journal of the American Society for Informationence & Technology,1998,280(1):8-14.

[6] 張園園.基于用戶興趣的個性化搜索引擎的分析與研究[D].秦皇島:燕山大學,2006.

[7] 王 濤.基于行業的個性化搜索引擎的應用[D].北京:北方工業大學,2008.

[8] Vazirgiannis M,Drosos D,Vlachou A,et al.Web page rank prediction with Markov models[C]//WWW 2008.Beijing,China:ACM,2008.

[9] Wills R S.Google's page rank:the math behind the search engine[J].The Mathematical Intelligencer,2006,28(4):6-11.

[10] Lo S.全球最強搜索引擎谷歌Google[M].上海:上海財經大學出版社,2007.

[11] 林 中.Google搜索引擎的關鍵詞檢索[J].中國信息導報,2003(3):60-61.

[12] 陳 鋼.搜索引擎優化寶典[M].北京:清華大學出版社,2009 .

[13] 周元興.Google入門與實例教程[M].北京:電子工業出版社,2007.

[14] 萬勝林,王祖榮.搜索引擎的類型及其功能分析[J].中國信息導報,2003(5):52-54.

Research on Web Search Engine Technology

SHEN Jian,CHAI Yan-na

(Education Technology and Network Center,Chang’an University,Xi’an 710064,China)

Information in Internet is exponential growth with the development of science and technology.There should be a tool to help users to manage the big data effectively and get the useful information what they want,and locate and index information quickly and properly,which is the target of search engine,and why search engine has been an essential tool in daily life.The search engine technologies are researched and their internal principle and mechanism are discussed,and their technical architecture and the information retrieval are analyzed.In the working principle,the relative algorithm and strategy is studied.At the same time,the core technology and algorithm adopted by Google’s search engine are studied and compared with the traditional technology,analyzing their superiority.In addition,the indexes and SEO the search engine working process involves are discussed respectively.It is pointed out that the information retrieval tools are important for huge amounts of information processing and advanced in information retrieval,the development of which will drive the progress of information science.

search engine;spider;index sorting;SEO

2016-01-06

2016-05-11

時間：2016-11-22

陜西省信息化重點建設項目(2171-20120042)

申 健(1980-)，男，碩士，工程師，研究方向為計算機網絡技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1233.050.html

TP31

A

1673-629X(2016)12-0030-05

10.3969/j.issn.1673-629X.2016.12.007