使用python 比较2个100G 左右文件， 要求得出2个文件有多少行是相同的？

wenhq

对，LS说的正确！！！

ts32767

能用数据库吗？如果可以用数据库，那么我先把建一个数据库，把两个文件放在两张数据表里面，两张数据表结构相同，每一条记录有：index，文件名，行号，行内容。然后用脚本把文件导入到数据库，导入完成之后，根据行内容的MD5建立索引。索引完成之后排序，后面再直接用select根据MD5索引就可以找到所有重复的行。这应该是最投机取巧的办法。

代价就是需要一个400G的硬盘来做。

如果不用数据库，那么只能用DFA建一个多模式匹配的树加上AC算法来做了。假设文件是A和文件B，将文件A看成模式集合（即源串集合），文件B看做待匹配模式。如果内存是1G，依次读入文件A，每读入一行就更新一次DFA树，直到DFA树的存储空间到达800MB，此时记录下已经读入的行数在A中的位置，开始依次从B文件中读入一行，每读入一行就用AC算法在DFA树中扫描一次，有命中就记录（可以记录与A中哪一串命中），这种算法的好处就在于支持多次命中 （即A中若有若干行一模一样，那么命中结果会全部包含这些行）。如此比较一直到B文件遍历结束。然后释放这个DFA树，DFA树存储空间释放，然后从A中上次建立DFA树结束的地方继续读入，直到满了800M之后，再从B中第一行开始读入。开始将B中的每一行跟A中第二棵树进行比较。接着做第三棵树。。。直到A文件结束。

这个算法的好处在于，你能同时在多个机器上独立的进行比较：

比如： 机器1： A文件第1行到4096行建立一棵树，跟整个B文件比较
          机器2： A文件第4096行到8192行建立一棵树，跟整个B文件比较
          机器3： A文件第8192行到....行建立一棵树，跟整个B文件比较

最后汇总结果。 由于对A文件进行了预读，B文件也可以进行分段预读，整个算法的开销应该集中在DFA树的建立上，DFA的树的建立算法很简单，有很多现成的模块可用，这个过程类似于RE 模块的compile方法，只不过Re模块做的是NFA，在compile的时候将NFA专程DFA了。

Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。是目前多模式匹配的核心算法。

inpool

逐行读取要比较的文件，根据该行的前2-3个字符将该行存入不同的文件
为避免出现文件名中不允许出现的字符，可以进行md5摘要。两种方案
前几个字符分布比较集中的

1. for line in open('a.txt'):
   
2.     fname = 'a' + md5(line).hexdigest()[:3] + '.txt'
   
3.     open(fname, 'a').write(line)

复制代码

分布比较平均的

1. for line in open('a.txt'):
   
2.     fname = 'a' + md5(line[:3]).hexdigest()[:3] + '.txt'
   
3.     open(fname, 'a').write(line)

复制代码

写入的文件比较灵活，可以结合pickle等模块，然后再分别比较对应的文件就行了

idhly

比较同意楼上的，先对每个行进行指纹计算（计算方法很多），把数据量缩减下来，然后进行第一轮按指纹进行范围筛选，让第一轮筛选下来的结果进入第二轮筛选（这个要看数据文件的结构和数据分离度），最优的情况是第一轮完了就可以找出匹配的各行。

最好能有个样本文件，关于数据结构的最优化分析这个计算机还是没有人脑好使。。。

jakieyoung

这个问题的实质是数据量太大，大大超过内存时，怎么处理数据的问题。因为不能把数据全部读入内存进行操作，所以需要采用其他的手段来解决。
问题解决方法一般是，将原始数据先根据某种规则拆分到很多小文件中去，文件小到可以直接读入内存操作。然后对拆分后的所有文件再操作一遍即可。

针对这个问题，楼主所说的hash的方法是可行的。需要找到一种碰撞率非常低的hash算法，比如murmur，或者干脆用md5.
对A文件的每一行，计算hash，将hash值小于10万（举例，这个值根据内存大小进行调节）的放在文件A00001中，大于10万，小于20万写入A00002中，
依次类推。 B文件也一样做操作，拆分后的文件命名为B00001，B00002.。。。。。

然后，对A00001，B00001进行对比，因为这两个文件都可以读入内存比较，所以很方便知道相同的行有多少个。对A00002，B00002继续操作，……
最后把相同行的数目相加就得到总的相同行数了。