|
|
在开发Booso新闻搜索引擎的时候，出现一个问题就是有很多的新闻属于转载的形式，要判断新闻是否转载，经过实验，我发现可以用“平移”算法来实现。
"平移算法"非常简单易用，就是比较两个文章／字串中最高的重叠率和平均重叠的长度。
例如我们有两个文章的标题：
"报告显示中国ip视频通信应用早于西方国家_通讯与电讯_科技时代_新浪网"
http://269s.tinline.com/26819/26820.htm
"权威机构调查显示中国ip视频通信应用早于西方_搜狐it"
http://269s.tinline.com/8765/8766.htm
以上两个新闻是转载同一来源，但是略做了更动，根据平移算法，我们固定一个字串，然后将另外一个字串从末尾对应第一字串的开头进行平移，然后计算两个字串之间的交集。如果字符完全一样则为1，不一样为0，将所有的值加起来。
"________报告显示中国ip视频通信应用早于西方国家_通讯与电讯_科技时代_新浪网"
"权威机构调查显示中国ip视频通信应用早于西方_搜狐it"
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0"
可以看到当B和A平移到一定的位置的时候能够找到最大的重叠度。上例是14个连续字符。
相识性：AB重叠部分／（A的长度 ＋ B的长度 - AB重叠的长度）
14／ (33+25-14) = 31%
一般超过20%即可判断为相同主题或者是转载同一来源。
平移算法的功能：
1] 实现对高度相识性的文章进行识别。转载，来源的识别。
2] 可以发现主题，发现核心内容。
例如实现匹配的部分，上例是
A&B = “中国ip视频通信应用早于西方”
是完全匹配的部分，就是相识文章的最核心的内容。
|
|
