相信大家在实际工作中都遇到过数据重复的问题, 当然也就存在虑重的工作。 比如数据库中需要对同一个字段进行虑重, 大多数情况下我们直接使用Set就能解决问题, 今天我所说的这个大文本虑重是什么含义呢?一起来看看需求吧。 需求: 公司SEO人员给了我一个文本文件, 里面大概有三千多万行字符串, 他们的要求是希望我用最短的时间把这个文本文件重复的给删除掉。 起初我想的直接用excle去处理吧, 当时 因为这个文件都达到了几百兆, 所以编辑修改起来都很费劲。
首先脑海中想到的第一个就是用大数据去处理, 只是耳边经常听过Hadoop,Spark之类的词, 但是自己也并未真正接触过。于是便一通Google, 然后找到两个解决方案。
Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是:
当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:
如果这些点有任何一个 0,则被检索元素一定不在; 如果都是 1,则被检索元素很可能在。
(误判补救方法是:再建立一个小的白名单,存储那些可能被误判的信息。)
另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
这里只是简单做个介绍, 有兴趣的盆友可以参考:更多布隆过滤器简介。
使用BloomFilter,有三个重要的值,错误率(false positive rate)、哈希函数个数以及BloomFilter位数组的大小,关于这三个值的最优配置算法,相关阅读中的文章有详细的说明。有一个原则,(BloomFilter位数组大小)/(实际的元素个数)越大,错误率越低,但消耗的空间会越多.
使用或者说接触Spark是因为公司有人做过一次这个方面的分享, 所以有些耳熟, 于是便从网上找了些入门按理, 自己尝试着用了一下。
public static void main(String[] args) throws Exception {
System.setProperty("hadoop.home.dir", "C:\\Users\\WangMeng\\Desktop\\Java类\\hadoop-common-2.2.0\\");
SparkConf conf = new SparkConf().setAppName("Text String Distinct").setMaster("local").set("spark.executor.memory", "1g");
JavaSparkContext sc = new JavaSparkContext(conf);
//读取需要虑重的文本文件
JavaRDD<String> textFile = sc.textFile("C:\\Users\\WangMeng\\Desktop\\Java类\\seo\\test.txt");
final JavaRDD<String> distinct = textFile.distinct();
final long count = distinct.count();
//保存率重后的文本文件
distinct.coalesce(1).saveAsTextFile("C:\\Users\\WangMeng\\Desktop\\Java类\\seo\\sparkSplit.txt");
}
用Spark是不是很简单?代码也很少, 只需要读取文本创建一个rdd, 然后使用distinct就可以了, 如果想了解更多可以查看:Spark更多介绍。
在windows下这里好像好需要一个hadoop-common-2.2.0包, 如果不引入会报找不到winutils.exe, 这里提供一个下载地址, 如果不能下载了请联系我。hadoop-common-2.2.0下载地址
到了这里就讲完了, 当然, 对于大文本的处理还是有更多更好的方法的,我这里只是尝试了这两种方案, 处理千万级行的数据都不用一分钟就可以虑重好, 布隆过滤器和Spark过滤后的行数都是相差无几的, 这里我还是更推荐使用Spark, 毕竟现在比较流行大数据, 有时间我也会继续探究大数据的相关内容。