Python中如何对比多个文件并识别新插入的内容
有一个文本文件 0.txt ,内容如下
语文
数学
外语
政治
物理
生物
这个文件被复制 100 份,变成 1.txt, 2.txt... 100.txt ,每一份里面都会随机在头部,尾部或者中间插入一行或者多行内容(不改变已有内容的顺序),例如:
在数学和外语之间插入一条信息,在物理和生物之间也插入一条信息,变成:
语文
数学
化学
外语
政治
物理
计算机
生物
现在,给你 1.txt, 2.txt... 100.txt,如何用复杂度最小的办法,推测出 0.txt 的内容,并且确定每一个文本文件里面哪些内容是相对于 0.txt 新增的?
Python中如何对比多个文件并识别新插入的内容
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库进行文件差异对比是最标准的方法。
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 )
一点微小的思路
用字典存的话,是按照{‘语文’: 89, ‘数学’: 30}这种方式,全部遍历完成以后看次数为 100 的就是 0.txt 的内容了。然后再通过任何一个文件里面的内容来确定顺序。这种算法没有问题。
对,细节没有推敲(工作中累了水一下,哈哈)
因为不确定你插入的词是否会和原始词一样,所以开始没有用统计次数的思路去算,而是默认有重复的
1 去重
2 统计每个行出现的次数
3 出现次数等于文件总数的行是原始存在的
用 Set 就能搞定了。
把所有文件读到一个 Set 里,然后和 0.txt diff 一哈
怎么听起来就是一个求交集的事情?
不止一个解吧,0.txt 为空应该就能满足要求。
每一个文件都出现的就是需要的内容.
随便找一个文件, 遍历其他文件是否包某行内容, 其他好像也没有办法


