`
wangdei
  • 浏览: 372363 次
社区版块
存档分类
最新评论

(转贴)数学之美 系列十三 信息指纹及其应用

阅读更多

数学之美 系列十三 信息指纹及其应用
2006年8月3日 上午 11:17:00

发表者:吴军,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 以前被认为是没有漏洞的,现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌, 因为这和黑客能真正攻破你的注册信息是还两回事。

信息指纹的虽然历史很悠久,但真正的广泛应用是在有了互联网以后,这几年才渐渐热门起来。
http://googlechinablog.com/2006/08/blog-post.html

分享到:
评论

相关推荐

    易语言源码动网转贴.rar

    动网转贴可能需要解析这些数据来获取帖子的信息,如标题、内容、作者等,并将它们封装到转发请求中。 3. **用户身份验证**:为了确保用户权限和安全性,动网转贴功能可能涉及到用户登录状态的检查和验证,这可能...

    电子政务-导电泡棉转贴装置.zip

    综上所述,"导电泡棉转贴装置"在电子政务中的应用涉及到硬件设计、设备维护、电磁兼容性和法规遵从等多个方面,是保障电子政务系统稳定运行的关键技术之一。通过阅读"行业分类-电子政务-导电泡棉转贴装置.pdf"这份...

    动易系统的论坛转贴工具

    《动易系统的论坛转贴工具详解与应用》 在互联网信息交流日益频繁的今天,论坛作为用户互动的重要平台,其内容分享与传播的作用不容忽视。动易系统的论坛转贴工具,便是为了解决用户在论坛间便捷分享内容而设计的一...

    动网转贴.e.rar

    动网是中国早期知名的网络论坛软件之一,提供了丰富的社区功能,允许用户发帖、回帖、互动等。这个压缩包可能是从动网论坛导出的数据,用于数据迁移、备份或者分析。 【描述】由于提供的描述仅为"动网转贴.e.rar",...

    动网转贴.zip易语言项目例子源码下载

    《易语言项目实例——动网转贴》 易语言,作为一种中文编程语言,以其独特的语法和易用性,深受广大编程爱好者尤其是初学者的喜爱。这个名为“动网转贴”的项目,是易语言编程实践中一个典型的例子,它为学习者提供...

    BFC UBB转贴器

    由于与BFC采集器使用的是相同的转换模块,本程序同时可用来做采集信息验证工作,只要它能够转换的代码BFC采集器即可正常转换为UBB代码。 <br> 转换模块升级时可直接用BFC采集器中的EnginLib.dll文件...

    行业分类-设备装置-FPC吸附胶纸转贴组件.zip

    本压缩包文件"行业分类-设备装置-FPC吸附胶纸转贴组件.zip"主要关注的是FPC在实际应用中的一个重要环节——FPC吸附胶纸转贴组件。这个组件在FPC的制造和组装过程中起到关键作用,确保FPC能够稳定地固定在设备上,并...

    易语言动网转贴.rar

    6. **界面设计**:如果这是一个图形用户界面的应用,那么易语言的窗口部件和界面设计也是重要部分,需要考虑用户体验和交互设计。 总的来说,"易语言动网转贴"可能是一个结合了网络爬虫、数据解析、数据库操作等多...

    论坛专用屏蔽干扰码转贴工具

    标题中的“论坛专用屏蔽干扰码转贴工具”指的是一个专为论坛设计的软件,它的主要功能是处理并转换论坛上常见的干扰码,以便用户能够顺利地复制和粘贴信息。在论坛交流中,有时为了防止恶意爬虫或者保护内容不被搜索...

    Html处理软件、转贴工具(源代码)

    去除Html中的干扰码等(样例中以轻之国度的干扰码为例) 配置文件语法: 方法类型(整数) 最大匹配长度(整数) 字符串1(删除开头) 字符串2(删除结尾) 方法类型: 1:删除单行 2:删除行与行之间的

    行业资料-电子功用-全自动导电布成型转贴穿管设备及工艺的介绍分析.rar

    标题"行业资料-电子功用-全自动导电布成型转贴穿管设备及工艺的介绍分析.rar"表明这是一份关于电子行业中的特定应用——全自动导电布成型转贴穿管设备及其相关工艺的详细介绍。导电布是一种具有导电性能的材料,常...

    东度极品论坛转贴工具

    东度极品论坛转贴工具东度极品论坛转贴工具

    行业文档-设计装置-木器、玻璃用贴花纸生产及转贴方法.zip

    《木器、玻璃用贴花纸生产及转贴方法》是一个深入探讨装饰材料工艺的行业文档,主要聚焦于贴花纸在木器和玻璃制品上的应用。这份文档可能包含了从贴花纸的设计、生产到实际转贴过程中的各种技术细节和实践经验。 1....

    jquery的转贴功能实现

    可以使用jQuery选择器获取这些信息,例如`$("meta[property='og:title']").attr("content")`来获取Open Graph标题。 3. **构建分享链接**:不同的社交平台有不同的API或URL结构来接受分享请求。例如,Facebook使用`...

    Spark 入门实战系列

    Spark 入门实战系列,适合初学者,文档包括十部分内容,质量很好,为了感谢文档作者,也为了帮助更多的人入门,传播作者的心血,特此友情转贴: 1.Spark及其生态圈简介.pdf 2.Spark编译与部署(上)--基础环境搭建....

    论坛转贴 v1.0 JS版-源码.zip

    【标题】"论坛转贴 v1.0 JS版-源码.zip" 提供的是一个基于JavaScript的论坛转贴功能的源代码实现。JS版通常指的是使用JavaScript编程语言编写的版本,这表明该软件可能主要用于网页端,利用浏览器的JavaScript引擎...

    史上最全的转贴代码

    【标题】:“史上最全的转贴代码”通常指的是一个包含大量可复用代码片段或解决方案的集合,这些代码可能来自于各种编程语言,旨在帮助开发者快速解决问题或者作为学习参考。这样的资源对于初学者和经验丰富的程序员...

    易语言动网转贴

    1. **窗口名**:在编程中,窗口名通常指的是一个应用程序或界面的标识符,用于区别不同的窗口。在易语言中,可以使用特定的函数来获取或设置窗口的名称。 2. **较验**:这可能是“校验”的误写,校验通常涉及到数据...

Global site tag (gtag.js) - Google Analytics