【文章內(nèi)容簡(jiǎn)介】 0034(34/32)%8=134%32=2MD5簽名函數(shù)URLInt Hash[8]Hash[1]圖25 Bitmap結(jié)構(gòu)的哈希表定義一個(gè)哈希表，即Int Hash[8]。對(duì)URL執(zhí)行MD5簽名，假定得到的值為34。用34除32，得到商1，用其對(duì)8取模得到1，表示槽位在Hash[1]中。用34除32得到余數(shù)為2，表示34映射到Hash[1]整個(gè)32位整數(shù)的第3個(gè)比特位上，將這個(gè)比特位置1，則Hash[1]為4。圖26為34按比特位展開(kāi)：前3位決定哈希數(shù)組下標(biāo)后5為決定整型的哪一位00100010圖26 34位比特位展開(kāi)前面計(jì)算的C代碼如下：（1）：int MD5 = 34。（2）：int index_int = MD5amp。31。//相當(dāng)于34%32（3）：int index_Hash = (MD55)amp。7。 //相當(dāng)于（34//32）%8,32是2的5次冪（4）：if ( Hash [ index_Hash ] amp。 (1 index_int ))。 //表示探測(cè)該槽位是否已經(jīng)被置位（5）：else { Hash [ index_Hash ] = Hash [ index_Hash] | (1 index_int )。//表示該槽位沒(méi)有被置位，用或運(yùn)算置位。不重復(fù)抓取的好處在于基本處理了死循環(huán)的問(wèn)題，即抓取過(guò)的不會(huì)再繼續(xù)抓取。然而實(shí)際操作中有這樣一個(gè)問(wèn)題，如果任意2個(gè)網(wǎng)頁(yè)存在鏈接，則它們的最短路徑為萬(wàn)維網(wǎng)直徑長(zhǎng)度17。這樣就不能保證爬蟲(chóng)一定會(huì)按照最佳路徑抓取每一個(gè)網(wǎng)頁(yè)，因?yàn)槿魏我粋€(gè)網(wǎng)頁(yè)都可能從多個(gè)種子站點(diǎn)開(kāi)始廣度優(yōu)先被遍歷到。所以應(yīng)在深度為17的時(shí)候停止抓取，對(duì)于那些未抓到的網(wǎng)頁(yè)，期待從其他種子站點(diǎn)更加經(jīng)濟(jì)的達(dá)到。不重復(fù)抓取非常合適多個(gè)爬蟲(chóng)合作抓取，可以進(jìn)一步降低記錄歷史抓取情況的散列表的大小。若有N個(gè)爬蟲(chóng)。則散列表的大小可以被壓縮到1/N。4．網(wǎng)頁(yè)抓取優(yōu)先策略網(wǎng)頁(yè)抓取優(yōu)先策略也稱為“頁(yè)面選擇問(wèn)題”（Page Selection），通常是盡可能的首先抓取重要性高的網(wǎng)頁(yè)，這樣可以保證在有限的資源內(nèi)盡可能的照顧某些網(wǎng)頁(yè)。重要性度由鏈接受歡迎度、鏈接重要度和平均鏈接深度這3個(gè)方面決定。鏈接受歡迎度鏈接受歡迎度IB(P)主要由反向鏈接的數(shù)目和質(zhì)量決定。一個(gè)網(wǎng)頁(yè)有越多的鏈接指向它，那么表示其他網(wǎng)頁(yè)對(duì)于它的認(rèn)可度就越高，這個(gè)網(wǎng)頁(yè)被訪問(wèn)的概率就越高。一個(gè)網(wǎng)頁(yè)被多個(gè)重要性高的網(wǎng)頁(yè)所指向，那么其重要性也就越高。鏈接重要度鏈接重要度IL(P) 是一個(gè)關(guān)于URL字符串的函數(shù)，考察的是字符串本身。如認(rèn)為包含“?！被蛘摺啊！钡腢RL重要度高。平均鏈接深度平均鏈接深度ID(P)表示在一個(gè)種子站點(diǎn)集合中，每個(gè)種子站點(diǎn)都存在一條鏈路到達(dá)某一個(gè)網(wǎng)頁(yè)，這個(gè)數(shù)值就是平均鏈接深度。網(wǎng)頁(yè)重要性的度量為I（P），它由以上兩個(gè)量化值線性決定，即： I(P)=α*IB(P)+β*IL(P)平均鏈接深度由廣度優(yōu)先的遍歷規(guī)則保證，因此不作為重要性評(píng)價(jià)的指標(biāo)。5．網(wǎng)頁(yè)重訪策略互聯(lián)網(wǎng)不僅僅非常龐大，更處于不斷的變化中。因此，網(wǎng)絡(luò)爬蟲(chóng)不得不周期性的重新訪問(wèn)那些已經(jīng)被抓去過(guò)的網(wǎng)頁(yè)，來(lái)保持與互聯(lián)網(wǎng)的變化一致。網(wǎng)頁(yè)重訪基本分為以下2類：統(tǒng)一的重訪策略:爬蟲(chóng)以相同的頻率重訪那些已經(jīng)抓去過(guò)的全部網(wǎng)頁(yè)個(gè)體的重訪策略:爬蟲(chóng)根據(jù)其更新頻率來(lái)決定重訪該個(gè)體網(wǎng)頁(yè)的頻率。研究表明，網(wǎng)頁(yè)的更新過(guò)程符合泊松過(guò)程、網(wǎng)頁(yè)更新時(shí)間間隔符合指數(shù)分布，因此可以對(duì)不同類型的網(wǎng)頁(yè)采取不同的更新策略。泊松分布： PX=k=exλkk! k=0,1,2,…。 Robots協(xié)議Robots協(xié)議是Web站點(diǎn)和搜索引擎爬蟲(chóng)交互的一種方式，robots。txt是存放在站點(diǎn)根目錄下的一個(gè)純文本文件，該文件可以指定搜索引擎爬蟲(chóng)只抓去指定的內(nèi)容，或者是禁止搜索引擎爬蟲(chóng)抓取網(wǎng)站的部分或全部?jī)?nèi)容。爬蟲(chóng)訪問(wèn)某個(gè)站點(diǎn)時(shí)，會(huì)先查詢有沒(méi)有此文件。若有則按照這個(gè)文件訪問(wèn)，若沒(méi)有則搜索引擎就沿著鏈接抓取。Robots。txt必須放置在站點(diǎn)的根目錄下，并且文件名必須全部為小寫(xiě)。robots。txt文件包含一條或更多的記錄，這些記錄通過(guò)空行分開(kāi)（以CR,CR/NL, or NL作為結(jié)束符），每一條記錄的格式如下所示：field:optionalspacevalueoptionalspace。該文件中的記錄通常以一行或多行Useragent開(kāi)始，后面加上若干Disallow行,詳細(xì)情況如下：Useragent:該項(xiàng)的值用于描述搜索引擎robot的名字，在robots。txt文件中，如果有多條Useragent記錄說(shuō)明有多個(gè)robot會(huì)受到該協(xié)議的限制。Disallow:該項(xiàng)的值用于描述不希望被訪問(wèn)到的一個(gè)URL，這個(gè)URL可以是一條完整的路徑，也可以是部分的，任何以Disallow開(kāi)頭的URL均不會(huì)被robot訪問(wèn)到。語(yǔ)法實(shí)例：：robots。txt為空就可以，什么都不要寫(xiě)。：Useragent: *Disallow: /目錄名1/Disallow: /目錄名2/Disallow: /目錄名3/，例如禁止谷歌：Useragent: googlebotDisallow: /：Useragent: *Disallow: /google蜘蛛： googlebot百度蜘蛛：baiduspideryahoo蜘蛛：slurpalexa 蜘蛛：ia_archivermsn 蜘蛛：msnbotaltavista 蜘蛛：scooterlycos蜘蛛：lycos_spideralltheweb蜘蛛：fastwebcrawler/nktomi蜘蛛:slurp分析器的功能就是對(duì)搜集器搜集來(lái)的網(wǎng)頁(yè)信息或者下載的文檔進(jìn)行分析，提取相關(guān)的網(wǎng)頁(yè)信息，根據(jù)一定的相關(guān)度計(jì)算，得到每一個(gè)網(wǎng)頁(yè)針對(duì)頁(yè)面內(nèi)容中級(jí)超鏈接中每一個(gè)關(guān)鍵詞的相關(guān)度。其完成的工作主要包括信息抽取、網(wǎng)頁(yè)消重、中文分詞和PageRank計(jì)算等。 信息抽取的目的，是從半結(jié)構(gòu)化網(wǎng)頁(yè)中抽取出有價(jià)值的能夠代表網(wǎng)頁(yè)的屬性，例如錨文本、標(biāo)題和正文等。把這些屬性結(jié)合起來(lái)組成一個(gè)網(wǎng)頁(yè)對(duì)象，這種處理亦叫做“網(wǎng)頁(yè)結(jié)構(gòu)化”網(wǎng)頁(yè)結(jié)構(gòu)化的目標(biāo):網(wǎng)頁(yè)結(jié)構(gòu)化的目標(biāo)是抽取網(wǎng)頁(yè)的基本屬性，其能夠描述這個(gè)網(wǎng)頁(yè)，并打包成為一個(gè)網(wǎng)頁(yè)對(duì)象:錨文本：就是鏈接文本，一般來(lái)說(shuō)，頁(yè)面添加的鏈接一般來(lái)說(shuō)都應(yīng)該跟頁(yè)面有直接相關(guān)的聯(lián)系，搜索引擎可以根據(jù)指向某一個(gè)網(wǎng)頁(yè)的鏈接的錨文本描述來(lái)判斷該網(wǎng)頁(yè)的內(nèi)容屬性。標(biāo)題：特指HTML標(biāo)識(shí)語(yǔ)言中title/title中間的文字部分，這些文字由網(wǎng)頁(yè)制作者本人編寫(xiě)，表達(dá)了網(wǎng)頁(yè)的基本含義。正文標(biāo)題：抽取正文中適當(dāng)?shù)奈淖肿鳛檎臉?biāo)題。正文：網(wǎng)頁(yè)的主題內(nèi)容，它完整的表達(dá)了網(wǎng)頁(yè)的基本信息，一般出現(xiàn)在DIV、TABLE、P等HTML標(biāo)簽中。正向鏈接：正向鏈接是網(wǎng)頁(yè)編寫(xiě)者編寫(xiě)的引導(dǎo)用戶繼續(xù)在網(wǎng)上瀏覽的鏈接，也是其他網(wǎng)頁(yè)的錨文本。圖27為一個(gè)網(wǎng)頁(yè)一般包含的5個(gè)屬性：屬 性含 義title頁(yè)面標(biāo)題content title正文標(biāo)題concent正文link正向鏈接集合anchor指向自身的錨文本圖27網(wǎng)頁(yè)對(duì)象的5個(gè)屬性及含義HTML標(biāo)簽樹(shù)、由于互聯(lián)網(wǎng)上大多數(shù)靜態(tài)網(wǎng)頁(yè)都是以HTML網(wǎng)頁(yè)形式存在，它把其描述的全部?jī)?nèi)容都按照HTML語(yǔ)法存放標(biāo)簽中，為了更清楚地描述網(wǎng)頁(yè)的組織結(jié)構(gòu)，將網(wǎng)頁(yè)中的標(biāo)簽按照出現(xiàn)順序依次整理出來(lái)并用適當(dāng)?shù)慕Y(jié)構(gòu)記錄。由于標(biāo)簽的嵌套關(guān)系，因此整理結(jié)果會(huì)成為一個(gè)樹(shù)形結(jié)構(gòu)。HTML HEADBODYTITLETABLETRTRTR TDTDTD 圖28 HTML標(biāo)簽樹(shù)通過(guò)投票得到正文在HTML語(yǔ)言編寫(xiě)的網(wǎng)頁(yè)中，由于沒(méi)有標(biāo)注出正文，且正文可能分布在多個(gè)HTML標(biāo)簽中，因此判定一個(gè)完整的正文是一個(gè)難點(diǎn)。為此引入文本塊的概念，對(duì)那些如標(biāo)簽P/P標(biāo)簽間的文字認(rèn)為是一個(gè)文本塊。定義一組規(guī)則，使他們對(duì)文本塊進(jìn)行打分。得分越高的文本塊往往重要度也就越高。規(guī)則可以諸如：文本長(zhǎng)度，位置，反向鏈接位置等。圖29為簡(jiǎn)單投票算法的一般模型：文本塊2得分文本塊1得分…….規(guī)則n規(guī)則1文本塊2文本塊1 圖29簡(jiǎn)單投票算法重復(fù)或者的網(wǎng)頁(yè)會(huì)對(duì)搜索引擎產(chǎn)生非常大負(fù)載，導(dǎo)致搜索引擎的效率下降，網(wǎng)頁(yè)查重的第一步就是判斷那些網(wǎng)頁(yè)是重復(fù)或者相似的。網(wǎng)頁(yè)相似有4中類型：（1）內(nèi)容和格式完全相同（2）內(nèi)容相同，格式不同（3）部分重要的內(nèi)容相同，格式相同 （4）部分重要的內(nèi)容相同，格式不同要實(shí)現(xiàn)網(wǎng)頁(yè)查重一般需要3步：特征抽取有兩種算法一種是“IMatch”算法，盡可能只抽取一個(gè)特征，這樣只要比較一次即可；另一個(gè)算法是“Shingle”，抽取多個(gè)特征詞匯，通過(guò)比較亮哥特征集合的相似度實(shí)現(xiàn)文檔重查?！癐Match”算法抽取的特征只有一個(gè)，因此只需要為文檔計(jì)算一個(gè)簽名值，如果2個(gè)文檔的簽名值完全相同，則文檔相似。 Shingle”算法的特征有多個(gè)，其計(jì)算方法為記錄完全一致的Shingle個(gè)數(shù)，然后除以兩個(gè)文檔的Shingle總數(shù)個(gè)數(shù)減去一致的Shingle個(gè)數(shù)，數(shù)學(xué)表示為：J=A∩BA∪B ,這個(gè)數(shù)值稱為“Jacccard系數(shù)”消重主要考慮得問(wèn)題是留下哪個(gè)網(wǎng)頁(yè)，現(xiàn)在搜索引擎主要采用的方法是保留爬蟲(chóng)首先抓取的網(wǎng)頁(yè)，丟棄其他相同的，這種方法實(shí)現(xiàn)簡(jiǎn)單，且很大程度上保證了優(yōu)先保留原創(chuàng)的原則。在網(wǎng)頁(yè)分析的過(guò)程中，中文與英文的處理方式是不同的，這是因?yàn)橹形男畔⑴c英文信息有一個(gè)明顯的差別: 英文單詞之間有空格，而中文文本中詞與詞之間沒(méi)有分割符。這就要求在對(duì)中文網(wǎng)頁(yè)進(jìn)行分析之前，先要將網(wǎng)頁(yè)中的句子切割成一個(gè)個(gè)的詞的序列，這就是中文分詞。目前，中文自動(dòng)分詞比較成熟的技術(shù)是基于分詞詞典的機(jī)械分詞方法。這種方法是按照一定的策略將要分析的漢字串與詞典中的詞條進(jìn)行匹配。根據(jù)匹配策略的不同，機(jī)械分詞方法又有如下幾種算法: 正向最大匹配算法、逆向最大匹配算法、最少分詞算法等。這種方法的優(yōu)點(diǎn)是分詞的速度快，準(zhǔn)確度有一定的保證，但對(duì)未登錄詞的處理效果較差。中文自動(dòng)分詞的難點(diǎn)在于分詞歧義的處理和未登錄詞的識(shí)別，如何處理這兩個(gè)問(wèn)題一直是該領(lǐng)域研究的熱點(diǎn)。歧義主要包括交叉歧義（如化妝和服裝，可分解為“化妝