V2EX 首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
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
V2EX  ›  Python

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

  •  
  •   billion · 6 天前 · 986 次点击

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

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

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

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

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

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

    23 回复  |  直到 2017-09-15 15:59:08 +08:00
        1
    gstqc   6 天前 via iPhone
    diff?
    看下 Python 有没有这种库
        2
    billion   6 天前
    @gstqc Python 有这个库叫做 difflib。但是不太好用。
        3
    20015jjw   6 天前
    bucket sort?
        4
    billion   6 天前
    @gstqc 我想问的点是如何最高效地对比 100 个文件,如果使用 diff 的话,两两对比要进行 9900 次,太耗费时间和资源。
        5
    gamexg   6 天前
    @billion #4 x 行一个 hash ?
    不过有多少文件下,需要优化这个?
        6
    billion   6 天前
    补充说明:同一条内容可以插入多个文件的不同位置,但是同一条内容最多插入 99 个文件,所以在 100 个文件都出现的内容显然就是原始数据。所以问题是,如果在避免两两对比的情况下,分别找到原始数据和新插入的数据?

    为了增加难度,把 100 个文件改成 100 亿个文件,每个文件 100 亿行以上。
        7
    SuperMild   6 天前   ♥ 1
    除了 0.txt 之外,其它文件只插入不删除 0.txt 的项目? 行数(字节数)最少的那个就是 0.txt 了。
        8
    SuperMild   6 天前
    看错了。不过这种需求,通常扔进数据库里处理比较好
        9
    xml123   6 天前 via Android   ♥ 1
    如果只加一行的话,两个文件不就能对比出来原始文件吗
        10
    elvodn   6 天前   ♥ 1
    cat *.txt | sort | uniq -c | sort -nr
        11
    jmc891205   6 天前   ♥ 1
    没有深入思考过
    首先我知道我会求两个序列的最长公共子序列 时间复杂度印象中是 O(n^2)。这里可能记错 欢迎指正。
    然后求所有序列的公共子序列只需要遍历一遍所有序列就好了。这里是 O(n)
    总的时间复杂度是 O(n^3)
        12
    jmc891205   6 天前
    @jmc891205 哦第一个 n 和第二个 n 不太一样。写成 O(m*n^2)好了。
        13
    oisc   6 天前   ♥ 1
    keyword: edit distance 动规求解编辑距离就是 diff 算法的原型
        14
    ChristopherWu   6 天前   ♥ 1
    每个文件都遍历一遍,用 map 来存
    之后看 map 里,出现最多的前 x 个词是什么,就可以知道哪些是原始词;
    如果你早知道 x 是多少,其他就简单了。
    不知道的话,就出现频率大小,遍历看看是否每个文件都有(这个过程也可以每个文件词存 map )

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

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

    当然,如果数据规模超级大,那样这个问题就应该考虑分布式运算之类的了。
        16
    billion   6 天前
    @ChristopherWu
    用字典存的话,是按照{'语文': 89, '数学': 30}这种方式,全部遍历完成以后看次数为 100 的就是 0.txt 的内容了。然后再通过任何一个文件里面的内容来确定顺序。这种算法没有问题。
        17
    ChristopherWu   6 天前
    @billion 对,细节没有推敲(工作中累了水一下,哈哈)
        18
    ChristopherWu   6 天前
    @billion 因为不确定你插入的词是否会和原始词一样,所以开始没有用统计次数的思路去算,而是默认有重复的
        19
    cdwyd   6 天前 via Android
    1 去重
    2 统计每个行出现的次数
    3 出现次数等于文件总数的行是原始存在的
        20
    noe132   6 天前
    用 Set 就能搞定了。
    把所有文件读到一个 Set 里,然后和 0.txt diff 一哈
        21
    otakustay   6 天前
    怎么听起来就是一个求交集的事情?
        22
    oaix   5 天前
    不止一个解吧,0.txt 为空应该就能满足要求。
        23
    ThatIsFine   5 天前
    每一个文件都出现的就是需要的内容.

    随便找一个文件, 遍历其他文件是否包某行内容, 其他好像也没有办法
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   554 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.7.5 · 58ms · UTC 19:51 · PVG 03:51 · LAX 12:51 · JFK 15:51
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1