任何段信息文字都可以对应个不太长随机数作为区别它和其它信息指纹(Fingerpr)只要算法设计好任何两段信息指纹都很难重复就如同人类指纹样信息指纹在加密、信息压缩和处理中有着广泛应用

　　我们在图论和网络爬虫文中提到为了防止重复下载同个网页我们需要在哈希表中纪录已经访问过网址(URL)但是在哈希表中以串形式直接存储网址既费内存空间又浪费查找时间现在网址般都较长比如如果在 Google 或者百度在查找数学的美对应网址长度在百个以上下面是百度链接

　　http://www.baidu.com/s?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

　　假定网址平均长度为百个那么存贮 200 亿个网址本身至少需要 2 TB即两千 GB 容量考虑到哈希表存储效率般只有 50%实际需要内存在 4 TB以上即使把这些网址放到了计算机内存中由于网址长度不固定以串形式查找效率会很低因此我们如果能够找到个将这 200 亿个网址随机地映射到128 2进位即 16 个字节整数空间比如将上面那个很长串对应成个如下随机数:

　　893249432984398432980545454543

　　这样每个网址只需要占用 16 个字节而不是原来百个这就能把存储网址内存需求量降低到原来 1/6这个16 个字节随机数就称做该网址信息指纹(Fingerpr)可以证明只要产生随机数算法足够好可以保证几乎不可能有两个串指纹相同就如同不可能有两个人指纹相同样由于指纹是固定 128 位整数因此查找计算量比串比较小得多网络爬虫在下载网页时它将访问过网页网址都变成个个信息指纹存到哈希表中每当遇到个新网址时计算机就计算出它指纹然后比较该指纹是否已经在哈希表中来决定是否下载这个网页这种整数查找比原来串查找,可以快几倍到几十倍

　　产生信息指纹关键算法是伪随机数产生器算法(prng)最早 prng 算法是由计算机的父冯诺伊曼提出来他办法非常简单就是将个数平方掐头去尾取中间几位数比如个 4位 2进制数 1001(相当于十进制9)其平方为 01010001 (十进制 81)掐头去尾剩下中间 4位 0100当然这种思路方法产生数字并不很随机也就是说两个区别信息很有可能有同指纹现在常用 MersenneTwister 算法要好得多

　　信息指纹用途远不止网址消重信息指纹孪生兄弟是密码信息指纹个特征是其不可逆性, 也就是说,无法根据信息指纹推出原有信息这种性质正是网络加密传输所需要比如说个网站WebSite可以根据用户Cookie 识别区别用户这个 cookie 就是信息指纹但是网站WebSite无法根据信息指纹了解用户身份这样就可以保护用户隐私在互联网上加密可靠性取决于是否很难人为地找到拥有同指纹信息 比如个黑客是否能随意产生用户 cookie从加密角度讲 MersenneTwister算法并不好它产生随机数有相关性

　　互联网上加密要用基于加密伪随机数产生器(csprng)常用算法有 MD5 或者 SHA1 等标准它们可以将不定长信息变成定长 128 2进位或者 160 2进位随机数值得提事SHA1 以前被认为是没有漏洞现在已经被中国王小云教授证明存在漏洞但是大家不必恐慌这和黑客能真正攻破你注册信息是还两回事

　　信息指纹虽然历史很悠久但真正广泛应用是在有了互联网以后这几年才渐渐热门起来