如何对比多个文件，从而发现新插入的内容

[billion]

有一个文本文件 0.txt ，内容如下

语文
数学
外语
政治
物理
生物

这个文件被复制 100 份,变成 1.txt, 2.txt... 100.txt ，每一份里面都会随机在头部，尾部或者中间插入一行或者多行内容（不改变已有内容的顺序），例如：

在数学和外语之间插入一条信息，在物理和生物之间也插入一条信息，变成：

语文
数学
化学
外语
政治
物理
计算机
生物

现在，给你 1.txt, 2.txt... 100.txt,如何用复杂度最小的办法，推测出 0.txt 的内容，并且确定每一个文本文件里面哪些内容是相对于 0.txt 新增的？

[gstqc]

diff?
看下 Python 有没有这种库

[billion]

@gstqc Python 有这个库叫做 difflib。但是不太好用。

[20015jjw]

bucket sort?

[billion]

@gstqc 我想问的点是如何最高效地对比 100 个文件，如果使用 diff 的话，两两对比要进行 9900 次，太耗费时间和资源。

[gamexg]

@billion #4 x 行一个 hash ？
不过有多少文件下，需要优化这个？

[billion]

补充说明：同一条内容可以插入多个文件的不同位置，但是同一条内容最多插入 99 个文件，所以在 100 个文件都出现的内容显然就是原始数据。所以问题是，如果在避免两两对比的情况下，分别找到原始数据和新插入的数据？

为了增加难度，把 100 个文件改成 100 亿个文件，每个文件 100 亿行以上。

[SuperMild]

除了 0.txt 之外，其它文件只插入不删除 0.txt 的项目？ 行数（字节数）最少的那个就是 0.txt 了。

[SuperMild]

看错了。不过这种需求，通常扔进数据库里处理比较好

[xml123]

如果只加一行的话，两个文件不就能对比出来原始文件吗

[elvodn]

cat *.txt | sort | uniq -c | sort -nr

[jmc891205]

没有深入思考过
首先我知道我会求两个序列的最长公共子序列 时间复杂度印象中是 O(n^2)。这里可能记错 欢迎指正。
然后求所有序列的公共子序列只需要遍历一遍所有序列就好了。这里是 O(n)
总的时间复杂度是 O(n^3)

[jmc891205]

@jmc891205 哦第一个 n 和第二个 n 不太一样。写成 O(m*n^2)好了。

[oisc]

keyword: edit distance 动规求解编辑距离就是 diff 算法的原型

[ChristopherWu]

每个文件都遍历一遍，用 map 来存
之后看 map 里，出现最多的前 x 个词是什么，就可以知道哪些是原始词；
如果你早知道 x 是多少，其他就简单了。
不知道的话，就出现频率大小，遍历看看是否每个文件都有（这个过程也可以每个文件词存 map ）

一点微小的思路

[coderluan]

如果就是例子里那些数据，可以编程做啊，把每个文件读到多个数组中，然后这题就变成了类似于从多个字符串中找一一个共有字串，不考虑时间复杂度的话，枚举就可以，直接拿最短字符串的一个字串当答案，不对再换下一个。

当然，如果数据规模大些，就需要考虑时间复杂度了，比如先找出公共最长串，然后把每个位当成 01，转化成二进制问题。

当然，如果数据规模超级大，那样这个问题就应该考虑分布式运算之类的了。

[billion]

@ChristopherWu
用字典存的话，是按照{'语文': 89, '数学': 30}这种方式，全部遍历完成以后看次数为 100 的就是 0.txt 的内容了。然后再通过任何一个文件里面的内容来确定顺序。这种算法没有问题。

[ChristopherWu]

@billion 对，细节没有推敲（工作中累了水一下，哈哈）

[ChristopherWu]

@billion 因为不确定你插入的词是否会和原始词一样，所以开始没有用统计次数的思路去算，而是默认有重复的

[cdwyd]

1 去重
2 统计每个行出现的次数
3 出现次数等于文件总数的行是原始存在的

[noe132]

用 Set 就能搞定了。
把所有文件读到一个 Set 里，然后和 0.txt diff 一哈