內容相同但位置不同的文字檔比對問題

inmolee

UID: 22938
帖子: 2
积分: 4
在线时间: 10 分钟

1^# inmolee 发表于 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的方式有比較快的方法嗎？
請高手請幫幫忙，謝謝!

Lonki

UID: 21498
帖子: 1
积分: 2
在线时间: 10 分钟

2^# Lonki 发表于 2007-12-05 11:07

# 对于小文件, HASH是很好的选择.

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