如何高效地做到大文本去除重复行

Question

主要是对行去重
如果先排序的话。。大约是这样：

sort bigtext.txt|uniq

因为uniq只能去相邻行的重，但是对大文本进行排序这个代价有点大？O(n log n)对于n达到上亿好像太慢了？
其他的使用set更加。。。如果重复率小，吃内存吃的不行。。。

Answer 1

P.S. 哈希表实现对内存有要求，基本上1000w去重后的数据对应1G内存的样子。我都用64G的机器搞，所以还好。。如果再大，上hadoop吧。

如果只是去重，用sort的效率很低（指的是上千万行的量级），因为做了额外操作，因为你只是要去重，而不是排序

用awk数组来实现很简单很快，利用了awk数组是hashtable实现的特性。内存占用和去重后（注意是去重后)的行数（注意是行数，而不是你的文本内容）成正比。

cat 一堆文件 | awk '{ if (!seen[$0]++) { print $0; } }'

来个实际的测试结果吧，取100w 不重复的URL，简单复制一份，形成一个200w行的文件（请原谅我不能拿几亿的数量做测试，因为sort实在太慢了，上面说可以接受的肯定是没有测试过。。）

$ wc -l 200w
2000000 200w
$ tail -1 200w
http://photo.blog.sina.com.cn/photo/511c583f448cc39a9cb5c

$ time cat 200w | sort | uniq > sort_uniq
cat 200w 0.01s user 0.08s system 0% cpu 21.844 total
sort 35.13s user 0.24s system 76% cpu 46.279 total
uniq > sort_uniq 21.43s user 0.17s system 46% cpu 46.278 total

sort && uniq 耗时 46s，并且会打满一个CPU核

$ time cat 200w | sort -u > sort_u
cat 200w 0.01s user 0.08s system 0% cpu 24.806 total
sort -u > sort_u 47.56s user 0.31s system 99% cpu 48.002 total

** sort -u 耗时48s，差不多吧 **

$ time cat 200w | awk '{ if (!seen[$0]++) { print $0; } }' > awk
cat 200w 0.01s user 0.08s system 3% cpu 3.144 total
awk '{ if (!seen[$0]++) { print $0; } }' > awk 2.83s user 0.23s system 96% cpu 3.158 total

awk 方法耗时3s , 而且最重要的awk方法的时间复杂度是O(n)， sort是O(nlogn)，200w就差这么大，2000w呢，2亿么，可想而知

Answer 2

但是对大文本进行排序这个代价有点大？O(n log n)对于n达到上亿好像太慢了？

代价不大。排序的话是省内存的。（sort的算法实现应该是比较高效的。）

要不就是对每行算SHA-1，这样只要比较SHA-1就可以。

Answer 3

有时候超大文本你的内存受不了，所以比较好的方法是找几个分割点，把所有数据分成N堆，各自排序后组合。（貌似得编码……）

Answer 4

如果可以忍受误差（就是有一定的误判），bloom filter是个不错的办法。

Answer 5

我提供一个思路供您参考。
扫一遍文件，对每一行计算一个MD5或者SHA-1值，在内存构建trie树。鉴于数据量很大，生成的MD5值应该存在许多前缀，所以采用trie可以节省空间（如果想进一步节省空间，可以采用三向单词查找树，比trie分支更少），而且trie树的深度不会超过MD5值的长度，几十而已，每次查找或者插入MD5值都是个时间复杂度为常数的操作。向trie添加某个MD5值时如果发现该值已经存在，则抛弃目前扫描的行；如果不存在，则把MD5值插入trie树，把当前扫描行写入结果文件（这个文件保存所有不重复的行）。
这样，扫描一遍文件就能实现去重。

Answer 6

例如：多个大数据文本文件合并以及文本行去重 130Gb 20亿行数据 60分钟即可完成去重操作

互联网上目前最快的单机版软件 爬虫工具的最佳拍档 支持TB级文本文件合并去重

作者：zhengzizhi
来源：CSDN
原文：https://blog.csdn.net/zhengzi...
版权声明：本文为博主原创文章，转载请附上博文链接！

Answer 7

awk '!x[$0]++' file1 fiel2 file3....