1 下載--構建網絡爬蟲

1.1 圖遍歷算法的取舍

從理論上講，廣度優先搜索（BFS）和深度優先搜索（DFS）算法的時間復雜度都是 O（n + e），不同的算法爬下整個靜態網頁的內容所用的時間是相同的。但在現實生活中，時間有限，互聯網時刻變化。所以應該考慮有限時間里盡可能多的爬下最重要的網頁，一個網站中最重要的網頁應該是它的首頁以及首頁所連接的頁面，BFS 明顯優于 DFS.但實際的網絡爬蟲都是由很多服務器組成的分布式系統，這些下載服務器和網絡服務器建立通信需要額外時間，這時就需要用到 DFS 以避免握手次數過多。

1.2 提取URL并做出URL表

有些頁面的 URL 以文本形式存儲在頁面中，有明顯標識；而有些時候需要模擬瀏覽器運行才可以提取到頁面中隱含的 URL.但在互聯網這張大圖上，一個頁面可能被多個頁面所指向，遍歷時，為了防止一個網頁被重復下載，這時就需要一個哈希表做記錄，即遇到一個網頁，首先查找判斷 URL 是否在表中，若存在直接跳過，若不存在，下載頁面并將這個頁面的 URL 存入哈希表中。但是如果同時有上千臺服務器一起下載網頁，為了避免不同服務器重復判斷一個 URL,要注意存儲哈希表的服務器的通信問題。第一，調度系統要明確每臺下載服務器的分工，減少 URL 的重復判斷次數；第二，盡可能使用批處理，每次向哈希表發送一批詢問和更新一批內容，減少通信次數。

2 索引--布爾代數

索引是基于數據庫的，數據庫的 SQL 查詢背后的基本原理是布爾運算，支持各種復雜的邏輯組合，而今天的搜索引擎即是把用戶輸入的自然語言查詢轉換成布爾代數。最簡單的索引結構就是一串很長的二進制數，這個數的位數代表有多少網頁，每一位對應一個頁面，1 代表這個頁面中有這個關鍵字，0 代表沒有。比如查詢“寵物沐浴液”,關鍵字“寵物”對應的二進制數是 100011010000000…，表示第一、第五、第六、第八個頁面包含這個關鍵字；關鍵字“沐浴液”對應的二進制數是011010010000000…，要篩選出同時包含“寵物”和“沐浴液”網頁時，只需將這兩個數進行布爾運算 AND,結果為 000010010000000…，可知第五、第八個頁面滿足要求。綜上，互聯網搜索引擎的索引是一張大表，每一行是一串二進制數字，表示包含某個關鍵詞的頁面序號。

3 排序--網頁質量的度量

PageRank 的核心思想：一個頁面用戶訪問的越多質量越高，而用戶在瀏覽網頁時主要通過超鏈接進行頁面跳轉，因此我們需要通過分析超鏈接組成的拓撲結構來推算網頁被訪問的頻率。其中，指向這個網頁的其他頁面本身也有一個自己的權重。一個網頁的 PageRank值應該來源于所有指向這個網頁的其他頁（X1,X2,…，.Xk）的權重（Y1,Y2,…，.Yk）之和，即

對矩陣 A 按行切分 10 份，對矩陣 B 按列切分 10 份。每個結果的計算量都是最后結果的十分之一，用 10 倍的空間復雜度縮短 10 倍的時間復雜度。MapReduce 即是把一個大任務分成多個子任務，分布到不同的計算機中計算，最后再將中間結果合并成最終結果。

4 結語

在搜索引擎中，給定一個特定查詢，有關網頁的排名大致由相關性和網頁本身質量所確定。但是任何搜索產品給出的結果都不完美，排名靠前的不一定是高質量的，而是商業氣息很濃的。針對 PageRank 算法會出現很多賣鏈接的網站，解決辦法主要用到余弦定理和圖論中的 Clicque 算法。即便是有好的算法來衡量網頁質量和查詢相關性，但搜索反作弊仍舊是一個長期的任務，需要不斷的消除“噪音”,才能提高搜索引擎的質量。