桂澜山碧桂园怎么样:数学之美 系列十三 信息指纹及其应用(转载)
来源:百度文库 编辑:偶看新闻 时间:2024/04/28 07:02:03
发表者:吴军,Google 研究员
任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的指纹(Fingerprint)。只要算法设计的好,任何两段信息的指纹都很难重复,就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。
我们在图论和网络爬虫一文中提到,为了防止重复下载同一个网页,我们需要在哈希表中纪录已经访问过的网址(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 二进位即 16 个字节的整数空间,比如将上面那个很长的字符串对应成一个如下的随机数:
893249432984398432980545454543
这样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6。这个16 个字节的随机数,就称做该网址的信息指纹(Fingerprint)。可以证明,只要产生随机数的算法足够好,可以保证几乎不可能有两个字符串的指纹相同,就如同不可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数,因此查找的计算量比字符串比较小得多。网络爬虫在下载网页时,它将访问过的网页的网址都变成一个个信息指纹,存到哈希表中,每当遇到一个新网址时,计算机就计算出它的指纹,然后比较该指纹是否已经在哈希表中,来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。
产生信息指纹的关键算法是伪随机数产生器算法(prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单,就是将一个数的平方掐头去尾,取中间的几位数。比如一个四位的二进制数 1001(相当于十进制的9),其平方为 01010001 (十进制的 81)掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机,也就是说两个不同信息很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。
信息指纹的用途远不止网址的消重,信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,
无法根据信息指纹推出原有信息,这种性质, 正是网络加密传输所需要的。比如说,一个网站可以根据用户的Cookie 识别不同用户,这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份,这样就可以保护用户的隐私。在互联网上,加密的可靠性,取决于是否很难人为地找到拥有同一指纹的信息, 比如一个黑客是否能随意产生用户的 cookie。从加密的角度讲 MersenneTwister,算法并不好,因为它产生的随机数有相关性。
互联网上加密要用基于加密伪随机数产生器(csprng)。常用的算法有 MD5 或者 SHA1 等标准,它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事,SHA1 以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌, 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久,但真正的广泛应用是在有了互联网以后,这几年才渐渐热门起来。
任何一段信息文字,都可以对应一个不太长的随机数,作为区别它和其它信息的指纹(Fingerprint)。只要算法设计的好,任何两段信息的指纹都很难重复,就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。
我们在图论和网络爬虫一文中提到,为了防止重复下载同一个网页,我们需要在哈希表中纪录已经访问过的网址(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 二进位即 16 个字节的整数空间,比如将上面那个很长的字符串对应成一个如下的随机数:
893249432984398432980545454543
这样每个网址只需要占用 16 个字节而不是原来的一百个。这就能把存储网址的内存需求量降低到原来的 1/6。这个16 个字节的随机数,就称做该网址的信息指纹(Fingerprint)。可以证明,只要产生随机数的算法足够好,可以保证几乎不可能有两个字符串的指纹相同,就如同不可能有两个人的指纹相同一样。由于指纹是固定的 128 位整数,因此查找的计算量比字符串比较小得多。网络爬虫在下载网页时,它将访问过的网页的网址都变成一个个信息指纹,存到哈希表中,每当遇到一个新网址时,计算机就计算出它的指纹,然后比较该指纹是否已经在哈希表中,来决定是否下载这个网页。这种整数的查找比原来字符串查找,可以快几倍到几十倍。
产生信息指纹的关键算法是伪随机数产生器算法(prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单,就是将一个数的平方掐头去尾,取中间的几位数。比如一个四位的二进制数 1001(相当于十进制的9),其平方为 01010001 (十进制的 81)掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机,也就是说两个不同信息很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。
信息指纹的用途远不止网址的消重,信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,
无法根据信息指纹推出原有信息,这种性质, 正是网络加密传输所需要的。比如说,一个网站可以根据用户的Cookie 识别不同用户,这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份,这样就可以保护用户的隐私。在互联网上,加密的可靠性,取决于是否很难人为地找到拥有同一指纹的信息, 比如一个黑客是否能随意产生用户的 cookie。从加密的角度讲 MersenneTwister,算法并不好,因为它产生的随机数有相关性。
互联网上加密要用基于加密伪随机数产生器(csprng)。常用的算法有 MD5 或者 SHA1 等标准,它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。值得一提的事,SHA1 以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌, 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久,但真正的广泛应用是在有了互联网以后,这几年才渐渐热门起来。
浪客系列问题之十三
数学反证法及其应用的论文
数学 请教射影定理及其应用 谢谢
数学之美,你怎么看?
系列翻译及回答十三
WAP技术及其应用
遗传算法及其应用
遗传算法及其应用
离心现象及其应用
什么是IEEE1394及其应用?
什么是IrDA及其应用?
反函数及其应用
如何求导,及其应用
电磁学基本知识及其应用
哪里有下载韩中庚编的《数学建模方法及其应用》急需,谢谢合作!!!!!
哪里有下载韩中庚编的《数学建模方法及其应用》急需,谢谢合作!!!!!
数学应用
数学应用
数学应用
数学应用
数学应用
大学专业中的:材料化学;机械设计制造及其自动化;环境工程;土木工程;数学与应用数学都学什么?
求助 采撷数学之美 这句话用英语怎么说
求上联 走近数学走进数学走尽数学,数学之美美不胜收。