December 02, 2004
平移算法简介::[Search Engine]
在开发Booso新闻搜索引擎的时候，出现一个问题就是有很多的新闻属于转载的形式，要判断新闻是否转载，经过实验，我发现可以用“平移”算法来实现。
"平移算法"非常简单易用，就是比较两个文章／字串中最高的重叠率和平均重叠的长度。
例如我们有两个文章的标题：
"报告显示中国ip视频通信应用早于西方国家_通讯与电讯_科技时代_新浪网"
http://tech.sina.com.cn/t/2004-12-01/1231468255.shtml
"权威机构调查显示中国ip视频通信应用早于西方_搜狐it"
http://it.sohu.com/20041201/n223268718.shtml
以上两个新闻是转载同一来源，但是略做了更动，根据平移算法，我们固定一个字串，然后将另外一个字串从末尾对应第一字串的开头进行平移，然后计算两个字串之间的交集。如果字符完全一样则为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视频通信应用早于西方”
是完全匹配的部分，就是相识文章的最核心的内容。
Posted at December 2, 2004 12:20 PM by Liang at 12:20 PM | Comments (5) | TrackBack(1) | Booso!| Niu.la收藏!Trackback
You can ping this entry by using http://www.wespoke.com/cgi-bin/mt/mt-tb.cgi/668
Trackbacked from http://wsop-ps2-en.isismedia.com with I really liked your comments here. I hope you're going to update your site soon. on .
Comments
有个问题，Booso新闻搜索引擎只搜索新闻的标题么？
另外此算法在判断两篇文章是否为转载的时候，时间复杂度应该是O(n^2)吧，然后再将所有新闻两两组合判断转载，时间复杂度还是太高。
Posted by: Carl at December 2, 2004 10:36 PM from 218.30.119.82booso 的新闻搜索是全文搜索。
时间复杂程度的确是O(n^2)，可是你忘记了，先可以对所有的文章进行类别排序，然后每一篇只对类别相近的作判断即可。
1000个新闻源，进行10各分类，然后进行20个相近内的进行判断：10*100*2^20/2 ~ = 524288000
而2^1000=10715086071862673209484250490600018105614048117055336074437503883703\
51051124936122493198378815695858127594672917553146825187145285692314\
04359845775746985748039345677748242309854210746050623711418779541821\
53046474983581941267398767559165543946077062914571196477686542167660\
429831652624386837205668069376
没看懂你的意思:-(
类别排序指的是什么？排序就要有大小之分，如何比较两个新闻的大小呢？或许你指的是分类，但是毕竟转载的情况有限，类别还是太多。
另外两个计算公式都是什么啊？2^1000 ??!!!
Posted by: Carl at December 3, 2004 12:48 AM from 218.30.119.82做法：1] 先做分类，例如我们分类按照：科技／教育／互联网／。。。
2] 每一篇根据相识性只能分到一个类别里面
3］根据相似性排序。
4] 例如在“互联网”新闻里拍第 50 的只跟拍名在40-60之间的进行比较。
2^1000是2的1000次方。
Posted by: 6e at December 3, 2004 12:37 PM from 129.119.200.36多谢，理解你的意思了:-)
我知道2^1000是2的1000次方，但是不知道从何而来，呵呵
Posted by: Carl at December 3, 2004 09:56 PM from 221.194.28.166