本文章也同步至本人的CSDN博客中： http://blog.csdn.net/u012881584/article/details/70477832
今天來(lái)說(shuō)一個(gè)Java中處理大文本字符串慮重的兩個(gè)解決方案。
相信大家在實(shí)際工作中都遇到過(guò)數(shù)據(jù)重復(fù)的問(wèn)題， 當(dāng)然也就存在慮重的工作。
比如數(shù)據(jù)庫(kù)中需要對(duì)同一個(gè)字段進(jìn)行慮重， 大多數(shù)情況下我們直接使用Set就能解決問(wèn)題， 今天我所說(shuō)的這個(gè)大文本慮重是什么含義呢？一起來(lái)看看需求吧。
需求:
公司SEO人員給了我一個(gè)文本文件， 里面大概有三千多萬(wàn)行字符串， 他們的要求是希望我用最短的時(shí)間把這個(gè)文本文件重復(fù)的給刪除掉。 起初我想的直接用excle去處理吧， 當(dāng)時(shí) 因?yàn)檫@個(gè)文件都達(dá)到了幾百兆， 所以編輯修改起來(lái)都很費(fèi)勁。
這里直接給出解決思路：
首先腦海中想到的第一個(gè)就是用大數(shù)據(jù)去處理， 只是耳邊經(jīng)常聽(tīng)過(guò)Hadoop，Spark之類(lèi)的詞， 但是自己也并未真正接觸過(guò)。于是便一通Google， 然后找到兩個(gè)解決方案。
利用布隆過(guò)濾器去解決。
利用Spark的distinct去解決。
1， 布隆過(guò)濾器
原理
如果想判斷一個(gè)元素是不是在一個(gè)集合里，一般想到的是將集合中所有元素保存起來(lái)，然后通過(guò)比較確定。鏈表、樹(shù)、散列表（又叫哈希表，Hash table）等等數(shù)據(jù)結(jié)構(gòu)都是這種思路。但是隨著集合中元素的增加，我們需要的存儲(chǔ)空間越來(lái)越大。同時(shí)檢索速度也越來(lái)越慢。
Bloom Filter 是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，Bloom filter 可以看做是對(duì) bit-map 的擴(kuò)展, 它的原理是：
當(dāng)一個(gè)元素被加入集合時(shí)，通過(guò) K 個(gè) Hash 函數(shù)將這個(gè)元素映射成一個(gè)位陣列（Bit array）中的 K 個(gè)點(diǎn)，把它們置為 1。檢索時(shí)，我們只要看看這些點(diǎn)是不是都是 1 就（大約）知道集合中有沒(méi)有它了：
如果這些點(diǎn)有任何一個(gè) 0，則被檢索元素一定不在；
如果都是 1，則被檢索元素很可能在。
優(yōu)點(diǎn)
It tells us that the element either definitely is not in the set or may be in the set.
它的優(yōu)點(diǎn)是空間效率和查詢(xún)時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，布隆過(guò)濾器存儲(chǔ)空間和插入 / 查詢(xún)時(shí)間都是常數(shù)O(k)。另外, 散列函數(shù)相互之間沒(méi)有關(guān)系，方便由硬件并行實(shí)現(xiàn)。布隆過(guò)濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求非常嚴(yán)格的場(chǎng)合有優(yōu)勢(shì)。缺點(diǎn)
但是布隆過(guò)濾器的缺點(diǎn)和優(yōu)點(diǎn)一樣明顯。誤算率是其中之一。隨著存入的元素?cái)?shù)量增加，誤算率隨之增加。但是如果元素?cái)?shù)量太少，則使用散列表足矣。
(誤判補(bǔ)救方法是：再建立一個(gè)小的白名單，存儲(chǔ)那些可能被誤判的信息。)
另外，一般情況下不能從布隆過(guò)濾器中刪除元素. 我們很容易想到把位數(shù)組變成整數(shù)數(shù)組，每插入一個(gè)元素相應(yīng)的計(jì)數(shù)器加 1, 這樣刪除元素時(shí)將計(jì)數(shù)器減掉就可以了。然而要保證安全地刪除元素并非如此簡(jiǎn)單。首先我們必須保證刪除的元素的確在布隆過(guò)濾器里面. 這一點(diǎn)單憑這個(gè)過(guò)濾器是無(wú)法保證的。另外計(jì)數(shù)器回繞也會(huì)造成問(wèn)題。
這里只是簡(jiǎn)單做個(gè)介紹， 有興趣的盆友可以參考：
延伸閱讀
學(xué)習(xí)是年輕人改變自己的最好方式