本文章也同步至本人的 CSDN 博客中: http://blog.csdn.net/u012881584/article/details/70477832
相信大家在实际工作中都遇到过数据重复的问题, 当然也就存在虑重的工作。 比如数据库中需要对同一个字段进行虑重, 大多数情况下我们直接使用 Set 就能解决问题, 今天我所说的这个大文本虑重是什么含义呢?一起来看看需求吧。 需求: 公司 SEO 人员给了我一个文本文件, 里面大概有三千多万行字符串, 他们的要求是希望我用最短的时间把这个文本文件重复的给删除掉。 起初我想的直接用 excle 去处理吧, 当时 因为这个文件都达到了几百兆, 所以编辑修改起来都很费劲。
首先脑海中想到的第一个就是用大数据去处理, 只是耳边经常听过 Hadoop,Spark 之类的词, 但是自己也并未真正接触过。于是便一通 Google, 然后找到两个解决方案。
Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是:
当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:
如果这些点有任何一个 0,则被检索元素一定不在; 如果都是 1,则被检索元素很可能在。
(误判补救方法是:再建立一个小的白名单,存储那些可能被误判的信息。)
另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
这里只是简单做个介绍, 有兴趣的盆友可以参考:更多布隆过滤器简介。
- public static void main(String[] args)throwsException {finalBloomFilter dealIdBloomFilter = BloomFilter.create(newFunnel() {
- @Override
- public void funnel(String from, PrimitiveSink into) {
- into.putString(from, Charsets.UTF_8);
- }//0.0000001d为错误率, 9000000 为预估元素的个数, 我第一次测试用了大概9000000行字符串的文本},9000000,0.0000001d);
- BufferedReader br =newBufferedReader(newInputStreamReader(newFileInputStream(newFile("C:\\Users\\WangMeng\\Desktop\\test.txt")),"utf-8"));
- String line;inti =0;
- StringBuilder sb =newStringBuilder();while((line = br.readLine()) !=null) {final booleanput = dealIdBloomFilter.put(line);if(put) {
- sb.append(line).append("\n");
- i++;
- }if(i %1000==0) {//保存虑重后的文本。FileUtils.write(newFile("C:\\Users\\WangMeng\\Desktop\\Java类\\seo\\bloomFilterSplit.txt"),
- sb.toString(), Charsets.UTF_8,true);
- sb =newStringBuilder();
- }
- }
- }
来源: http://www.cnblogs.com/wang-meng/p/6750128.html