V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
v3exad
V2EX  ›  问与答

一个简单算法问题,关于字符匹配

  •  
  •   v3exad · 2017-07-05 16:02:14 +08:00 · 2007 次点击
    这是一个创建于 2683 天前的主题,其中的信息可能已经有所发展或是发生改变。

    假设我有两个文本文件

    ## A 文本 ##

    a1,b1,c1
    a2,b2,c2
    a3,b3,c3
    ...
    

    ## B 文本 ##

     b2,d2
     b1,d1
     b5,d5
     ...
    

    如果要写一个简单程序把两个文本内容合并成

     a1,b1,c1,d1
     a2,b2,c2,d2
     a3,b3,c3,d3
     ...
    

    本人算法不好,就只会用最简单的方法,就是取一行,然后遍历另一个文本去做匹配。。
    不知各位 v2er,有啥高效的方法,不吝赐教

    第 1 条附言  ·  2017-07-05 18:48:46 +08:00
    看来大家不是很明白我的意思
    我补充一下

    A 文本内容是
    abc:a12:xxxx2
    sdfsdf:b33:dfsd34
    danirg:a4444:329vk



    B 文本内容是
    b33:31s444
    a12:34k334k
    a4444:sfe4fergre


    合并成:
    abc:a12:xxxx2:34k334k
    sdfsdf:b33:dfsd34:31s444
    danirg:a4444:329vk::sfe4fergre


    就是 5 楼说的 join 操作而已,类似 sql 语句 1.b=2.b,b 是唯一的
    18 条回复    2017-07-06 10:47:16 +08:00
    neosfung
        1
    neosfung  
       2017-07-05 16:21:14 +08:00
    恕我直言
    看不懂最后合并的文本和前面两个文本有啥关系哦
    pipapa
        2
    pipapa  
       2017-07-05 16:33:13 +08:00
    对第二个文档预处理下顺序?
    v3exad
        3
    v3exad  
    OP
       2017-07-05 16:34:02 +08:00
    @neosfung 额,就是把内容合并了,a1,b1,c1,d1 都是对应的。。不能 a1,b2,c3,d4 这样子
    v3exad
        4
    v3exad  
    OP
       2017-07-05 16:35:15 +08:00
    @pipapa 但是 a 文本的内容并不是排好序的。a1,a2 是为了方便展示一下内容而已
    geelaw
        5
    geelaw  
       2017-07-05 16:39:26 +08:00
    如果 b 这列是 UNIQUE,那么这个操作其实是 JOIN ON 1.b = 2.b。

    如果我们又假设有 CSV 表头( A 的名是 a,b,c,B 的列名是 b,d ),用 PowerShell 可以这样:

    $dict=@{};
    get-content a.txt | convertfrom-csv | write | foreach {
    $dict[$_.b]=$_;
    };
    get-content b.txt | convertfrom-csv | write | foreach {
    if ($dict[$_.b] -ne $null)
    {
    add-member -inputobject $dict[$_.b] -membertype noteproperty -name 'd' -value $_.d;
    }
    };
    $dict.Values | write;
    Chingim
        6
    Chingim  
       2017-07-05 17:22:48 +08:00
    abcd 就是单纯的字母? 还是任意长的字符串?
    1,2,3,4 最大有多大?
    FlowerChen
        7
    FlowerChen  
       2017-07-05 17:32:24 +08:00
    把每个字符拆开,放在一个对象,或者数组里,假设这些数据都放在数组里命名为 Arr,比如 a1 拆分后 --> {'value':'a1','letter':'a','num':1},然后两个 for 循环,for(i = 0; i < Arr.length; i ++)先按 Arr[i].num 排序,再按 Arr[i].letter 排序,
    binux
        8
    binux  
       2017-07-05 17:39:53 +08:00
    对两个文件排序,merge
    vingz
        9
    vingz  
       2017-07-05 17:48:10 +08:00
    假设,a,b,c,d 是字符串前缀,1,2,3,4 是字符串后缀,
    合并规则:
    1. 同行根据前缀排序,(直接字符串排序)
    2. 同列根据后缀排序,(直接字符串排序)
    看内存大小和文件大小,《编程珠玑》第一章节就有类似对文件内容排序的算法。

    算法 1:内存如果受限的话,先分别读入文本 1 和文本 2 中全部的 a&b,分别对 a 和 b 排序,然后层层输出到一个中间文件 3,(a1&b1 是第一层,a2&b2 是第二层);同理处理 c&d 后输出到中间文件 4 ;最后合并文件 3 和 4 的每一层,输出为最终文件。(异常 case,比如缺少 b1,但有 b2,等情况需要考虑)
    算法 2:如算法 1 处理 a/b/c/d 的 1&2 到中间文件 3,处理 a/b/c/d 的 3&4 到中间文件 4,最后拼接文件 3 和 4 输出最终文件。
    因为楼主对问题背景和问题定义描述不清晰,我就参考编程珠玑的解法给了思路。
    miaoever
        10
    miaoever  
       2017-07-05 18:05:18 +08:00 via iPhone
    就像 #5 说的,这个就是个 Join 操作,最简单快速的方法就是把 A 文件根据 join key 建 hash table, 然后对 B 文件每行根据 key 来查询并 join.
    v3exad
        11
    v3exad  
    OP
       2017-07-05 18:37:47 +08:00
    @Chingim 就是单纯文本内容而已,就是类似数据库的一个字段内容。。。和一个 csv 差不多
    v3exad
        12
    v3exad  
    OP
       2017-07-05 18:49:56 +08:00
    @binux 恩,这个也可以
    v3exad
        13
    v3exad  
    OP
       2017-07-05 18:51:03 +08:00
    @miaoever 谢谢,我研究一下看看
    shoumu
        14
    shoumu  
       2017-07-05 19:29:02 +08:00
    文本大小多大,key 应该是 b 吧,把小的那个文本放到字典里面,遍历大的那个间文件就可以了
    v3exad
        15
    v3exad  
    OP
       2017-07-05 19:32:03 +08:00
    @shoumu 这种文本几十行还行,我试过两个都 1w+行的时候,挺慢的
    shoumu
        16
    shoumu  
       2017-07-05 19:37:42 +08:00
    @v3exad
    1w+还好吧,除非你对时效性要求特别高,前几天搞过一个类似的工作,数据量大概是亿*千万级别的,跑一次下来几十分钟。。。。
    ryd994
        17
    ryd994  
       2017-07-06 08:11:24 +08:00 via Android
    你这样还不如进数据库
    v3exad
        18
    v3exad  
    OP
       2017-07-06 10:47:16 +08:00
    @ryd994 这也可以啊,只不过是想了解一下有没有高效的算法而已
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   975 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 22:26 · PVG 06:26 · LAX 14:26 · JFK 17:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.