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

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

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

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

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

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

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