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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

假设我有两个文本文件

## 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 是唯一的

文本

算法

赐教

V2er

18 条回复 • 2017-07-06 10:47:16 +08:00

neosfung

2017-07-05 16:21:14 +08:00

恕我直言
看不懂最后合并的文本和前面两个文本有啥关系哦

pipapa

2017-07-05 16:33:13 +08:00

对第二个文档预处理下顺序？

v3exad

2017-07-05 16:34:02 +08:00

@neosfung 额，就是把内容合并了，a1,b1,c1,d1 都是对应的。。不能 a1,b2,c3,d4 这样子

v3exad

2017-07-05 16:35:15 +08:00

@pipapa 但是 a 文本的内容并不是排好序的。a1,a2 是为了方便展示一下内容而已

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

2017-07-05 17:22:48 +08:00

abcd 就是单纯的字母? 还是任意长的字符串?
1,2,3,4 最大有多大?

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

2017-07-05 17:39:53 +08:00

对两个文件排序，merge

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

2017-07-05 18:05:18 +08:00 via iPhone

就像 #5 说的，这个就是个 Join 操作，最简单快速的方法就是把 A 文件根据 join key 建 hash table, 然后对 B 文件每行根据 key 来查询并 join.

v3exad

2017-07-05 18:37:47 +08:00

@Chingim 就是单纯文本内容而已，就是类似数据库的一个字段内容。。。和一个 csv 差不多

v3exad

2017-07-05 18:49:56 +08:00

@binux 恩，这个也可以

v3exad

2017-07-05 18:51:03 +08:00

@miaoever 谢谢，我研究一下看看

shoumu

2017-07-05 19:29:02 +08:00

文本大小多大，key 应该是 b 吧，把小的那个文本放到字典里面，遍历大的那个间文件就可以了

v3exad

2017-07-05 19:32:03 +08:00

@shoumu 这种文本几十行还行，我试过两个都 1w+行的时候，挺慢的

shoumu

2017-07-05 19:37:42 +08:00

@v3exad
1w+还好吧，除非你对时效性要求特别高，前几天搞过一个类似的工作，数据量大概是亿*千万级别的，跑一次下来几十分钟。。。。

ryd994

2017-07-06 08:11:24 +08:00 via Android

你这样还不如进数据库

v3exad

2017-07-06 10:47:16 +08:00

@ryd994 这也可以啊，只不过是想了解一下有没有高效的算法而已