目錄

【1】搜索引擎概述

【2】搜索引擎的基礎(chǔ)技術(shù)

【3】搜索引擎的平臺基礎(chǔ)

【4】搜索結(jié)果的改善優(yōu)化

__________________________________________________

【1】搜索引擎概述

過去的15年間，互聯(lián)網(wǎng)信息急劇膨脹，靠人工的方式去篩選獲取有用信息不再可能，因此搜索引擎應(yīng)運(yùn)而生。根據(jù)其發(fā)展，可以將其劃為四個時代。

• 分類目錄。yahoo是這個時期的代表，采用純?nèi)斯し绞绞占?#xff0c;質(zhì)量較高，但效率低。

• 文本檢索。采用了經(jīng)典的信息檢索模型，主要查詢用戶關(guān)鍵詞語網(wǎng)頁內(nèi)容相似度，收錄容量增加，但質(zhì)量不是很好。如，早期的AltaVista.

• 鏈接分析。典型：Google的PageRank，極大擴(kuò)充了網(wǎng)頁內(nèi)容，質(zhì)量有提高，隨之而來各種作弊方法。

• 用戶為中心？現(xiàn)在的大部分搜索引擎對相同查詢返回相同的結(jié)果，但是不同用戶可能關(guān)注不一樣，未來也許更多考慮用戶的差異性。

說到發(fā)展，不得不提搜索引擎的三個主要目標(biāo)，無論它往何方發(fā)展，以下三個目標(biāo)總是一個很好的評估標(biāo)準(zhǔn)：

• 更全：如何把更多相關(guān)的網(wǎng)頁收錄？

• 更快：如何從數(shù)以億計的網(wǎng)頁中迅速返回結(jié)果？

• 更準(zhǔn)：如何把用戶最感興趣的結(jié)果呈現(xiàn)？

【2】搜索引擎的基礎(chǔ)技術(shù)

這一部分主要從以下四個部分來講述搜索引擎的基礎(chǔ)技術(shù)，這四個部分也是搜索引擎的重要環(huán)節(jié)。

• 網(wǎng)絡(luò)爬蟲

• 建立索引

• 內(nèi)容檢索

• 鏈接分析

2.1 網(wǎng)絡(luò)爬蟲?

網(wǎng)絡(luò)爬蟲是搜索引擎的下載系統(tǒng)，它的作用是內(nèi)容的獲取，手段就是在萬維網(wǎng)中通過鏈接不斷爬取收集各類網(wǎng)頁。但是互聯(lián)網(wǎng)的頁面浩如煙海，而且每天不斷有新的內(nèi)容產(chǎn)生，根據(jù)爬取目標(biāo)和范圍，可以將爬蟲簡單分為以下幾類：

• 批量性爬蟲：明確的抓取目標(biāo)和范圍，達(dá)到即停止

• 增量型爬蟲：應(yīng)對網(wǎng)頁不斷更新的狀態(tài)，爬蟲需要及時反應(yīng)。通用商業(yè)引擎一般都是這類

• 垂直型爬蟲：只針對某個特定領(lǐng)域的爬蟲，根據(jù)主題過濾。

爬蟲在爬取網(wǎng)頁的時候，應(yīng)該怎樣確定下一步的目標(biāo)呢？主要有以下策略：

• 寬度優(yōu)先：最簡單的方式，即將某個頁面中的鏈接依次加入待爬取隊列

• 局部PageRank：PageRank是一種網(wǎng)頁重要性指標(biāo)，這種方式根據(jù)一定時期內(nèi)的局部PageRank值決定下一步爬取目標(biāo)

• OPIC：當(dāng)下載當(dāng)前網(wǎng)頁后，將其重要性平均分給包含的鏈接，每次選取最重要的頁面，不用迭代計算，速度較快

• 大站優(yōu)先：思想很簡單，以網(wǎng)站為單位衡量頁面重要性。

接下來，簡要介紹一下搜索引擎中的一個重要問題：暗網(wǎng)抓取。所謂暗網(wǎng)，是指常規(guī)方式很難爬到的網(wǎng)頁，而在網(wǎng)絡(luò)中，這樣的網(wǎng)是大量存在的。有的網(wǎng)頁沒有外鏈，有的主要內(nèi)容存儲于數(shù)據(jù)庫中(如攜程網(wǎng))，沒有鏈接指向這些記錄。暗網(wǎng)挖掘是商業(yè)搜索引擎的一大研究重點(diǎn)，Google是這樣，百度的“阿拉丁”計劃也在于此。

2.2 建立索引

對于搜索引擎，索更是其中最重要的核心技術(shù)之一，面對海量的網(wǎng)頁內(nèi)容，如何快速找到包含用戶查詢詞的所有網(wǎng)頁？倒排索引在其中扮演了關(guān)鍵的角色。

對于一個網(wǎng)頁，我們把它看做一個文檔，其中的內(nèi)容由一個個單詞組成。為了對于用戶的搜索詞快速給出文檔結(jié)果，我們要建立一個單詞-文檔的存儲結(jié)構(gòu)。倒排索引是實(shí)現(xiàn)單詞—文檔矩陣的一種具體存儲形式。通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：單詞詞典和倒排文件。

單詞詞典主要是兩種存儲方式：哈希加鏈接和樹形結(jié)構(gòu)。

索引建立方法：

（1）兩遍文檔遍歷

　　在第一遍掃描文檔集合時，該方法并沒有立即開始建立索引，而是收集一些全局的統(tǒng)計信息。比如文檔集合包含的文檔個數(shù)N，文檔集合內(nèi)所包含的不同單詞個數(shù)M，每個單詞在多少個文檔中出現(xiàn)過的信息DF。在獲得了上述3 類信息后，就可以知道最終索引的大小，于是在內(nèi)存中分配足夠大的空間，用來存儲倒排索引內(nèi)容。在第二遍掃描的時候，開始真正建立每個單詞的倒排列表信息，即對某個單詞來說，獲得包含這個單詞的每個文檔的文檔ID，以及這個單詞在文檔中的出現(xiàn)次數(shù)TF

（2）排序法

　　排序法對此做出了改進(jìn)，該方法在建立索引的過程中，始終在內(nèi)存中分配固定大小的空間，用來存放詞典信息和索引的中間結(jié)果，當(dāng)分配的空間被消耗光的時候，把中間結(jié)果寫入磁盤，清空內(nèi)存里中間結(jié)果所占空間，以用做下一輪存放索引中間結(jié)果的存儲區(qū)。這種方法由于只需要固定大小的內(nèi)存，所以可以對任意大小的文檔集合建立索引。

（3）歸并法

　　在分配的內(nèi)存定額被消耗光時，排序法只是將中間結(jié)果寫入磁盤，而詞典信息一直在內(nèi)存中進(jìn)行維護(hù)，隨著處理的文檔越來越多，詞典里包含的詞典項(xiàng)越來越多，所以占用內(nèi)存越來越大，導(dǎo)致后期中間結(jié)果可用內(nèi)存越來越少。歸并法對此做出了改進(jìn)，即每次將內(nèi)存中數(shù)據(jù)寫入磁盤時，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫入磁盤，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。

索引更新策略：

• 完全重建

• 再合并策略

• 原地更新策略

• 混合策略

2.3 內(nèi)容檢索

內(nèi)容檢索模型是搜索引擎排序的理論基礎(chǔ)，用來計算網(wǎng)頁與查詢的相關(guān)性。

常用的檢索模型

• 布爾模型

• 向量空間模型

• 概率模型

• 語言模型

• 機(jī)器學(xué)習(xí)排序

檢索系統(tǒng)評價指標(biāo)

• 精確率：搜索結(jié)果中相關(guān)文檔的比例 A/(A+B)
  

• 召回率：結(jié)果中相關(guān)文檔占所有相關(guān)文檔的比例 A/(A+C)
  

• P@10 : 前10個結(jié)果中相關(guān)查詢的數(shù)目
  

• MAP指標(biāo) ：對返回結(jié)果按次序加權(quán),權(quán)值為排名的倒數(shù)
  

	查詢相關(guān)	查詢無關(guān)
在搜索結(jié)果內(nèi)	A	B
不在搜索結(jié)果	C	D

2.4 鏈接分析

搜索引擎在查找能夠滿足用戶請求的網(wǎng)頁時，主要考慮兩方面的因素：一方面是用戶發(fā)出的查詢與網(wǎng)頁內(nèi)容的內(nèi)容相似性得分，即網(wǎng)頁和查詢的相關(guān)性；另一方面就是通過鏈接分析方法計算獲得的得分，即網(wǎng)頁的重要性。鏈接分析就是通過網(wǎng)絡(luò)的鏈接結(jié)構(gòu)去獲取網(wǎng)頁重要性的一類方法。

鏈接分析算法很多，從模型上看，主要分為兩類：

• 隨機(jī)游走：從某個網(wǎng)頁以一定的概率跳轉(zhuǎn)到它所包含的鏈接

• 子集傳播：給予某個子集一定的傳播，按照特定的條件，將權(quán)值傳給其他網(wǎng)頁

常用算法：

• PageRank

• HITS

• SALSA

• 主題敏感PageRank

• Hilltop

【3】搜索引擎的平臺基礎(chǔ)

這一部分主要是講搜索引擎的平臺支持，主要是云存儲和云計算模型。

對于商業(yè)搜索引擎，需要保存大量的數(shù)據(jù)，并且需要對這些大規(guī)模的海量數(shù)據(jù)進(jìn)行處理。云存儲和云計算就是為了這個問題提出的解決方案。

大量的數(shù)據(jù)不可能存在一臺服務(wù)器上，它必然是分布式存儲的。當(dāng)數(shù)據(jù)更新時，這就會產(chǎn)生多個服務(wù)器上數(shù)據(jù)不一致的情況，以及如何選擇服務(wù)器的問題。

我們首先先介紹一些基本原則：

（1）CAP原則

CAP是Consistency，Availability，Partition Tolerance的簡稱，即一致性，可用性和分區(qū)容忍性。

對于一個數(shù)據(jù)系統(tǒng)，三個原則不能兼得。云存儲往往關(guān)注CA，犧牲部分一致性。

（2）ACID原則

這是關(guān)系數(shù)據(jù)庫采取的原則。它是Atomicity，Consistency，Isolation，Durability的縮寫，即原子性，一致性，事務(wù)獨(dú)立，持久性。

（3）BASE原則

大多云存儲系統(tǒng)采用，它和ACID不同，犧牲了強(qiáng)數(shù)據(jù)一致性換取高可用性。因?yàn)橛脩艨赡軐?shù)據(jù)的變化沒有能不能提供服務(wù)敏感。

它的三個方面是：

• 基本可用: Basically Available

• 柔性狀態(tài): Soft State，不要求隨時同步

• 最終一致性: 即若數(shù)據(jù)一致性，只要在一定時間段內(nèi)達(dá)到一致即可

Google的云存儲和云計算架構(gòu)

云存儲：

• GFS文件系統(tǒng)：由主服務(wù)器(Master)，Chunk服務(wù)器和GFS客戶端構(gòu)成

• Chubby鎖服務(wù)：針對分布式系統(tǒng)粗粒度的鎖服務(wù)

• BigTable：針對海量數(shù)據(jù)的結(jié)構(gòu)或半結(jié)構(gòu)的存儲模型，本質(zhì)是三維映射表，由行主鍵，列主鍵以及時間構(gòu)成

• MegaStore：適合于實(shí)時交互，而GFS和BigTable適合后臺處理

云計算

• MapReduce

• Percolator ：增量模式，作為對MapReduce的補(bǔ)充
  

• Pregel：大規(guī)模圖計算模型

其它云存儲系統(tǒng)

• Dynamo ： Amazon

• PNUTS ： Yahoo!
  

• HayStack ： Facebook

【4】搜索結(jié)果的改善優(yōu)化

前面講過，搜索引擎追求的三個目標(biāo)就是更快，更全，更準(zhǔn)。但是要達(dá)到這些目標(biāo)并不是一件很輕松的工作，需要很多環(huán)節(jié)的處理。這一部分主要從以下一個方面來講講，怎樣提高搜索引擎的搜索結(jié)果，改善搜索質(zhì)量，提升搜索性能。

4.1 作弊分析

作弊方法

• 內(nèi)容作弊：設(shè)置無關(guān)關(guān)鍵字，內(nèi)容農(nóng)場 （大量低質(zhì)量內(nèi)容）

• 鏈接作弊：鏈接農(nóng)場，互相鏈接...

• 頁面隱藏作弊：欺騙爬蟲，隱藏?zé)o關(guān)關(guān)鍵字，重定向。。。

• WEB2.0作弊

反作弊整體思路

• 信任傳播

• 不信傳播

• 異常發(fā)現(xiàn)

（1）所謂信任傳播模型，基本思路如下：在海量的網(wǎng)頁數(shù)據(jù)中，通過一定的技術(shù)手段或者人工半人工手段，從中篩選出部分完全值得信任的頁面，也就是肯定不會作弊的頁面（可以理解為白名單），算法以這些白名單內(nèi)的頁面作為出發(fā)點(diǎn)，賦予白名單內(nèi)的頁面節(jié)點(diǎn)較高的信任度分值，其他頁面是否作弊，要根據(jù)其和白名單內(nèi)節(jié)點(diǎn)的鏈接關(guān)系來確定。白名單內(nèi)節(jié)點(diǎn)通過鏈接關(guān)系將信任度分值向外擴(kuò)散傳播，如果某個節(jié)點(diǎn)最后得到的信任度分值高于一定閾值，則認(rèn)為沒有問題，而低于這一閾值的網(wǎng)頁則會被認(rèn)為是作弊網(wǎng)頁。

（2）不信任傳播模型從框架上來講，其和信任傳播模型是相似的，最大的區(qū)別在于：初始的頁面子集合不是值得信任的頁面節(jié)點(diǎn)，而是確認(rèn)存在作弊行為的頁面集合，即不值得信任的頁面集合（可以理解為黑名單）。賦予黑名單內(nèi)頁面節(jié)點(diǎn)不信任分值，通過鏈接關(guān)系將這種不信任關(guān)系傳播出去，如果最后頁面節(jié)點(diǎn)的不信任分值大于設(shè)定的閾值，則會被認(rèn)為是作弊網(wǎng)頁。

（3）異常發(fā)現(xiàn)模型也是一個高度抽象化的算法框架模型，其基本假設(shè)認(rèn)為：作弊網(wǎng)頁必然存在有異于正常網(wǎng)頁的特征，這種特征有可能是內(nèi)容方面的，也有可能是鏈接關(guān)系方面的。而制定具體算法的流程往往是先找到一些作弊的網(wǎng)頁集合，分析出其異常特征有哪些，然后利用這些異常特征來識別作弊網(wǎng)頁。

　　只要操縱搜索引擎搜索結(jié)果能夠帶來收益，那么作弊動機(jī)就會始終存在，尤其是在網(wǎng)絡(luò)營銷起著越來越重要宣傳作用的時代尤其如此。作弊與反作弊是相互抑制同時也是相互促進(jìn)的一個互動過程，“道高一尺，魔高一丈”的故事不斷重演。前述內(nèi)容主要是以技術(shù)手段來進(jìn)行反作弊，而事實(shí)上純粹技術(shù)手段目前是無法徹底解決作弊問題的，必須將人工手段和技術(shù)手段相互結(jié)合，才能取得較好的反作弊效果。技術(shù)手段可以分為相對通用的手段和比較特殊的手段，相對通用的手段對于可能新出現(xiàn)的作弊手法有一定的預(yù)防能力，但是因?yàn)槠渫ㄓ眯?#xff0c;所以針對性不強(qiáng)，對特殊的作弊方法效果未必好。而專用的反作弊方法往往是事后諸葛亮，即只有作弊行為已經(jīng)發(fā)生并且比較嚴(yán)重，才可能歸納作弊特征，采取事后過濾的方法。人工手段則與技術(shù)手段有很強(qiáng)的互補(bǔ)性，可以在新的作弊方式一出現(xiàn)就被人發(fā)現(xiàn)，可以看做一種處于作弊進(jìn)行時的預(yù)防措施。所以從時間維度考慮對作弊方法的抑制來說，通用反作弊方法重在預(yù)防，人工手段重在發(fā)現(xiàn)，而專用反作弊方法重在事后處理，其有內(nèi)在的聯(lián)系和互補(bǔ)關(guān)系存在。

4.2 分析用戶意圖

準(zhǔn)確分析用戶的搜索意圖是目前搜索引擎的重點(diǎn)研究方向。

用戶的意圖可以初略分為

• 導(dǎo)航型

• 信息型

• 事物型

搜索日志是挖掘用戶意圖的重要數(shù)據(jù)來源

• 點(diǎn)擊圖：用戶在查詢結(jié)果出來后點(diǎn)擊的鏈接可能更是他希望的結(jié)果

• 查詢回話：用戶在短時間的連續(xù)查詢詞存在相關(guān)性

• 查詢圖：構(gòu)建用戶查詢之間的結(jié)構(gòu)關(guān)系

用戶在搜索時可能想不到合適的搜索詞，或者關(guān)鍵詞輸入錯誤，這時候就需要幫助用戶澄清搜索意圖。

常見的方法是：

• 相關(guān)搜索

• 查詢糾錯
  

4.3 網(wǎng)頁去重

經(jīng)過統(tǒng)計，網(wǎng)絡(luò)中有相當(dāng)比例的網(wǎng)頁是近似相同或者完全相同的，高達(dá)29%。如果搜索返回大量相似網(wǎng)頁，顯然降低了搜索結(jié)果質(zhì)量。針對這一現(xiàn)象，網(wǎng)頁去重就顯得十分必要。

網(wǎng)頁去重一般是在爬蟲抓取到網(wǎng)頁后，對其建立索引之前。去重算法應(yīng)該兼顧準(zhǔn)確性和運(yùn)行效率。

典型的網(wǎng)頁去重算法：

• 特征抽取

• 文檔指紋生成

• 相似性計算

幾種典型的去重算法：

• Shingling算法：將文檔中連續(xù)的單詞序列作為特征

• I-Match算法：先統(tǒng)計一個全局的特征詞典，然后用單文檔的特征與其比較

• SimHash算法：可能是目前最優(yōu)秀的去重算法

• SpotSig算法

4.4 緩存機(jī)制

緩存機(jī)制可以加快用戶相應(yīng)速度，節(jié)省計算資源

緩存系統(tǒng)的目標(biāo)是最大化緩存命中率和保持緩存與索引的一致性

緩存的對象主要是網(wǎng)頁搜索結(jié)果和查詢詞對應(yīng)的倒排列表

緩存淘汰策略主要有動態(tài)策略和混合策略

這個內(nèi)容是我從別的網(wǎng)站轉(zhuǎn)過來的，感覺可以讓各位產(chǎn)品經(jīng)理了解一下。

來源：博客園

總結(jié)

以上是生活随笔為你收集整理的搜索引擎基本原理，产品知识普及帖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。