中国的博客，走近我们的产品、技术和文化
Google 中国的博客，走近我们的产品、技术和文化
数学之美 系列十三 信息指纹及其应用
2006年8月3日
发表者：吴军，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 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。但是大家不必恐慌， 因为这和黑客能真正攻破你的注册信息是还两回事。
信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。
標籤
编程之夏，UR
创新
创意改善社会 公益温暖中国
促进智能能源利用
大学
谷歌翻译，即时相机翻译，Instant Camera Translation
谷歌十周年系列
谷歌艺术与文化
观妙中国，Shadow Art，智玩皮影
广告
广告安全
互联网，Internet
科技
女性开发者
社会
视频广告
数据中心
数字营销
搜索
网站管理员
文化研究所
艺术计划
音乐搜索
愚人节
增强型广告系列
智能隐形眼镜项目
中小企业
adexchange
Admob
admob sdk
Ads
Adsense
AdWords
android
android m
Android应用开发中国大学生挑战赛
App Inventor
Calendar
cardboard
CES
Chrome
Chrome Web Store
Chrome，Chrome实验
Chrome实验
CI
Code Jam
corporate
Creative
Cross-device
Cultural Institute
culture
Data Center
DevArt
Developer
display
diversity
Doodle
DoubleClick
G+
G2G，Culture
GA&C
gaming
Global Impact Awards
Gmail
Gogle科学挑战赛
Good to Know
Google Ads
Google AdWords
Google Analytics
Google Art Project
Google Arts & Culture
Google Code-in竞赛
Google Demo Day Asia
Google Docs
Google Doodle
Google Drive
Google Drive 云端硬盘
Google Fiber
Google Font
Google for Startups
Google Green
Google I/O
Google Image Search
Google Keep
Google partners
Google Play
Google Science Fair
Google Search
Google Top Contributor Summit
Google Translate
Google Trend
Google Trends
Google Zeitgeist 2012
Google安全系统
Google博士生奖研金
Google翻译
Google奖学金
Google杰出贡献者峰会
Google科学挑战赛
Google网站管理员
Google网站管理员，Webmaster
Google文化研究所
Google在线营销挑战赛
Google中国教育高峰会
IME 输入法
Innovation
Made with Code
maps
mobile ads
mobile ads sdk
Modoo
moonshot
native ads
Nexus
programmatic buying
Project X
Pwn20wn及Pwnium3 黑客大赛
Remarketing. Ads
Search
Security
smb
Solve for X
Street view
student
UR
VR
Web Platform Docs
web security
Webmaster
year in search 2014
YouTube
zeitgeist
博客归档
2024
11月
10月
8月
7月
6月
5月
4月
3月
2月
1月
2023
12月
11月
10月
9月
5月
4月
3月
2月
2022
11月
10月
5月
4月
2月
1月
2021
10月
9月
5月
4月
3月
2月
2020
12月
5月
4月
3月
2019
10月
8月
7月
6月
5月
4月
3月
2018
12月
10月
9月
8月
7月
6月
5月
3月
2月
1月
2017
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2016
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2015
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2014
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2013
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2012
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2011
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2010
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2009
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2008
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2007
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
1月
2006
12月
11月
10月
9月
8月
7月
6月
5月
4月
3月
2月
Feed
