【第170期 November 5, 2011】 |
||
|
 |
研發新視界[發表日期：2011/11/5] 前言  《圖一》搜尋引擎基本架構 搜尋引擎就是針對抓回來的資料作全文檢索；使用者在Query Interface輸入查詢，而伺服器端藉由Traversal Robot來將網路上的網頁抓取下來，在解析其內容後，在資料庫建立Indexing File。接收到使用者的查詢後，在分析其查詢，就可以至Indexing File中找到符合其查詢的檔案，其架構如圖一所示。 搜尋引擎不斷的在技術上精進，以便達到更佳的搜尋結果，以下便介紹在搜尋引擎中所使用到的主要技術。 WWW robots (spiders, wanders, crawlers, walkers, ants) 而將網路上的網頁抓下來的程式稱作為robots，大多人以web crawlers稱呼。Web crawler 的工作原理非常簡單，就像一般使用者上網路一樣，例如我們連到Yahoo!的首頁，我們第一步會先看看首頁上面有什麼內容，找找看有沒有我們要的東西（文字或是圖片、影像），如果沒有的話就再看看旁邊的連結，找到相關的連結點選滑鼠連進去觀看，就這樣反覆的直到找到我們需要的資料或是失去耐心。 就網頁伺服器來說，客戶端的對象是人，而Web crawler的目的就是利用程式來代替人的角色，讓程式連到我們所要蒐集資料的網站，然後沿著每個頁面的連結，將文字資料或是圖片抓取回來，將資料直接存入資料庫。 當我們利用瀏覽器拜訪一個網站是，瀏覽器會為我們發出這樣的 request：  瀏覽器送出的 request 可分為兩部分，一部份是需求標頭，另一部份是需求主體，上面就是一個需求標頭的例子。當網頁伺服器收到我們的請求之後，會送回適當的HTTP回覆：  知道HTTP協定的工作方式之後，便可以對Web Crawler給定一個起始的網址（Seed Url），Web Crawler對網頁伺服器發出 HTTP request，在根據伺服器端傳送回來的資料分析，從抓回的資料中取出頁面上的連結（就是 <a href="http://some.host.com">Link</a>這樣的連結標籤），這些連結便可以做為Web Crawler下次參訪的網址，其架構如圖二所示。 《圖二》Web Crawlers架構 Ranking of Search Engine 在擁有大量的網頁資料後，搜尋引擎便需要根據使用者的查詢來找出並且排序其重要性和相關性。 如果某一網頁包含查詢中的主題，便可以認為其網頁與其查詢相關。搜尋引擎可以利用各式各樣的文字比對方法來衡量所有網頁的相關性：像是查詢出現在瀏覽器的標頭、是否為粗體字、或是文字在網頁中出現的比率。一般來說，可以利用tf-idf（Term frequency-Inverse document frequency）演算法，利用網頁中重複出現的字詞來衡量相關性。 Google創辦人Larry Page及Sergey Brin在1998年發表了搜尋引擎的排名演算法PageRank。這個演算法導入了隨機瀏覽的概念，即有人上網無聊隨機打開一些頁面，點一些連結。一個頁面的PageRank值也影響了它被隨機瀏覽的機率。為了便於理解，這裡假設上網者不斷點網頁上的連結，最終到了一個沒有任何鏈出頁面的網頁，這時候上網者會隨機到另外的網頁開始瀏覽。 為了對那些有連結的網頁公平，q = 0.85（這裡的q被稱為阻尼係數（damping factor），其意義是，在任意時刻，假想的隨機瀏覽者停止在某頁面後繼續瀏覽的機率。）的演算法被用到了所有頁面上，估算頁面可能被上網者放入書籤的機率。所以，這個等式如下：  p1,p2,...,pN是被研究的頁面，M(pi)是鏈入pi頁面的數量，L(pj)是pj鏈出頁面的數量，而N是所有頁面的數量。PageRank值是一個特殊矩陣中的特徵向量。這個特徵向量為：  如果pj不鏈向pi，而且對每個j都成立時，  等於0。 所以一個頁面的PageRank是由其他頁面的PageRank計算得到。Google不斷的重複計算每個頁面的PageRank。如果給每個頁面一個隨機PageRank值（非0），那麼經過不斷的重複計算，這些頁面的PR值會趨向於正常和穩定。 故每個網頁都可以算出一個PageRank值來衡量每個網頁的重要性，也就是說如果有一網頁有許多的鏈結指向這個網頁，便可以代表這個網頁重要性越高。 參考資料 ‧http://en.wikipedia.org/wiki/Web_crawler ‧http://en.wikipedia.org/wiki/Search_engine_optimization ‧http://zh.wikipedia.org/zh-hant/PageRank
|
 |
友善列印
轉寄友人