如何用算法找出两个文件中是否具有雷同内容?

各位果壳的大侠们,求助!就是类似毕业论文的查重的功能,不过只需要找出给定的两个或多个文件的雷同并标识出来,求算法,谢谢谢谢!!

推荐  (0) | 9人关注关注
4个答案
25 0

欧漏,二维动态规划的效率不是最优的。。的复杂度还是太高了。。。一万行的两个文件,会使用到接近400M内存,花费时间也不可忍受
Unix系统里面自带的diff、git diff、meld等文件差异比较工具(当然windows上也有基于diff的windiff),主要问题是 longest common subsequence problem 最长子串问题,本质是个NP难的问题。
文献[1]介绍了一种复杂度的差异算法。。N是两个文本大小之和,D是从A文件修改到B文件得最小修改量。
总的结果就是diff可以在1秒内算出两个100k大小的文件的差异。

http://en.wikipedia.org/wiki/Diff

19 0

傅里叶变黄油猫软件工程师,应用数学专业

2014-05-22 20:22

如果你的目的是比较两个文件,看有什么不同,那需要的算法叫:
Levenshtein distance(编辑距离)
这是业内常用的文本文件比较算法,基本思路是二维动态规划,既可以在行与行之间逐个字符比较,也可以在整个文件范围所有行一起比较。通过剪枝,在文件差别不大的前提下可以让时间复杂度接近O(N)。

不过我重新想了一下,这好像不符合你的问题。你的问题应该是,类似检查一篇文章是不是有抄袭。

这个也不难,不过不能用Levenshtein distance,而是用类似搜索引擎的技术。

(1)先对一大堆别人的文章建立全文索引。由于我们只是为了检测大段的抄袭,所以精确度要求不高。将文章每两个标点之间的句子索引,而无需切割成一个个词。索引用各种key-value的数据结构即可,不要求保存的话用C++的std::map或者Java的Map之类的库,要求保存的话可以高端一点,用nosql,例如Google LevelDB。不用担心数据量太大,10亿字都毫无压力,每次搜索都是毫秒级。索引的key是每一个句子,value是该句子在那篇论文、哪个位置出现,如果出现多次可以记录多条。

(2)对怀疑目标(可能有抄袭行为的文章),也是每两个标点之间切割,然后每句在上面的索引上搜索一下,有的话就将这句后面都相同的文本标记为疑似抄袭,并给出其它论文中出现的位置。

(3)最后人工判断这些标记出来的位置是否抄袭。

这个东西超好用,想像老师搜来一大堆论文,建立索引后,学生收上来的论文用程序一扫,谁有抄都一目了然,简直丧心病狂啊!

1 0
支持者: Karlson

要是能把生物信息学使用的blast算法用到这个地方就非常棒了!

0 0

LD算法太慢了。。。直接用Map太粗糙了点,

有个叫simhash的东西,楼主可以去百度一下。

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区