在一个文件中找到不在另一个文件中的行的快速方法？

Question

我有两个大文件(文件名集).每个文件大约有30,000行.我试图找到一种快速查找file1中不存在于file2中的行的方法.

例如,如果这是file1:

line1
line2
line3

这是file2:

line1
line4
line5

然后我的结果/输出应该是:

line2
line3

这有效:

grep -v -f file2 file1

但是在我的大文件上使用它时非常非常慢.

我怀疑有一个很好的方法来使用diff(),但输出应该只是行,没有别的,我似乎无法找到一个开关.

任何人都可以帮我找到一个快速的方法,使用bash和基本的Linux二进制文件？

编辑:为了跟进我自己的问题,这是我到目前为止使用diff()找到的最好方法:

diff file2 file1 | grep '^>' | sed 's/^>\ //'

当然,必须有更好的方法吗？

Answer 1

该通讯命令(简称"常用")可能是有用的comm - compare two sorted files line by line

#find lines only in file1
comm -23 file1 file2 

#find lines only in file2
comm -13 file1 file2 

#find lines common to both files
comm -12 file1 file2 

该man文件实际上非常易读.

Answer 2

您可以通过控制GNU diff输出中旧/新/未更改行的格式来实现此目的:

diff --new-line-format="" --unchanged-line-format=""  file1 file2

应对输入文件进行排序,以使其正常工作.使用bash(和zsh),您可以使用流程替换进行就地排序<( ):

diff --new-line-format="" --unchanged-line-format="" <(sort file1) <(sort file2)

另外,在上述新的和不变的线被抑制,从而仅改变(即删除的行中的情况下)被输出.你也可以使用一些diff选项,其他解决方案不提供,如-i忽略大小写,或各种空白选项(-E,-b,-v对于不太严格的匹配等).

说明

选项--new-line-format,--old-line-format并--unchanged-line-format让您控制的方式diff格式之间的差异,类似 printf的格式说明.这些选项分别格式化新(添加),旧(删除)和未更改的行.将一个设置为空""可以防止输出那种线.

如果您熟悉统一差异格式,则可以使用以下部分重新创建它:

diff --old-line-format="-%L" --unchanged-line-format=" %L" \
     --new-line-format="+%L" file1 file2

该%L说明符是有问题的行,我们每个前缀为"+"," - "或"",像diff -u (请注意,它只能输出不同,它缺乏--- +++与@@线在每个分组改变的顶部).您也可以使用此做其他有用的东西像数每行有%dn.

该diff方法(以及其他建议comm和join)仅生成带有排序输入的预期输出,但您可以使用它<(sort ...)进行排序.这是一个简单的awk(nawk)脚本(受Konsolebox答案中链接的脚本的启发),它接受任意排序的输入文件,并按照它们在file1中出现的顺序输出缺失的行.

# output lines in file1 that are not in file2
BEGIN { FS="" }                         # preserve whitespace
(NR==FNR) { ll1[FNR]=$0; nl1=FNR; }     # file1, index by lineno
(NR!=FNR) { ss2[$0]++; }                # file2, index by string
END {
    for (ll=1; ll<=nl1; ll++) if (!(ll1[ll] in ss2)) print ll1[ll]
}

这将file1的全部内容逐行存储在行号索引数组中ll1[],并将file2的全部内容逐行存储在行内容索引关联数组中ss2[].读取两个文件后,迭代ll1并使用in运算符确定file1中的行是否存在于file2中.(diff如果有重复,这将对方法有不同的输出.)

如果文件足够大以至于存储它们都会导致内存问题,则可以通过仅存储file1并在读取file2时删除匹配来交换CPU以获取内存.

BEGIN { FS="" }
(NR==FNR) {  # file1, index by lineno and string
  ll1[FNR]=$0; ss1[$0]=FNR; nl1=FNR;
}
(NR!=FNR) {  # file2
  if ($0 in ss1) { delete ll1[ss1[$0]]; delete ss1[$0]; }
}
END {
  for (ll=1; ll<=nl1; ll++) if (ll in ll1) print ll1[ll]
}

上面将file1的全部内容存储在两个数组中,一个由行号ll1[]索引,一个由行内容索引ss1[].然后,当读取file2时,将从ll1[]和中删除每个匹配行ss1[].最后输出file1的剩余行,保留原始顺序.

在这种情况下,如上所述,您还可以使用GNU进行分割和征服split(过滤是GNU扩展),每次使用file1块重复运行并完全读取file2:

split -l 20000 --filter='gawk -f linesnotin.awk - file2' < file1

需要注意的使用和放置-意义stdin上的gawk命令行.这是由split每个调用20000行的块中的file1 提供的.

对于非GNU系统的用户,几乎肯定是GNU coreutils软件包可以获取,包括OSX的部分苹果的Xcode工具,它提供了GNU diff,awk虽然只有一个POSIX/BSD split而不是一个GNU版本.

Answer 3

像konsolebox建议,海报grep解决方案

grep -v -f file2 file1

如果你只是添加-F选项,将模式视为固定字符串而不是正则表达式,实际上效果很好(快).我在一对必须比较的~1000行文件列表中验证了这一点.随着-F花了0.031秒(实际),而无需花了2.278秒(实际),重定向grep的输出结果的时候wc -l.

这些测试还包括-x开关,它是解决方案的必要部分,以确保在file2包含与file1中的一行或多行匹配但不是全部的行的情况下完全准确.

因此,不需要对输入进行排序的解决方案是快速,灵活(区分大小写等),并且(我认为)适用于任何POSIX系统:

grep -F -x -v -f file2 file1

Answer 4

这对我来说似乎很快：

comm -1 -3 <(sort file1.txt) <(sort file2.txt) > output.txt

Answer 5

什么是排序和差异的速度？

sort file1 -u > file1.sorted
sort file2 -u > file2.sorted
diff file1.sorted file2.sorted

Answer 6

使用combinefrom moreutilspackage，一个支持not, and, or,xor操作的集合工具

combine file1 not file2

即给我文件1中但不在文件2中的行

或者给我文件 1 中的行减去文件 2 中的行

注意： combine在执行任何操作之前对两个文件中的唯一行进行排序和查找，但diff不会。因此，您可能会发现diff和 的输出之间存在差异combine。

所以实际上你是说

在 file1 和 file2 中找到不同的行，然后在 file1 中给我行减去 file2 中的行

根据我的经验，它比其他选项快得多

Answer 7

如果你是短期的一些最低限度的Linux发行版“神奇工具”，例如，有只有一个解决方案cat，sort以及uniq：

cat includes.txt excludes.txt excludes.txt | sort | uniq --unique

测试：

seq 1 1 7 | sort --random-sort > includes.txt
seq 3 1 9 | sort --random-sort > excludes.txt
cat includes.txt excludes.txt excludes.txt | sort | uniq --unique

# Output:
1
2    

与相比，这也相对较快grep。

Answer 8

$ join -v 1 -t '' file1 file2
line2
line3

在-t确保它的整体线条比较,如果你有一些行的空间.

Answer 9

您可以使用Python：

python -c '
lines_to_remove = set()
with open("file2", "r") as f:
    for line in f.readlines():
        lines_to_remove.add(line.strip())

with open("f1", "r") as f:
    for line in f.readlines():
        if line.strip() not in lines_to_remove:
            print(line.strip())
'