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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2630 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

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

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

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

txt

插入

外语

文件

23 条回复 • 2017-09-15 15:59:08 +08:00

0ZXYDDu796nVCFxq

2017-09-14 15:29:53 +08:00 via iPhone

diff?
看下 Python 有没有这种库

billion

2017-09-14 15:31:37 +08:00

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

20015jjw

2017-09-14 15:36:42 +08:00

bucket sort?

billion

2017-09-14 15:38:01 +08:00

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

gamexg

2017-09-14 15:43:24 +08:00

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

billion

2017-09-14 15:47:06 +08:00

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

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

SuperMild

2017-09-14 15:48:37 +08:00

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

SuperMild

2017-09-14 15:51:13 +08:00

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

xml123

2017-09-14 15:51:36 +08:00 via Android

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

elvodn

2017-09-14 15:54:49 +08:00

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

jmc891205

2017-09-14 15:56:02 +08:00

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

jmc891205

2017-09-14 15:57:06 +08:00

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

oisc

2017-09-14 15:58:18 +08:00

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

ChristopherWu

2017-09-14 15:58:54 +08:00

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

一点微小的思路

coderluan

2017-09-14 16:00:42 +08:00

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

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

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

billion

2017-09-14 16:06:45 +08:00

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

ChristopherWu

2017-09-14 16:11:04 +08:00

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

ChristopherWu

2017-09-14 16:12:32 +08:00

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