Python中如何对比多个文件并识别新插入的内容

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

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

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

数学外语之间插入一条信息,在物理生物之间也插入一条信息,变成:

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

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


Python中如何对比多个文件并识别新插入的内容

24 回复

diff?
看下 Python 有没有这种库


要对比多个文件并识别新插入的内容,最直接的方法是使用Python的difflib库。下面是一个完整的示例,它会比较两个文本文件并输出新增的行:

import difflib

def compare_files(file1_path, file2_path):
    with open(file1_path, 'r', encoding='utf-8') as f1, \
         open(file2_path, 'r', encoding='utf-8') as f2:
        lines1 = f1.readlines()
        lines2 = f2.readlines()
    
    # 使用difflib的Differ进行行级比较
    differ = difflib.Differ()
    diff = list(differ.compare(lines1, lines2))
    
    # 提取新增的行(以'+ '开头的行)
    new_lines = [line[2:] for line in diff if line.startswith('+ ')]
    
    return new_lines

# 使用示例
if __name__ == "__main__":
    file1 = "old_version.txt"
    file2 = "new_version.txt"
    
    inserted_content = compare_files(file1, file2)
    
    print("新插入的内容:")
    for i, line in enumerate(inserted_content, 1):
        print(f"{i}: {line.strip()}")

如果你需要比较多个文件,可以扩展这个函数:

def compare_multiple_files(file_paths):
    """比较多个文件,找出每个文件相对于前一个文件的新增内容"""
    results = {}
    
    for i in range(1, len(file_paths)):
        new_content = compare_files(file_paths[i-1], file_paths[i])
        results[f"{file_paths[i-1]} -> {file_paths[i]}"] = new_content
    
    return results

# 使用示例
files = ["v1.txt", "v2.txt", "v3.txt", "v4.txt"]
all_changes = compare_multiple_files(files)

for comparison, changes in all_changes.items():
    print(f"\n{comparison} 中的新增内容:")
    for line in changes:
        print(f"  - {line.strip()}")

对于更复杂的场景(比如需要忽略空格、区分大小写等),difflib还提供了其他比较器,比如HtmlDiff可以生成HTML格式的差异报告。

总结建议:使用difflib库进行文件差异对比是最标准的方法。

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

bucket sort?

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

#4 x 行一个 hash ?
不过有多少文件下,需要优化这个?

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

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

除了 0.txt 之外,其它文件只插入不删除 0.txt 的项目? 行数(字节数)最少的那个就是 0.txt 了。

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

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

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

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

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

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

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

一点微小的思路

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

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

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


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

对,细节没有推敲(工作中累了水一下,哈哈)

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

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

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

怎么听起来就是一个求交集的事情?

不止一个解吧,0.txt 为空应该就能满足要求。

每一个文件都出现的就是需要的内容.

随便找一个文件, 遍历其他文件是否包某行内容, 其他好像也没有办法

回到顶部