bash - `uniq` 没有对巨大的文本文件进行排序？

Question

我有一个非常大的文本文件(即今天的 40 GB)，我想过滤出唯一的行而不对文件进行排序。

文件有 unix 行结尾，所有内容匹配 [[:print:]]。我尝试了以下 awk 脚本来仅显示唯一的行:

awk 'a[$0] {next} 1' stupid.txt > less_stupid.txt

我的想法是通过引用其元素来填充一个数组，使用文件的内容作为键，然后跳过数组中已有的行。但这失败有两个原因——首先，因为它莫名其妙地不起作用(即使在小测试文件上)，其次，因为我知道我的系统将在整组唯一行加载到内存之前耗尽内存通过 awk。

经过搜索，我找到了this answer推荐:

awk '!x[$0]++'

虽然这适用于小文件，但它也会在读取整个文件之前耗尽内存。

什么是更好(即有效)的解决方案？我对几乎所有事情都持开放态度，尽管我更偏向于使用我知道的语言(bash 和 awk，因此是标签)的解决方案。在尝试将问题可视化时，我想出的最好办法是存储一组行校验和或 MD5，而不是行本身，但这只会节省一点空间并冒着校验和冲突的风险。

任何提示都将非常受欢迎。告诉我这是不可能的也很受欢迎，这样我就不再试图弄清楚了。 :-P

Answer 1

awk '!x[$0]++' 技巧是最优雅的解决方案之一，无需排序即可删除重复文件或流。但是，它在内存方面效率低下并且不适合大文件，因为它将所有唯一行保存到内存中。

但是，更有效的实现方式是在数组中保存行的恒定长度 散列 表示而不是整行。您可以使用 Perl 在一行中实现这一点，它与 awk 脚本非常相似。

perl -ne 'use Digest::MD5 qw(md5_base64); print unless $seen{md5_base64($_)}++' huge.txt

这里我使用了 md5_base64 而不是 md5_hex 因为 base64 编码需要 22 个字节，而十六进制表示为 32。

但是，由于 hashes 的 Perl 实现仍然需要每个键大约 120 字节，您可能会很快用完您的大文件的内存。

这种情况下的解决方案是分块处理文件，手动拆分或使用 GNU Parallel使用 --pipe、--keep-order 和 --block 选项(正如您提到的那样，利用重复行相距不远的事实)。以下是如何使用 parallel 实现它:

cat huge.txt | pv | 
parallel --pipe --keep-order --block 100M -j4 -q \
perl -ne 'use Digest::MD5 qw(md5_base64); print unless $seen{md5_base64($_)}++' > uniq.txt

--block 100M 选项告诉 parallel 以 100MB 的 block 来处理输入。 -j4 表示并行启动 4 个进程。这里的一个重要论点是 --keep-order 因为您希望唯一的行输出保持相同的顺序。我在管道中包含了 pv，以便在执行长时间运行的进程时获得一些不错的统计数据。

在我对随机数据 1GB 文件执行的基准测试中，我使用上述设置达到了 130MB/秒的吞吐量，这意味着您可以在 4 分钟内删除 40GB 文件的重复数据(如果您有足够快的硬盘能够以这种速度写作)。

其他选项包括:

• 使用高效的 trie存储 key 和检查重复项的结构。例如，一个非常有效的实现是 marisa-trie用 C++ 编码 wrappers in Python .
• 用 external merge sort 对您的大文件进行排序或分发/bucket排序
• 将您的文件存储在数据库中，并在包含您的行或最有效的 md5_sums 行的索引列上使用 SELECT DISTINCT。
• 或使用bloom filters

这是使用 Bloom::Faster 的示例Perl 模块:

perl -e 'use Bloom::Faster; my $f = new Bloom::Faster({n => 100000000, e => 0.00001}); while(<>) { print unless $f->add($_); }' huge.txt > uniq.txt

您可以从cran 安装Bloom::Faster(sudo cran 然后安装“Bloom::Faster”)

解释:

• 您必须指定概率错误率 e 和可用桶的数量 n。每个桶所需的内存约为 2.5 字节。如果您的文件有 1 亿行，那么您将需要 1 亿个桶和大约 260MB 的内存。
• $f->add($_) 函数将一行的散列添加到过滤器中，如果键(即此处的行)是，则返回 true一个副本。
• 您可以估计文件中唯一行的数量，使用 dd if=huge.txt bs=400M count=1 | 解析文件的一小部分 | awk '!a[$0]++' | wc -l (400MB) 并将该数字乘以 100 (40GB)。然后将 n 选项设置得更高一些以确保安全。

在我的基准测试中，这种方法达到了 6MB/s 的处理速率。您可以将此方法与上面的 GNU parallel 建议结合使用，以利用多个内核并实现更高的吞吐量。