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

猪了个去
  • 349

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

sort bigtext.txt|uniq

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

回复
阅读 19.1k
7 个回答
ninehills
  • 1k
✓ 已被采纳

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亿么,可想而知

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

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

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

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

如果可以忍受误差(就是有一定的误判),bloom filter是个不错的办法。

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

冰雨
  • 1
新手上路,请多包涵

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

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

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

杨勇
  • 2
新手上路,请多包涵

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

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏