不排序巨大文本文件的`uniq`？

Question

我有一个非常大的文本文件（今天已经达到了40GB），我想过滤其中唯一的行，而不需要对文件进行排序。

该文件具有Unix行结束符，并且所有内容都匹配[[:print:]]。 我尝试了以下awk脚本以仅显示唯一行：

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

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

在搜索后，我发现这个答案建议：

awk '!x[$0]++'

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

有更好的（即可行的）解决方案吗？我对几乎任何东西都持开放态度，尽管我更倾向于使用我已知的语言（bash＆amp; awk，因此标签）。为了解决问题，我试图想象出的最好方法是存储行校验和或MD5的数组，而不是存储行本身，但这只节省了一点空间，并可能发生校验和冲突。

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

- Graham

---

为什么你想要避免排序？是因为你需要比排序更快的处理方式吗？排序后的文件占用太多空间了吗？或者有其他考虑因素使得排序不可行？ - user2357112

如果您无法在内存中存储完整的独特行集（并且每行都足够短，以至于即使每行的哈希值（sha256或其他）的合理总和也无法存储在内存中），那么我不确定这是可能的。 - Etan Reisner

你的原始脚本失败了，因为你从未修改 a[$0]，与你发现的答案不同。 - Jonathan Leffler

@EtanReisner，这是一个很好的问题 - 我可以进行多次扫描，一次用于识别重复数据，另一次用于修剪它。谢谢你的提问，我会进行调查！ - Graham

问题似乎更多地涉及如何处理大文件，因为当您使用这样的大文件时，内存是瓶颈。我认为“如何排序/去重”并不是真正的关注点。也许您应该查看http://www.slideshare.net/directi/mapreducedirecti?qid=9d03d57b-beda-4248-b914-745a723334be&v=qf1&b=&from_search=1。处理巨大数据是MapReduce等技术存在的原因。至少，这将为您提供一些探索传统`sort/uniq`内存陷阱以外的更多选项。 - slayedbylucifer

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个字节。

然而，由于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的块方式处理输入。-j4表示并行启动4个进程。这里一个重要的参数是--keep-order，因为你希望唯一的输出行保持相同的顺序。我在管道中加入了pv以获取一些漂亮的统计信息，当长时间运行的进程执行时。

在我使用随机数据1GB文件进行的基准测试中，我以以上设置达到了130MB/秒的吞吐量，这意味着您可以在4分钟内去重您的40GB文件（如果您拥有足够快速的硬盘能够以此速率写入）。

其他选项包括：

使用高效 Trie 结构来存储键并检查重复。例如，一个非常高效的实现是用 C++ 编写的 marisa-trie，并带有 Python 封装。

使用 外部排序 或分布/桶 排序对大型文件进行排序。

将文件存储在数据库中，并在包含行或最有效的 md5_sums 的索引列上使用 SELECT DISTINCT。

或者使用 Bloom 过滤器。

以下是使用 Perl 的 Bloom::Faster 模块的示例：

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

您可以从CPAN安装Bloom::Faster（sudo cpan install "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建议结合起来使用多个核心，以实现更高的吞吐量。

- henfiber

---

太棒了。我刚刚在不到10分钟的时间内整理了50多个超过25M行的文件！ - user2117258

@user2117258。很高兴它有所帮助。你使用了建议中的哪种方法？请注意，“布隆过滤器”方法可能会错误地删除一小部分（等于误差率e）的非重复行。 “parallel + perl”方法仅会删除重复行，但仅限于同一“块”中的行（由parallel中的--block 100M选项定义）。如果重复行足够接近，则此方法将奏效。您可以多次重新运行该过程，理想情况下使用不同的--block大小，以检测新块中之前未检测到的重复行。 - henfiber

Answer 2

我没有你的数据（或类似的内容）在手，所以无法进行测试，但是我为你提供一个概念证明：

$ t='one\ntwo\nthree\none\nfour\nfive\n'
$ printf "$t" | nl -w14 -nrz -s, | sort -t, -k2 -u | sort -n | cut -d, -f2-
one
two
three
four
five

我们的原始数据中包含一行重复数据。 pipes 的作用如下：

• nl 命令添加行号，这是一个标准、低影响力的 unix 工具。
• sort 命令第一次排序在第二个字段上-即nl之前的行的开头。根据您的数据需要进行调整。
• sort 命令第二次将事物放回到nl命令所定义的顺序中。
• cut 命令仅剥离行号。有多种方法可以做到这一点，但有些方法依赖于您的操作系统。这个方法是可移植的，并适用于我的例子。

现在... 对于非常大的文件，sort 命令将需要一些额外选项。 特别是 --buffer-size 和 --temporary-directory。请参阅 man sort 了解详情。

我不能保证这会很快，我怀疑您将使用大量的磁盘 IO，但我认为它至少可以工作。

- ghoti

---

我不知道nl有多少的可移植性; 你可以很容易地使用awk来编号行。就我个人而言，我会使用固定长度填充零的数字格式 (nl -w12 -nrz)；这将让你更精确地确定数据开始的位置，并且还能让你使用cut命令来去掉数字。但是肯定要点赞加一。 - rici

@rici，非常好的观点，谢谢。根据我的经验，nl 工具在 SunOS、HP/UX、Linux 和 *BSD 等系统上都有，但在 MINIX 2.0 中缺失。关于数字格式的建议很好 - 我相信这也会加快 sort 的速度。 - ghoti

只要sort保证保留重复行的最低行号，这看起来是不错的。我不确定它是否有保障。你肯定会从每组重复行中只得到一行，但我不确定它是否保证是每组重复行中的最低行号。 - Jonathan Leffler

可能需要在第一个字段上进行额外的子排序以处理JonathanLeffler指出的问题。 sort -t，-k2 -k1,1 -u 或类似的操作。（尽管这可能是默认操作。） - Etan Reisner

Answer 3

假设您首先可以对文件进行排序（即可以使sort file正常工作），那么我认为下面这种方法可能有效（取决于在内存使用等方面，大型awk脚本文件是否比大型awk数组更好）。

sort file | uniq -dc | awk '{gsub("\"", "\\\"", $0); print "$0==\""substr($0, index($0, $1) + 2)"\"{x["NR"]++; if (x["NR"]>1){next}}"} END{print 7}' > dedupe.awk
awk -f dedupe.awk file

以下是一个测试输入文件的例子：

line 1
line 2
line 3
line 2
line 2
line 3
line 4
line 5
line 6

创建一个awk脚本：

$0=="line 2"{x[1]++; if (x[1]>1){next}}
$0=="line 3"{x[2]++; if (x[2]>1){next}}
7

运行awk -f dedupe.awk file，输出如下：

line 1
line 2
line 3
line 4
line 5
line 6

如果awk脚本的大小是一个问题（可能不太可能），你可以使用另一个标记值来削减它，比如：

sort file | uniq -dc | awk 'BEGIN{print "{f=1}"} {gsub("\"", "\\\"", $0); print "$0==\""substr($0, index($0, $1) + 2)"\"{x["NR"]++;f=(x["NR"]<=1)}"} END{print "f"}'

该操作会使每行减少七个字符（如果从原始文本中删除空格，则减少六个字符），并生成以下结果：

{f=1}
$0=="line 2"{x[1]++;f=(x[1]<=1)}
$0=="line 3"{x[2]++;f=(x[2]<=1)}
f

这种解决方案可能会运行得更慢，因为它不会在找到匹配项时立即停止脚本的执行。

如果awk脚本的运行时间太长，甚至可以通过基于匹配计数对重复行进行排序来提高时间效率（但这是否有用将取决于数据的特性）。

- Etan Reisner

---

哇，你和ghoti都提出了听起来合理的解决方案，而其他人告诉我这是不可能的。谢谢，我会测试并看看效果如何。 - Graham

@ghoti 是的，这通常也不是我的首选解决方案（尽管它确实有其用武之地），但这种情况非常适合使用它。 - Etan Reisner

@EtanReisner：这是一个非常漂亮的解决方案，但生成的脚本可能接近文件大小，对吧？你需要大量内存来处理40GB的awk脚本。此外，通过所有行进行线性搜索使得该算法为O(n^2)，对吧？虽然我们不知道行有多长，但我怀疑n相当大。但我喜欢元编程，所以点个赞。 - rici

@rici 这就是我问是否已知的重复列表比已知的独特列表要小的部分原因（我认为它会有很大的差距，所以这应该比原始输入小得多）。是的，这将表现得相当差（因此我评论了一下尝试通过按频率排序来帮助解决这个问题）。更好的解决方案是将列表按前缀排序并进行更高级的基于树的匹配（即字典树和布隆过滤器的思想）。此外，我是根据awk可能在数组内部“优化”脚本的理论来操作的。 - Etan Reisner

@EtanReisner：数组是一个哈希表。有可能一些awk会将所有条件都是简单字符串匹配的程序优化为内部哈希表，以进行初始操作，但这种优化似乎需要付出很多工作，而收益却很少。因此，我的猜测是数组在时间和空间上都更有效率。但肯定值得进行基准测试。 - rici

Answer 4

我会这样做：

我会这样做：

#! /bin/sh
usage ()
{
    echo "Usage:  ${0##*/} <file> [<lines>]" >&2
    exit 1
}


if [ $# -lt 1 -o $# -gt 2 -o ! -f "$1" ]; then usage; fi
if [ "$2" ]; then
    expr "$2" : '[1-9][0-9]*$' >/dev/null || usage
fi

LC_ALL=C
export LC_ALL

split -l ${2:-10000} -d -a 6 "$1"

for x in x*; do
    awk '!x[$0]++' "$x" >"y${x}" && rm -f "$x"
done

cat $(sort -n yx*) | sort | uniq -d | \
    while IFS= read -r line; do
        fgrep -x -n "$line" /dev/null yx* | sort -n | sed 1d | \
            while IFS=: read -r file nr rest; do
                sed -i -d ${nr}d "$file"
            done
    done

cat $(sort -n yx*) >uniq_"$1" && rm -f yx*

（概念验证；在投入生产之前需要更多的磨合）。

这里发生了什么：

• split将文件分成10000行一块（可配置），块的名称为x000000，x000001，...
• awk从每个块中删除重复项，而不会干扰行顺序；生成的文件为yx000000，yx000001，... （因为awk无法在同一处进行可移植的更改）
• cat $(sort -n yx*) | sort | uniq -d重新组装块并找到重复项列表；由于块的构造方式，每个重复行最多出现一次在每个块中
• fgrep -x -n "$line" /dev/null yx*查找每个重复行所在的位置；结果是一系列行yx000005:23:some text
• sort -n | sed 1d从上述列表中删除第一个块（这是该行的第一次出现，应该保留）
• IFS=: read -r file nr rest将yx000005:23:some text拆分为file=yx000005，nr=23和其余内容
• sed -i -e ${nr}d "$file"从块$file中删除第$nr行
• cat $(sort -n yx*)重新组装块；它们需要进行排序，以确保它们以正确的顺序出现。

这可能不是非常快，但我想它应该能够工作。将每个块中的行数增加到10000行可以加速操作，但会消耗更多的内存。在跨块重复行数方面，操作为O(N^2)；幸运的是，这可能不会太大。

以上假设使用GNU sed（用于-i）。它还假定当前目录中没有名为x*或yx*的文件（这部分可能需要清理一下，也许通过将垃圾移到由mktemp -d创建的目录中）。

编辑：@EtanReisner的反馈后的第二个版本：

#! /bin/sh
usage ()
{
    echo "Usage:  ${0##*/} <file> [<lines>]" >&2
    exit 1
}


if [ $# -lt 1 -o $# -gt 2 -o ! -f "$1" ]; then usage; fi
if [ "$2" ]; then
    expr "$2" : '[1-9][0-9]*$' >/dev/null || usage
fi

tdir=$(mktemp -d -p "${TEMP:-.}" "${0##*/}_$$_XXXXXXXX") || exit 1
dupes=$(mktemp -p "${TEMP:-.}" "${0##*/}_$$_XXXXXXXX") || exit 1

trap 'rm -rf "$tdir" "$dupes"' EXIT HUP INT QUIT TERM

LC_ALL=C
export LC_ALL

split -l ${2:-10000} -d -a 6 "$1" "${tdir}/x"

ls -1 "$tdir" | while IFS= read -r x; do
    awk '!x[$0]++' "${tdir}/${x}" >"${tdir}/y${x}" && \
    rm -f "${tdir}/$x" || exit 1
done

find "$tdir" -type f -name 'yx*' | \
    xargs -n 1 cat | \
    sort | \
    uniq -d >"$dupes" || exit 1

find "$tdir" -type f -name 'yx*' -exec fgrep -x -n -f "$dupes" /dev/null {} + | \
    sed 's!.*/!!' | \
    sort -t: -n -k 1.3,1 -k 2,2 | \
    perl '
        while(<STDIN>) {
            chomp;
            m/^(yx\d+):(\d+):(.*)$/o;
            if ($dupes{$3}++)
                { push @{$del{$1}}, int($2) }
            else
                { $del{$1} = [] }
        }
        undef %dupes;

        chdir $ARGV[0];

        for $fn (sort <"yx*">) {
            open $fh, "<", $fn
                or die qq(open $fn: $!);
            $line = $idx = 0;
            while(<$fh>) {
                $line++;
                if ($idx < @{$del{$fn}} and $line == $del{$fn}->[$idx])
                    { $idx++ }
                else
                    { print }
            }
            close $fh
                or die qq(close $fn: $!);
            unlink $fn
                or die qq(remove $fn: $!);
        }
    ' "$tdir" >uniq_"$1" || exit 1

- lcd047

---

如果你仔细看的话，除了最终结果外磁盘上使用的空间仅为输入文件的2倍（初始文件和拆分块的大小），加上一个块的大小（每个块有10k行，可能小于1MB）。sort可能需要更多，但那是sort的问题，而不是我的脚本。由于每个块只能有一个重复的行，所以sed不会运行很多次。这就是首先去重块的全部意义。真的，请尝试理解应该发生什么，这并没有那么糟糕。 - lcd047

每个块在处理循环期间会被复制，但总共只有两次磁盘操作。是的，使用这样大小的分割，每个块可能会很小（但这本身可能是一个问题），您的全局匹配模式可能会超出行长度限制，目录遍历可能会因为文件系统无法处理那么多文件而变得非常缓慢，您可能会因为乱序读/写而耗尽磁盘缓存。您正在将唯一的行写入y*文件中。我们知道唯一行的总数大于内存容量，因此每个文件将拥有其中大部分的10k行。 - Etan Reisner

我承认我还没有完全考虑清楚，所以情况可能没有我想象的那么糟糕，但它仍然似乎比其他一些解决方案严格更差。但是，这种方法的好处在于可以用内存来换取磁盘空间，这意味着这种方法可能是唯一可行的方法（取决于数据大小、磁盘空间和可用内存）。 - Etan Reisner

@EtanReisner x文件在创建yx文件的同时就被删除了，不会重复存在。如果需要可以使用xargs等工具解决命令行缓冲区溢出的细节问题（你是否阅读了上面的“概念验证”警告？）。 - lcd047

@EtanReisner 当awk写入时，它们会被复制。 - 不行：awk '!x[$0]++' "$x" >"y${x}" && rm -f "$x"。 我不确定你是否可以使用xargs来处理主要的cat | sort循环 - sort -n ... | xargs -n 1 cat | sort ...。 - lcd047

Answer 5

如果有很多重复内容，一种可能的方法是使用split(1)将文件分成可管理的部分，并使用类似sort/uniq这样的传统方法来制作唯一行的摘要。这将比实际片段本身更短。之后，您可以比较这些部分以得出实际摘要。

- Noufal Ibrahim

---

如果他无法在内存中保存整个唯一行集，我不确定这会有什么帮助。在某个时候，他需要能够在不对它们进行排序的情况下在所有文件之间进行去重。我想可能会有一个聪明的N路去重算法，它不需要一次性将所有唯一行都保存在内存中，但如果有的话，我不知道它是什么。 - Etan Reisner

@EtanReisner 这不是一种无用的方法，跨文件删除重复项几乎可以在合理的时间内完成（请参见我的答案）。 - lcd047

Answer 6

也许不是你一直在寻找的答案，但是这里有一个建议：使用布隆过滤器。https://en.wikipedia.org/wiki/Bloom_filter 这种问题正是它们存在的主要原因之一。

- Mircea