本文章也同步至本人的CSDN博客中： http://blog.csdn.net/u012881584/article/details/70477832

今天來說一個Java中處理大文本字符串慮重的兩個解決方案。

相信大家在實際工作中都遇到過數(shù)據(jù)重復的問題， 當然也就存在慮重的工作。
比如數(shù)據(jù)庫中需要對同一個字段進行慮重， 大多數(shù)情況下我們直接使用Set就能解決問題， 今天我所說的這個大文本慮重是什么含義呢？一起來看看需求吧。
需求:
公司SEO人員給了我一個文本文件， 里面大概有三千多萬行字符串， 他們的要求是希望我用最短的時間把這個文本文件重復的給刪除掉。 起初我想的直接用excle去處理吧， 當時 因為這個文件都達到了幾百兆， 所以編輯修改起來都很費勁。

這里直接給出解決思路：

首先腦海中想到的第一個就是用大數(shù)據(jù)去處理， 只是耳邊經(jīng)常聽過Hadoop，Spark之類的詞， 但是自己也并未真正接觸過。于是便一通Google， 然后找到兩個解決方案。

  • 利用布隆過濾器去解決。

  • 利用Spark的distinct去解決。

1， 布隆過濾器

  • 原理
    如果想判斷一個元素是不是在一個集合里，一般想到的是將集合中所有元素保存起來，然后通過比較確定。鏈表、樹、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結構都是這種思路。但是隨著集合中元素的增加，我們需要的存儲空間越來越大。同時檢索速度也越來越慢。

Bloom Filter 是一種空間效率很高的隨機數(shù)據(jù)結構，Bloom filter 可以看做是對 bit-map 的擴展, 它的原理是：

當一個元素被加入集合時，通過 K 個 Hash 函數(shù)將這個元素映射成一個位陣列（Bit array）中的 K 個點，把它們置為 1。檢索時，我們只要看看這些點是不是都是 1 就（大約）知道集合中有沒有它了：

如果這些點有任何一個 0，則被檢索元素一定不在；
如果都是 1，則被檢索元素很可能在。

  • 優(yōu)點
    It tells us that the element either definitely is not in the set or may be in the set.
    它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，布隆過濾器存儲空間和插入 / 查詢時間都是常數(shù)O(k)。另外, 散列函數(shù)相互之間沒有關系，方便由硬件并行實現(xiàn)。布隆過濾器不需要存儲元素本身，在某些對保密要求非常嚴格的場合有優(yōu)勢。

  • 缺點
    但是布隆過濾器的缺點和優(yōu)點一樣明顯。誤算率是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。

(誤判補救方法是：再建立一個小的白名單，存儲那些可能被誤判的信息。)

另外，一般情況下不能從布隆過濾器中刪除元素. 我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，每插入一個元素相應的計數(shù)器加 1, 這樣刪除元素時將計數(shù)器減掉就可以了。然而要保證安全地刪除元素并非如此簡單。首先我們必須保證刪除的元素的確在布隆過濾器里面. 這一點單憑這個過濾器是無法保證的。另外計數(shù)器回繞也會造成問題。

這里只是簡單做個介紹， 有興趣的盆友可以參考：

網(wǎng)友評論