信息指纹(Fingerprint)及其应用

1.应用:   

 i.网页地址去重

          网页地址有100个字符,存储5000亿个网址本身需要50T的容量,而Hash表的存储效率只有50%,所有存储爬虫已经爬过的网址需要100T的内存

          解决办法:将网址随机映射到128个bit上,即16个字节的整数空间上,每个网址只需要16个字节,而不是100个了,内存的需求量下降到原来的1/6不到,这16个字节的随机数,就称作该网址的信息指纹

          步骤:a.现将网址转为数值(每个字符对应的ascii)b.通过伟随机数产生器,将得到的数值转为16个字节的整数

          在互联网上加密要使用基于加密的伪随机数产生器,常用MD5或者SHA-1等标准

      ii.判定集合是否相同:

          a.场景:

               两个查询,如“北京 中关村 星巴克”和“星巴克 中关村 北京”是否相同;一个人是否用两个不同的账号对同一群人发垃圾邮件;网上的一首歌是否是盗版别人的 

             需要将查询或者群体的邮件列表存储在两个集合里,然后判断两个集合是否相同即可  

        b.算法选择:

               两次变量对比:时间复杂度为O(N^2) 

             先排序,后遍历对比:时间复杂度为O(NlogN)

               先将一个集合放入HashSet,然后判断另一个集合的元素是否都在HashSet里,时间复杂度为O(N),但是有额外的空间负责度O(N) 

               完美的方案:对单个集合的元素求其信息指纹,然后相加,与两一个集合的信息指纹和比较,来判断两个集合元素是否相同,时间复杂度为O(N);用加法的交换率,消除了元素次序对结果的影响

           c.电子邮件的问题:

               如果按照b的思路,两次邮件列表里只有一两个用户不同,则需要对步骤进行一个修改,即按照同样的规则(如尾数为24的)对邮件列表进行过滤,如果他们的指纹相同,或者是否有80%以上的相同率,来判断两个邮件列表是否相同

           d.两篇网页、文章是否相同

               对两篇文章先去掉常见词、然后去掉出现一次的词(噪音),在剩下的词中对IDF最大的词进行信息指纹的求和、比较,即可判断是否是相同的文章;为了保证容错性,采取了相似哈希的信息指纹(见后文)

      iii.视频的反盗版:

          视频匹配两个核心技术:关键帧的提取和特征的提取,MPEG视频每秒有30帧图像,但是只有极少数的关键帧是完整的影像,其他帧存储的是和关键帧相比的差异值

          提取出视频中的关键帧(类似于主题词对新闻),然后对其最信息指纹的 2.指纹重复的可能性:     128位的伪随机数,其k个指纹不重复的概率为

,Pk随着k的增大而减小,当Pk<0.5时,k个指纹重复的期望超过1,此时k的最大值为:          

     在128bit时,N为2^128,所以k约等于2^64,即一千八百亿亿次才能重复一次,因此不同信息产生相同指纹的可能性几乎为0 3.相似哈希(Simhash)     如果网页中若干词T1,T2,…,Tk,其权重(如TF-IDF)为W1,W2,…,Wk,先计算其信息指纹(这里以8bit为例),在计算相似哈希:     i.扩展:          将8bit的信息指纹扩展为8个实数:对于每一个词一个词Tk,如果其第n位为1,则第一个实数Rn加Wn,如果为0,则Rn减Wn;最后得到8个实数,     ii.收缩:          然后将8个实数收缩,Rk>0?1:0,变为一个8位的二进制,即是其相似哈希指纹      iii.场景:          少数权重小的词不同的情况下,相似哈希也会相同          用64位的相似哈希做对比,如果两者相差一位,其网页内容重复的可能性大于80%

留下评论