February 18, 2006
信息指纹与消重算法::[Search Engine]
在半周的搜索引擎沙龙上在讨论Lucene的时候做猎兔分词的罗刚提到了信息指纹，我趁这个机会介绍一下信息指纹和消重。
信息指纹：就是提取一个信息的特征，通常是一组词或者一组词＋权重，然后根据这组词调用特别的算法，例如MD5，将之转化为一组代码，这组代码就成为标识这个信息的指纹。
从理论上讲，每两个不同文本的特征信息是不同的，那么得到的代码也应该是不一样的，就象人的指纹。
搜索引擎在建立索引的时候需要对重复内容的网页进行识别和消重，这就要用到信息指纹。
例如，通常搜索引擎要先对网页进行消噪，就是净化网页，将一些模版类的，无用的广告等剔除调。然后得到预处理后的网页，然后对网页进行向量化处理，简单的讲就是分词，统计，并按照词频生成一个列表。
例如：
网页12
搜索10
引擎7
...
...
然后取前N个关键词作为信息的矢量，例如：[网页12搜索10引擎7] 这是可以直接进行MD5哈系，或者按照其它规则进行重拍后进行MD5哈系。例如本例，取前３个关键词，在进行哈系，得到的信息指纹就是：a7eb9d92a83cf438881915e0bc2df70b
这样a7eb9d92a83cf438881915e0bc2df70b 就作为本文档的指纹和以往的文档进行比较，如果有相同的，就说明指纹上看是一样的，就可以进入消重处理。
至于关键词的权重，因为有众多的提取算法，比较常用的是nf/df，这里不在赘述。另外高频词和停止词的消除也是必要的，这点可以参考基于信息噪音模型的分类算法，那个ppt里我细数了如何定义“噪音”，如何进行消噪。
Posted at February 18, 2006 11:23 PM by Liang at 11:23 PM | Comments (7) | TrackBack(1) | Booso!| Niu.la收藏!Trackback
You can ping this entry by using http://www.wespoke.com/cgi-bin/mt/mt-tb.cgi/851
今天才注意到我的博客名叫agile & sungny,sungny这个家伙好几年没到这里来了，以前还发个文章，估计都把这儿忘记了，正好我独占这里了，因此我决定改名，呵呵。
晚上搞了一下网页...
Trackbacked from http://agilejava.blogbus.com/logs/2006/03/2117342.html with 改名 on agile.
Comments
进行MD5或者SHA1，可以将不定长的string hash成定长的128bit整数。且这个过程不可逆（到目前为止）。碰撞已经被山东大学的王小云攻破。王小云已经证明用模差分法可以快速找到碰撞。所以在不考虑算法被攻破或碰撞的前提下，采用MD5或其他hash方法只可以提高比较速度，节省内存空间。既然已知此过程不可逆，那么这个信息指纹将被永远用作布尔比较。如果放在VSM向量空间模型中，是无法用夹角比较相似度的,即"有多么相似?" . 而只会比较"是否相似?" . 即一旦进行了hash,就永远无法对相关信息按照相似度进行排序了. 据我所知MD5在搜索引擎中还是主要用作URL的hash,至于信息指纹对信息相关度的判断还有待深入研究,毕竟这是一种简单且快速的方法.
Posted by: 张博文 at February 19, 2006 05:07 PM from 221.218.185.120同意1楼, 网页不会绝对相同,相似度比较更合理一点.
page1 page2
keyword_n [hit_n] keyword_n' [hit_m']
...
keyword_m [hit_m] keyword_n' [hit_m']
是否可以通过距离来计算相似度呢,取Top x个keyword,通过比较hit_n' - hit_n, 可以计算出page2和page1有多相似.如果能在指纹信息里包含上面的特征值,那用起来更好啊.
Posted by: Rainman at February 22, 2006 02:57 AM from 216.145.49.15 人和雨和地面的相对运动可以简化成人在雨滴空间内的运动。
在不考虑人的各方向截面面积差别的情况下，在雨滴固定且均匀分布的空间：如果没有风，人在垂直方向上以雨滴自由下落的速度运动；同时人在水平方向上跑动。这两个运动的距离和就是人淋到的总雨量。
这其中，人需要行进的距离是恒定的，雨滴下落的速率也是恒定的并且与人的运动方向垂直，所以人跑动的速度不会引起垂直方向上的速度变化。当然人跑得越快，所需的时间越短，当然淋到的雨也就越少。
但如果有风，雨滴与人的运动方向不垂直的话，人的跑动速度就会影响到另一个运动了。
如果风与人的跑动同向且同速，那么这时候雨滴的运动速度为负，复合速度为零，所以人不会淋到雨。
如果风向和人的跑动方向正好相反，那么这时候雨滴的运动速度为风速+人跑动的速度*2，人会淋到最多的雨量。
其他的风向都是这两种情况的中间情形
>简单的讲就是分词，统计，并按照词频生成一个列表
有两个问题还需要克服：
1）需要一种方式提取到真正的关键词，而不是象“你“”我““的”，“当然”这样频率高但无意义的词。可以考虑建立高频常见词库，用来过滤网页关键信息。
2）有的词是真正的关键词，但在一个页面中可能只出现一两次，按普通的排序方法，得到的结果肯定是效果不佳，应该对这些次施以更高的权重，问题是如何知道给哪些词高权重，看来还是需要建立一个列表。
Posted by: ffish at February 27, 2006 03:45 PM from 222.90.77.149