unix - 确定文本文件中唯一性和重复性的最佳方法

Question

我有一个大约 2000 万行的文本文件。每行长度为 25 个字符。我估计可能有大约 200k-300k 独特的行。我想知道到底有多少条独特的线，以及每条线有多少次出现(我希望结果是幂律式的)。

我可以这样做:

sort bigfile|uniq -c |sort -nr > uniqcounts
wc -l uniqcounts

但这是非常低效的内存和时间。

对于这个问题，你最好的命令行解决方案是什么？

Answer 1

当我遇到这样的文本处理问题时，我倾向于使用 Perl，尤其是因为 Perl 安装在大多数 Unix 系统上。 (你可以用 awk 做同样的事情，这可能更可用。)

这样的事情应该可以解决问题:

#!/usr/bin/perl

while(<>) {
    chomp;
    $lines{$_}++;
}

print "Total unique lines: ", scalar(keys %lines), "\n";
foreach my $line (sort {$lines{$b} <=> $lines{$a}} keys %lines) {
    printf "%6d  %s\n", $lines{$line}, $line;
}

(您可以将其作为单行来执行，但拆分后更易于阅读。)

这需要 O(n) 内存用于散列键，其中 n 是唯一行数。运行时效率取决于哈希查找，但会介于 O(n)(如果没有哈希冲突)和 O(n*log n)(平衡树)之间。在最坏的情况下，最终的可选排序可能需要 O(n^2)，并且如果唯一行数很高，则可能会主导运行时。