關(guān)鍵詞排名優(yōu)化-信息指紋特征及其原理

　　今天咱們講講關(guān)鍵詞排名優(yōu)化-信息指紋特征及其原理，任何一段信息文字，都可以對應(yīng)一個(gè)不太長的隨機(jī)數(shù)，作為差別它和其它信息的指紋（Fingerprint)。只需算法設(shè)計(jì)的好，任何兩段信息的指紋都很難重復(fù)，就仿佛人類的指紋一樣。信息指紋在加密、信息壓縮和處理中有著遍及的應(yīng)用。

　　我們在圖論和收集爬蟲一文中提到，為了防止重復(fù)下載統(tǒng)一個(gè)網(wǎng)頁，我們需求在哈希表中記載曾經(jīng)訪問過的網(wǎng)址（URL)。然則在哈希表中以字符串的方法直接存儲(chǔ)網(wǎng)址，既費(fèi)內(nèi)存空間，又糜費(fèi)查找時(shí)間?，F(xiàn)在的網(wǎng)址通俗都較長，比如，假設(shè)在 Google 或許百度在查找數(shù)學(xué)之美，對應(yīng)的網(wǎng)址長度在一百個(gè)字符以上。下面是百度的鏈接

　　如許每個(gè)網(wǎng)址只需求占用 16 個(gè)字節(jié)而不是本來的一百個(gè)。這就可以把存儲(chǔ)網(wǎng)址的內(nèi)存需求量降低到本來的 1/6。這個(gè)16 個(gè)字節(jié)的隨機(jī)數(shù)，就稱做該網(wǎng)址的信息指紋（Fingerprint)。可以證實(shí)，只需發(fā)生隨機(jī)數(shù)的算法足夠好，可以保證簡直不能夠有兩個(gè)字符串的指紋相反，就仿佛不能夠有兩團(tuán)體的指紋相反一樣。因?yàn)橹讣y是固定的 128 位整數(shù)，因此查找的計(jì)算量比字符串比擬小很多。收集爬蟲不才載網(wǎng)頁時(shí)，它將訪問過的網(wǎng)頁的網(wǎng)址都釀成一個(gè)個(gè)信息指紋，存到哈希表中，每當(dāng)碰到一個(gè)新網(wǎng)址時(shí)，計(jì)算機(jī)就計(jì)算出它的指紋，然后比擬該指紋可否曾經(jīng)在哈希表中，來決定可否下載這個(gè)網(wǎng)頁。這類整數(shù)的查找比本來字符串查找,可以快幾倍到幾十倍。

　　發(fā)生信息指紋的關(guān)鍵算法是偽隨機(jī)數(shù)發(fā)生器算法（prng)。最早的 prng 算法是由計(jì)算機(jī)之父馮諾伊曼提出來的。他的方法十分復(fù)雜，就是將一個(gè)數(shù)的平方掐頭去尾，取中間的幾位數(shù)。比如一個(gè)四位的二進(jìn)制數(shù) 1001（相當(dāng)于十進(jìn)制的9），其平方為 01010001 (十進(jìn)制的 81）掐頭去尾剩下中間的四位 0100。固然這類方法發(fā)生的數(shù)字其實(shí)不很隨機(jī)，也就是說兩個(gè)分歧信息很有能夠有統(tǒng)一指紋?，F(xiàn)在經(jīng)常使用的 MersenneTwister 算法要好很多。

　　信息指紋的用途遠(yuǎn)不止網(wǎng)址的消重，信息指紋的的孿生兄弟是暗碼。信息指紋的一個(gè)特點(diǎn)是其不成逆性, 也就是說,沒法依據(jù)信息指紋推出原有信息，這類性質(zhì)， 正是收集加密傳輸所需求的。比如說，一個(gè)網(wǎng)站可以依據(jù)用戶的Cookie 識(shí)別分歧用戶，這個(gè) cookie 就是信息指紋。然則網(wǎng)站沒法依據(jù)信息指紋了解用戶的身份，如許便可以保護(hù)用戶的隱私。在互聯(lián)網(wǎng)上，加密的牢靠性，取決于可否很難報(bào)答地找到具有統(tǒng)一指紋的信息， 比如一個(gè)黑客可否能隨便發(fā)生用戶的 cookie。從加密的角度講 MersenneTwister，算法并欠好，，因?yàn)樗l(fā)生的隨機(jī)數(shù)有相干性。

　　互聯(lián)網(wǎng)上加密要用基于加密偽隨機(jī)數(shù)發(fā)生器（csprng)。經(jīng)常使用的算法有 MD5 或許 SHA1 等規(guī)范，它們可以將不定長的信息釀成定長的 128 二進(jìn)位或許 160 二進(jìn)位隨機(jī)數(shù)。值得一提的事，SHA1 之前被認(rèn)為是沒有破綻的，現(xiàn)在曾經(jīng)被中國的王小云傳授證實(shí)存在破綻。然則大年夜家不用驚恐， 因?yàn)檫@和黑客能真正攻破你的注冊信息是還兩回事。