【Java】大文本字符串滤重的简单方案

今天来说一个Java中处理大文本字符串虑重的两个解决方案。

相信大家在实际工作中都遇到过数据重复的问题, 当然也就存在虑重的工作。 比如数据库中需要对同一个字段进行虑重, 大多数情况下我们直接使用Set就能解决问题, 今天我所说的这个大文本虑重是什么含义呢?一起来看看需求吧。 需求: 公司SEO人员给了我一个文本文件, 里面大概有三千多万行字符串, 他们的要求是希望我用最短的时间把这个文本文件重复的给删除掉。 起初我想的直接用excle去处理吧, 当时 因为这个文件都达到了几百兆, 所以编辑修改起来都很费劲。

这里直接給出解决思路:

首先脑海中想到的第一个就是用大数据去处理, 只是耳边经常听过Hadoop,Spark之类的词, 但是自己也并未真正接触过。于是便一通Google, 然后找到两个解决方案。

  • 利用布隆过滤器去解决。
  • 利用Spark的distinct去解决。

1, 布隆过滤器

  • 原理 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加,我们需要的存储空间越来越大。同时检索速度也越来越慢。

Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是:

当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:

如果这些点有任何一个 0,则被检索元素一定不在; 如果都是 1,则被检索元素很可能在。

  • 优点 It tells us that the element either definitely is not in the set or may be in the set. 它的优点是空间效率和查询时间都远远超过一般的算法,布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
  • 缺点 但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。

(误判补救方法是:再建立一个小的白名单,存储那些可能被误判的信息。)

另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

这里只是简单做个介绍, 有兴趣的盆友可以参考:更多布隆过滤器简介

  • 代码示例: public static void main(String[] args) throws Exception { final BloomFilter<String> dealIdBloomFilter = BloomFilter.create(new Funnel<String>() { @Override public void funnel(String from, PrimitiveSink into) { into.putString(from, Charsets.UTF_8); } //0.0000001d为错误率, 9000000 为预估元素的个数, 我第一次测试用了大概9000000行字符串的文本 }, 9000000, 0.0000001d); BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("C:\\Users\\WangMeng\\Desktop\\test.txt")), "utf-8")); String line; int i = 0; StringBuilder sb = new StringBuilder(); while ((line = br.readLine()) != null) { final boolean put = dealIdBloomFilter.put(line); if (put) { sb.append(line).append("\n"); i++; } if (i % 1000 == 0) { //保存虑重后的文本。 FileUtils.write(new File("C:\\Users\\WangMeng\\Desktop\\Java类\\seo\\bloomFilterSplit.txt"), sb.toString(), Charsets.UTF_8, true); sb = new StringBuilder(); } } }

使用BloomFilter,有三个重要的值,错误率(false positive rate)、哈希函数个数以及BloomFilter位数组的大小,关于这三个值的最优配置算法,相关阅读中的文章有详细的说明。有一个原则,(BloomFilter位数组大小)/(实际的元素个数)越大,错误率越低,但消耗的空间会越多.

2, 使用Spark过滤大文本文件

使用或者说接触Spark是因为公司有人做过一次这个方面的分享, 所以有些耳熟, 于是便从网上找了些入门按理, 自己尝试着用了一下。

  • 使用Spark首先需要在pom文件中引入spark-core包 <!-- https://mvnrepository.com/artifact/org.apache.spark/spark-core_2.11 --> <dependency> <groupId>org.apache.spark</groupId> <artifactId>spark-core_2.11</artifactId> <version>2.1.0</version> </dependency>
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, 毕竟现在比较流行大数据, 有时间我也会继续探究大数据的相关内容。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大史住在大前端

野生前端的数据结构基础练习(5)——散列

散列函数相关的应用非常广,例如webpack打包时在文件名中添加的哈希值,将给定信息转换为固定位数字符串的加密信息等都是散列的实际应用,感兴趣的读者可以自行搜索...

872
来自专栏互扯程序

设计模式不止23种!

现在是资源共享的时代,同样也是知识分享的时代,如果你觉得本文能学到知识,请把知识与别人分享。

1234
来自专栏Java爬坑系列

【JAVA零基础入门系列】Day14 Java对象的克隆

  今天要介绍一个概念,对象的克隆。本篇有一定难度,请先做好心理准备。看不懂的话可以多看两遍,还是不懂的话,可以在下方留言,我会看情况进行修改和补充。   克隆...

2086
来自专栏机器之心

数据科学入门必读:如何使用正则表达式?

选自Dataquest 作者:Alex Yang 机器之心编译 参与:Panda 正则表达式对数据处理而言非常重要。近日,Dataquest 博客发布了一篇针对...

34410
来自专栏黑泽君的专栏

linux系统下,警告:warning: implicit declaration of function ‘gets’ [-Wimplicit-function-declaration] 和 war

gets()函数的基本用法为: char *gets(char *s); 该函数的参数是一个字符数组,该函数的返回值也是一个字符数组。

4021
来自专栏Java帮帮-微信公众号-技术文章全总结

十道海量数据处理面试题与十个方法总结 【面试+提高】

十道海量数据处理面试题与十个方法总结 一、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。   此题,在我之前的一篇文章算法里头...

6458
来自专栏Android开发实战

设计模式-访问者模式

访问者模式的基本想法是,软件系统中拥有一个由许多对象构成的、比较稳定的对象结构,这些对象的类都拥有一个 accept 方法用来接受访问者对象的访问。访问者是一个...

1203
来自专栏醒者呆

基础大扫荡——背包,栈,队列,链表一口气全弄懂

提到数据结构,不得不说数据类型,有人将他们比作分子和原子的关系,我们都知道大自然最小的构成单位是原子,数据类型描述的是原子的内部,如质子、中子的情况,而数据结构...

41215
来自专栏从流域到海域

《Java程序设计基础》 第4章手记

《Java程序设计基础》 第4章手记 本章主要内容 - 语句和复合语句 - 分支结构 - 循环结构 - 跳转语句 这四部...

2028
来自专栏AI科技大本营的专栏

实操 | 内存占用减少高达90%,还不用升级硬件?没错,这篇文章教你妙用Pandas轻松处理大规模数据

编译 | AI科技大本营(rgznai100) 参与 | 周翔 注:Pandas(Python Data Analysis Library) 是基于 Num...

2644

扫码关注云+社区

领取腾讯云代金券