免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1768 | 回复: 1

內容相同但位置不同的文字檔比對問題 [复制链接]

论坛徽章:
0
发表于 2007-12-05 10:03 |显示全部楼层
請高手請幫幫忙
假設有兩個文字檔,文字檔A內容跟文字檔B差不多,但是放置的位置不同,請問該如何去比較?(PS這兩個文字檔大概有二百萬行那麼多喔)
例如文字檔A內容為:
#T  aaaaaaaaaaa
#T  bbbbbbbbbb
#T  ccccccccccc
#T  dddddddddd
#T  eeeeeeeeeee

文字檔B內容與A差不多但行數不同:
#T  ccccccccccc
#T  aaaaaaaaaaa
#T  dddddddddd
#T  eeeeeeeeeee
#T  wwwwwww

比較檔案時,只要A檔出現過的,B檔有就算ok,若A有B沒有就顯示問題行,
實際上這兩個文字檔有二百多萬行,用perl的方式有比較快的方法嗎?
請高手請幫幫忙,謝謝!

论坛徽章:
0
发表于 2007-12-05 11:07 |显示全部楼层
# 对于小文件, HASH是很好的选择.

# 对于大文件, 暂时想到2个办法:
# 1. 逐行比较, 外循环遍历相对较大的文件, 内循环遍历相对较小的文件.
#    时间复杂度是O(na*nb). 当然, 这个就完全没效率可言了.
# 2. 先将2文件sort, 再比较, 时间复杂度就急剧下降到O(na+nb).
#    sort的耗时: 200W行, 平均每行76字节, 大概50秒.
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP