關鍵詞排名優化-信息指紋特征及其原理

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

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

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

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

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

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