任何一条信息文本都可以对应一个不太长的随机数作为指纹(指纹),将其与其他信息区分开来。只要算法设计得很好,任何两条信息的指纹就很难重复,就像人类的指纹一样。信息指纹识别在加密,信息压缩和处理方面具有广泛的应用。
我们在关于图论和网页爬虫的文章中提到,为了防止重复下载同一网页,我们需要记录在哈希表中访问过的URL(URL)。但是,在散列表中以字符串的形式直接存储URL会占用内存空间和浪费时间。当前网址通常较长。例如,如果您在谷歌或百度寻找数学之美,相应的URL超过100个字符。以下是百度的链接
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
假设URL的平均长度是100个字符,那么存储200亿个URL需要至少2 TB,这是2000 GB的容量。考虑到哈希表的存储效率通常只有50%,所需的实际内存比TB多4个。即使这些URL放在计算机的内存中,搜索字符串也是低效的,因为URL不是固定的。因此,如果我们可以找到一个函数,我们会将200亿个URL随机映射到128个bin或16个字节的整数空间,例如上面的长字符串到:之类的随机数。
89324943298843298045454543
这样,每个URL只需要占用16个字节,而不是原来的100个。这将把存储URL的内存需求减少到1/6。这个16字节的随机数称为URL的指纹。可以证明,只要生成随机数的算法足够好,就可以保证两个字符串几乎不可能有相同的指纹,就像两个人不可能有相同的指纹一样。因为指纹是固定的128位整数,所以查找比字符串小得多。当网络爬虫下载网页时,它将访问的网页的URL更改为信息指纹,并将其存储在哈希表中。每当遇到新的网址时,计算机就会计算其指纹并比较指纹。指纹是否已经在哈希表中,以决定是否下载网页。这个整数搜索可以比原来的字符串查找快几到几十倍。
生成信息指纹的关键算法是伪随机数生成算法。最早的prng算法是由计算机之父von neumann提出的。他的方法很简单,也就是说,一个数字的方头是尾随的,取中间的数字。例如,四位数的二进制数1001(相当于十进制数中的9)的平方为01010001(十进制数中的81),剩下的四位数为0100。当然,这种方法生成的数字不是很随机的,这意味着两个不同的信息可能具有相同的指纹。目前常用的梅森网络算法要好得多。信息指纹的使用远不止消除URL。信息指纹的孪生兄弟是密码。信息指纹识别的一个特征是其不可逆性,即,不能基于信息指纹导出原始信息。网络加密传输需要此属性。例如,网站可以根据用户的cookie识别不同的用户。这个cookie是信息指纹。但是,网站无法根据信息指纹了解用户的身份,从而可以保护用户的隐私。在因特网上,加密的可靠性取决于是否难以人工地查找具有相同指纹的信息,例如黑客是否可以随机生成用户的cookie。从加密的角度来看,MersenneTwister,算法并不好,因为它产生的随机数是相关的。
Internet上的加密使用加密的伪随机数生成器(csprng)。常用的算法是诸如MD5或SHA1之类的标准,它们可以将可变长度的信息改变为固定长度的128二进制或160个二进制随机数。值得一提的是,SHA1以前被认为是完美无缺的。中国的王晓云教授现在已经证明存在漏洞。但你不必恐慌,因为它仍然不同于黑客可以真正打破你的注册信息。