正如我们在文章中提到的图论和网络爬虫为了防止重复下载相同的Web页面我们需要记录的网址(url)访问哈希表。然而直接存储URL字符串的哈希表的形式消耗内存空间和搜索时间的浪费。当前url通常长。例如如果您正在寻找数学的美在谷歌或百度相应的URL是超过一百个字符的长度。下面是链接到百度
? ie = gb2312&bs = % CA % FD % D1%A7%D6%AE % C3%C0&sr = z = cl = 3 f = 8
wd = % CE % E2%BE % FC + % CA % FD % D1%A7%D6%AE % C3%C0&ct = 0
假设URL的平均长度是100个字符然后存储200亿URL本身至少需要2 TB二千GB的容量考虑到哈希表的存储效率通常只有50%超过4结核病所需的实际内存。即使这些url是存储在计算机的内存中搜索字符串的形式的效率会很低因为url的长度是不固定的。因此如果我们能找到一个函数随机地图这200亿128二进制或16字节整数空间的url例如上面的长字符串对应于一个随机数如下:893249432984398432980545454543
所以每个URL只需要占用16字节而不是原来的一百。这可以减少内存需求url存储到原来的1/6。这16字节的随机数叫做网站的指纹。它可以证明只要生成随机数的算法是足够好它可以保证对两个字符串来说几乎是不可能有相同的指纹就像两个人不可能有相同的指纹。由于指纹是一个固定的128位整数搜索的计算量远小于字符串比较。当一个网络爬虫下载一个网页它的url访问网页变成信息指纹并将它们存储在哈希表中。每当遇到一个新的URL计算机计算指纹和比较了指纹。指纹是否已经在哈希表来决定是否要下载这个网页。这种类型的整数搜索可以几美元到几十倍的原始字符串搜索。
指纹算法生成信息的关键是伪随机数发生器算法(prng)。最早的prng冯诺依曼提出的算法计算机之父。他的方法很简单那就是削减的平方数从一开始到最后网页搜索优化那就是削减的平方数从一开始到最后中间几位数。例如一个四位数的二进制数1001(相当于十进制9)它的平方是01010001 81(十进制)和中间的四位数是0100。当然这个方法不是很随机生成的数字这意味着两个不同的消息可能会有相同的指纹。常用的MersenneTwister算法要好得多。
指纹信息的目的是远远超过url的重复数据删除。信息指纹密码的孪生兄弟。信息指纹的特点之一是它的不可逆性即原始信息不能来源于信息的指纹。这个属性正是需要网络加密传输。例如一个网站可以识别不同的用户根据用户的cookie。这个饼干是一个指纹信息。然而网页搜索优化一个网站可以识别不同的用户根据用户的cookie。这个饼干是一个指纹信息。然而网站无法知道用户的身份基于指纹的信息这样可以保护用户的隐私。在互联网上加密的可靠性取决于人为很难找到相同的指纹信息如黑客是否能随机生成一个用户的cookie。从加密的角度MersenneTwister的算法不是很好因为它产生的随机数是相关的。
加密在网络上使用一个密码伪随机数发生器(csprng)。常用的如MD5、SHA1算法标准可以128变长信息转换成固定长度的二进制或二进制随机数字160。值得一提的是SHA1以前认为没有漏洞但它现在已经证明中国的王教授小云有漏洞。