比較兩個大檔案的重複資料，有沒有好的演算法？

1樓：龍吟滄海

這個問題在面試中遇到過，我簡單說一下我的思路。

我是這樣理解題意的：檔案a，b，分別有x，y行資料，每一行是乙個字串，現在想找到a和b中重複的資料。

這個問題其實是海量資料面試中非常常見的乙個場景，更細化一點的話可能會要求使用不超過多少的記憶體，在這裡不贅述。

思路1：使用bloom filter演算法。

如果不考慮100%準確率，那麼bloom filter將是很好的選擇，不了解的可以搜尋或者檢視海量資料處理演算法-Bloom Filter - CSDN部落格。

步驟：0）建立乙個大小為m的byte陣列（注意：m的取值和x和y中較大的有關，通常為降低錯誤率，m=nlg(1/E)*lge，具體證略）；

1）遍歷a（假如a是較大的檔案）將每一行，對這一行執行k個雜湊函式得到k個雜湊值，然後將m陣列中對應的位元位設定為1；

2）不考慮記憶體的情況，此時a已經全部儲存到byte陣列中，然後遍歷b的每一行，如果這一行經過k個hash函式得到的k個hash值所對應的陣列都為1，那麼表示該資料是重複的，否則不重複，最後取出所有重複的部分。

該演算法的空間複雜度只有m大小的陣列，不會動態增長，而時間複雜度主要在於(x+y)*k。

注意：bloom filter不能保證100%正確，例如k=3,x1字串經過3個hash得到的是0,1,2，那麼在0,1,2陣列位置為1，而y1經過3個hash恰好也得到0,1,2，這就判定y1存在，但實際上y1可能不存在。

思路2：hash

hash的原理就不說了，這裡主要使用「大而化小，分而治之」的策略。

步驟：0）根據給定記憶體需求或其他限制，預先估計要劃分多少個小檔案，例如1千萬資料可以劃分為100個檔案，然後盡量保證每個檔案分配的資料是均勻的；

1）遍歷a（假如a是較大的檔案），對a的每一行做hash運算，根據hash值將該行資料對映到乙個小檔案a1-a100檔案中；

2）a處理完成後，此時資料已經按照hash策略分布到多個小檔案中。此時遍歷b，做同樣的hash演算法（注意：兩個字串如果相同，那麼他們經過同一hash演算法得到的必然也是相等的），對映到b1-b100小檔案中；

3）逐個比較檔案對，此時資料量夠小，可以裝載到hashmap中進行比對，最後得到結果。

思路3：mapreduce

既然是海量資料，那麼解決方案至少要知道用mr方案。

大致思路（如有不正確請及時指出）：

0）map端主要是遍歷，以每行字串為key，value就是所屬的檔案，例如,,;

1）reduce端主要是將相同key的資料聚合到一起，value進行拼接，那麼假如value中包含a和b的，就表示是重複資料，只輸出這些就可以。

最後：推薦多查閱關於海量資料面試的問題，會比較有幫助。