MyRss之三---从LCS到MCC去重复

Rain 发表于 2008-04-22 20:15:13

Toy程序中很重要的一个功能是去重：即去掉那种转载流的文字，转载扩赛了信息但是也造成了相当麻烦的信息冗余，我不想看的信息逼着我看了一遍又一遍。
最牛逼的方法当然是能比较两个文章的全文，看全文的匹配度了，但是这个方法的时间代价太大。还有那种选取一部分Digest 出来比较的方法理论性远远大于使用性。最直接的方法就是看两个文章的标题的最长公共子串，亦即LCS( longest common substring).

LCS的原理非常的简单：

A串为：   A1 A2 A3 .....  An
B串为： B1 B2 B3 .....  Bm

只要反复的算下AB以各种位置叠在一起的最长连续字符个数就好了

数学上来说：就是写成这样一个矩阵：
match[n][m]=
  A1 A2 ..... ..... Am
B1 01 01 ... ... 01
B2 01 01 ... ... 01
... ... ... ... ... ...
Bn 01 01 ... ... 01

中间的值match[i][j]都是0或者1 (match[i][j]=1 means Bi=Aj)，下面就在这个表中选出最长的连续对角线都是1的串，对应的子串就是AB的最大的匹配。

举个例子吧：

from:  http://www.5do8.com/blog/doc/569/index.aspx

  A= I MISS MY CODE HI

  B= One Like MY Code

  i m i s s m y c o d e h i
o 0 0 0 0 0 0 0 0 1 0 0 0 0
n 0 0 0 0 0 0 0 0 0 0 0 0 0
e 0 0 0 0 0 0 0 0 0 0 1 0 0
l 0 0 0 0 0 0 0 0 0 0 0 0 0
i 1 0 1 0 0 0 0 0 0 0 0 0 1
k 0 0 0 0 0 0 0 0 0 0 0 0 0
e 0 0 0 0 0 0 0 0 0 0 1 0 0
m 0 1 0 0 0 1 0 0 0 0 0 0 0
y 0 0 0 0 0 0 1 0 0 0 0 0 0
c 0 0 0 0 0 0 0 1 0 0 0 0 0
o 0 0 0 0 0 0 0 0 1 0 0 0 0
d 0 0 0 0 0 0 0 0 0 1 0 0 0
e 0 0 0 0 0 0 0 0 0 0 1 0 0
























那个mycode就是最长匹配的串
在具体计算的时候考虑到汉字字符的多变性和英文很不一样，我们可以直接计算一个对角线上的所有的1而不用考虑联系性。
就变成了MCC(Max common characters)了，而这个MCC就是我们去判定重复的一个重要依据。
如果len(MCC) / min( len(string_A) ,len(string_B))>valve_Value就判定为转载。
-----------------------

这里可以有一个非常重要的改进，认为连续匹配会有非线性加成，如match_degree=sigma( len(common_substring[i])^2)
甚至我觉得可能某些搜索引擎就是这么干的。。【未验证】

----------------------
这样就实现了新闻的唯一性的保证，为了确保系统的效率不会被这个比较拖累的太多，可以只比较最近3个月的标题。

晚上写一个实现，能配合现在已经有的模块实现标题的唯一性。
-----------------------
filter.py

关键词(Tag): python mcc lcs 最长公共子串 最多公共字符集i

相关日志:

阅读303次 评论1条 个人主页 扔小纸条 文件夹: 不文艺且现实
收藏: QQ书签 del.icio.us 订阅: Google 抓虾

最新评论

发表评论

* 昵称

已经注册过? 请登录

新用户请先注册 以便能显示头像及追踪评论回复
Email
网址
* 评论
表情
 
 

分类小组论坛
杂谈, 娱乐、八卦, 文学、艺术, 体育, 旅游、同城, 象牙塔, 情感, 时尚、生活, 星座, 科技

请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

相关法律法规
全国人大常委会关于维护互联网安全的决定
中华人民共和国计算机信息系统安全保护条例
中华人民共和国计算机信息网络国际联网管理暂行规定
计算机信息网络国际联网安全保护管理办法
计算机信息系统国际联网保密管理规定