信息指纹及其应用

大家好，欢迎来到IT知识分享网。

什么是信息指纹

在前面的章节中，我们讲到，一段文字所包含的信息，就是它的信息熵。如果对这段信息进行无损压缩编码，理论上编码后的最短长度就是它的信息熵。当然，实际编码长度总是要略长于它的信息熵的比特数。但是,如果仅仅要区分两段文字或者图片，则远不需要那么长的编码。任何一段信息( 包括文字、语音、视频、图片等等)，都可以对应一个不太长的随机数，作为区别它和其他信息的指纹(Fingerprint)。只要算法设计得好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

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

http://www.baidu.com/s?ie=gb2312&bs=��ѧ֮��&sr=&z=&cl=3&f=8&wd=����+��ѧ֮��&ct=0

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

893249432984398432980545454543

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

产生信息指纹的关键算法是伪随机数产生器算法（Pseudo-random number generator , PRNG)。最早的 PRNG 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数 1001（相当于十进制的9），其平方为 01010001 (十进制的 81）掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。现在常用的 Mersenne Twister 算法要好得多。

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

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

信息指纹的虽然历史很悠久，但真正的广泛应用是在有了互联网以后，这几年才渐渐热门起来。上面一节讲述了在网络爬虫中利用信息指纹可以快速而经济(节省服务器)地判断一个网页是否已下载过。信息指纹在互联网和自然语言处理中还有非常多的应用，这里不可能(也不必要)一一列举，只是找几个有代表性的例子。

用例1：判定集合相同

在网页搜索中，有时需要判断两个查询用词是否完全相同(但是次序可能不同)，比如“北京中关村星巴克” 和“星巴克北京中关村”用词完全相同。更普遍的讲法是判断两个集合是否相同(比如一个人是否用两个不同的Email帐号对同一群人群发垃圾邮件)。解决这个问题有各种各样的方法，没有绝对正确的和错误的，但是有好的方法和笨的方法。

最直接的笨办法是对这个集合中的元素一一做比较，这个方法计算的时间复杂度是\(O(N^2)\)，其中N是集合的大小。如果谁面试时这么回答我,我肯定不会让他通过。

稍微好一点的办法是将两个集合的元素分别排序，然后顺序比较，这样计算时间的复杂度是\(O(NlogN)\)，比前面那种方法好了不少，但还不是很好。与这个方法处于同一个水平的是将第一个集 合放在一张哈希表中，然后把第二个集合的元素一一和哈希表中的元素作对比。这个方法的时间复杂度为\(O(N)\),达到了最佳。但是额外使用了\(O(N)\)的空间，而且代码很复杂，不完美。

完美的方法是计算这两个集合的指纹，然后直接进行比较。我们定义一个集合\(\mathrm{S}=\left\{e_1, e_2, \cdots, e_n\right\}\)的指纹\(F P(S)=F P\left(e_1\right)+F P\left(e_2\right)+\cdots+F P\left(e_n\right)\)，其中\(F P\left(e_1\right), F P\left(e_2\right), \ldots, F P\left(e_n\right)\)分别为\(S\)中这些元素对应的指纹。由于加法的交换率，保证集合的指纹不因元素出现的次序而改变，如果两个集合元素相同，那么它们的指纹一定相同。当然，不同元素的指纹也相同的概率非常非常小，在工程上完全可以忽略。我们在延伸阅读里会告诉读者这个概率有多小。

利用信息指纹的方法计算的复杂度是\(O(N)\),而且不需要额外的空间，因此是最佳方法。类似的应用还有很多，如比较网上的一首歌是否是盗版别人的，只要算算这两个音频文件的信息指纹即可。

用例2: 判定集合基本相同

爱思考的读者可能会挑战我:发垃圾邮件的人哪有这么傻，从两个帐号发出的垃圾邮件收信人都相同?如果稍微变上一两个，上面的方法不就不起作用了吗?解决这个问题需要我们能够快速判断两个集合是否基本相同，其实只要将上面的方法稍作改动即可。

可以分别从两个帐号群发的接收电子邮件地址清单(Email Address List)中按照同样的规则随机挑选几个电子邮件的地址，比如尾数为24的。如果它们的指纹相同,那么很有可能这两个接收的电子邮件单子基本相同。由于挑选的数量有限，通常是个位数，因此也很容易判断是否是80%,或者90%重复。上述判断集合基本相同的算法有很多实际的应用，比如在网页搜索中，判断两个网页是否是重复的。如果把两个网页(的正文)从头比到尾，计算时间太长，也没有必要。我们只需对每个网页挑出几个词，这些词构成网页的特征词集合。然后计算和比较这些特征集合的信息指纹即可。在两个被比较的网页中，常见的词一般都会出现，不能作为这两篇文章的特征。只出现一次的词，很可能是噪音，也不能考虑。在剩下的词中, 我们知道IDF大的词鉴别能力强，因此只需找出每个网页中IDF最大的几个词，并且算出它们的信息指纹即可。如果两个网页这么计算出来的信息指纹相同,它们基本上是相同的网页。为了允许有一定的容错能力,在Google里采用了一种特定的信息指纹——相似哈希( Simhash)。相似哈希的原理会在延伸阅读中介绍。

上面的算法稍作改进还可以判断一篇文章是否抄袭另一篇文章。具体的做法是，将每一篇文章切成小的片段，然后对这些片段用上述方法选择特征词的集合，并且计算它们的指纹。只要比较这些指纹，就能找出大段相同的文字，最后根据时间先后，找到原创的和抄袭的。Google 实验室利用这个原理做了一个名为CopyCat的项目，能够很准确地找出原文和转载(拷贝)的文章。

用例3：Youtube的反盗版

Google旗下的YouTube是全球最大的视频网站,和国内的视频网站不同，YouTube自身不提供和上传任何内容，完全由用户自己提供。这里的用户既包括专业的媒体公司，比如NBC和迪士尼，也包括个人用户。由于对后者没有太多上传视频的限制，一些人会上传专业媒体公司的内容。这件事不解决就会动摇YouTube的生存基础。

从上百万视频中找出一个视频是否是另-一个视频的盗版，并不是一件容易的事情。一段几分钟的视频，文件大小有几兆到几十兆，而且还是压缩的，如果恢复到每秒30帧的图像，数据量就会大得不得了。因此，没有人通过直接比较两段视频的方法来确定它们是否相似。

视频的匹配有两个核心技术,关键帧的提取和特征的提取。MPEG视频(在NTSC制的显示器上播放)虽然每秒钟有30帧图像，但是每一帧之间的差异不大。(否则我们看起来就不连贯了。)只有极少数的帧是完整的图像,这些称为关键帧。其余帧存储的只是和关键帧相比的差异值。关键帧对于视频的重要性，就如同主题词对于新闻的重要性一样。因此，处理视频图像首先是找到关键帧，接下来就是要用一组信息指纹来表示这些关键帧了。

有了这些信息指纹后，接下来查盗版的事情就类似于比较两个集合元素是否相同了。Google 收购YouTube后，由Google研究院研究图像处理的科学家们开发出的反盗版系统，效果非常好。由于可以找出相同的视频的原创和拷贝，Google制定了一个很有意思的广告分成策略:虽然所有的视频都可以插人广告，但是广告的收益全部提供给原创的视频，即使广告是插人在拷贝的视频中。这样一来，所有拷贝和上传别人的视频的网站就不可能获得收入。没有了经济利益，也就少了很多盗版和拷贝。

拓展1 指纹重复概率计算

信息指纹是通过伪随机数产生的。既然是伪随机数，两个不同的信息就有可能产生同样的指纹。这种可能性从理论上讲确实存在,但是非常小。至于有多小，我们就在这1节中分析。

假定一个伪随机数产生的范围是 \(0 \sim N-1\), 共 \(N\) 个。如果是 128 位的二进制, \(N=2^{128}\), 这是一个非常巨大的数字。如果随意挑选两个指纹, 那么它们重复的可能性就是 \(1 / N\), 不重复的可能性是 \(\frac{N-1}{N}\), 因为第一个可以是任一个, 第二个只有 \(N-1\) 的可选余地。如果随意挑选三个指纹, 要保证不重复, 第三个只有 \(N-2\) 的可选余地, 因此, 三个不重复的概率为 \(\frac{(N-1)(N-2)}{N^2}\) 。以此类推, \(k\) 个指纹不重复的概率 \(P_k=\frac{(N-1)(N-2) \ldots(N-k+1)}{N^{k-1}} 。\)

\(P_k\) 随着 \(k\) 增加而减小, 即产生的指纹多到一定程度, 就可能有重复的了。 如果 \(P_k<0.5\), 那么, \(k\) 个指纹重复一次的数学期望超过 1 。现在来估计一下这时候 \(k\) 的最大值。

上述不等式等价于

当 \(N \rightarrow \infty\),

这个概率需要小于 \(0.5\), 因此

这等效于

由于 \(k>0\), 上述不等式有唯一解

也就是说, 对于一个很大的 \(N, k\) 是一个很大的数字。如果用 MD5 指纹 (虽然它有缺陷), 它有 128 位二进制, \(k>2^{64} \approx 1.8 \times 10^{19}\) 。 也就是说, 每一千八百亿亿次才能重复一次, 因此, 不同信息产生相同指纹的可能性几乎为零。即使采用 64 位的指纹, 重复的可能性依然很低。

拓展2 相似哈希

相似哈希是一种特殊的信息指纹，是Moses Charikar在2002年提出来的,但是真正得到重视是当Google在网页爬虫中使用它，并且把结果发表在WWW会议上以后。虽然Charikar的论文写得比较晦涩，但是相似哈希的原理其实并不复杂。不妨用一个 Google 在下载网页时排查重复网页的例子来说明。

假定一个网页中有若干的词 \(t_1, t_2, \ldots, t_k\), 它们的权重 (比如 TF-IDF 值) 分布为 \(w_1, w_2, \ldots, w_k\) 。先计算出这些词的信息指纹, 为便于说明, 假定只用 8 位二进制的信息指纹。当然在实际工作中不能用这么短的, 因为重复概率太高。计算相似哈希分为两步。

第一步我称之为扩展, 就是将 8 位二进制的指纹扩展成 8 个实数, 用 \(r_1, r_2, \ldots, r_8\) 表示, 这些实数的值如下确定:

首先, 将它们的初值设置为 0 , 然后, 看 \(t_1\) 的指纹 ( 8 位), 如果 \(t_1\) 的第 \(i\) 位 为 1 , 在 \(r_i\) 上加上 \(w_1\); 如果为 0 , 在 \(r_i\) 上减去 \(w_1\) 。例如, \(t_1\) 的指纹为 10100110 (随便给的), 这样处理完 \(t_1\) 后, \(r_1\) 到 \(r_{\mathrm{8}}\) 的值如下:

处理了第一个词后，r1到r8的值

接下来处理第二个词 \(t_2\), 假如它的指纹是 00011001 , 那么根据上面逢 1 相加、逢 0 相减的原则, 因为第 1 位是 0 , 因此 \(r_1\) 上应该减去 \(t_2\) 的权重 \(w_2\), 这样 \(r_1=w_1-w_2\), 如此 \(r_2, \ldots, r_8\) 做同样处理, 结果如下表所示。

当扫描完全部词时, 就得到了最后的 8 个数 \(r_1, \ldots, r_8\), 第一步扩展过程到此结束。
假定 \(r_1, r_2, \ldots, r_8\) 的值在扩展后变为如下表所示的那样:

处理完所有的词后, \(r_1\) 到 \(r_8\) 的值, 然后把正数变成 1 , 负数变成 0

第二步我称之为收缩, 就是把 8 个实数变回成一个 8 位的二进制。这个过程非常简单, 如果 \(r_i>0\), 就把相应的二进制的第 \(i\) 位设置成 1 , 否则设置成 0 。这样就得到了这篇文章的 8 位相似哈希指纹。对于上面的例子, 这篇文章的 Simhash \(=00110001\) 。

相似哈希的特点是, 如果两个网页的相似哈希相差越小, 这两个网页的相似性越高。如果两个网页相同, 它们的相似哈希肯定相同。如果它们只有少数权重小的词不同, 其余的都相同, 几乎可以肯定它们的相似哈希也会相同。值得一提的是, 如果两个网页的相似哈希不同, 但是相差很小, 则对应的网页也非常相似。用 64 位的相似哈希做对比时, 如果只相差一两位, 那么对应网页内容重复的可能性大于 \(80 \%\) 。这样通过记录每个网页的相似哈希, 然后判断一个新网页的相似哈希是否已经出现过, 可以找到内容重复的网页, 就不必重复建索引浪费计算机资源了。

信息指纹的原理简单, 使用方便, 因此用途非常广泛, 是当今海量数据处理必不可少的工具。

小结

信息指纹可以理解成将一段信息 (文字、图片、音频、视频等) 随机地 映射到一个多维二进制空间中的一个点（一个二进制数字) 。只要这个随机函数做得好, 那么不同信息对应的这些点不会重合, 因此这些二进制的数字就成了原来信息所具有的独一无二的指纹。

原文来源

吴军. 数学之美 : Beauty of mathematics[M]. 人民邮电出版社, 2014.