如何比較大型文本文件？

Question

我對你對我的「技術」的看法有一個普遍的疑問。

有兩個文本文件（file_1和file_2）需要相互比較。兩者都非常巨大（3-4千兆字節，每個3000萬到4500萬行）。 我的想法是將file_1的幾行（儘可能多）讀到內存中，然後將這些行與全部行的file_2進行比較。如果匹配，則匹配的兩個文件中的行應寫入新文件。然後繼續下一行1000行file_1，也比較那些全部行file_2，直到我完全通過file_1。

但這聽起來確實非常耗時且對我來說很複雜。 你能想出其他方法來比較這兩個文件嗎？

您認爲比較可能需要多長時間？ 對於我的課程，時間並不重要。我沒有處理這些龐大文件的經驗，因此我不知道這可能需要多長時間。但不應該超過一天。 ;-)但我恐怕我的技術可能會永遠...

剛纔出現在我腦海中的Antoher問題：你會在內存中讀多少行？越多越好？有沒有辦法在實際嘗試之前確定可能的行數？ 我想盡可能多的閱讀（因爲我認爲這樣會更快），但我經常用完內存。

在此先感謝。

編輯 我想我必須多解釋一下我的問題。

目的不是看兩個文件一般是否相同（它們不是）。 每個文件中有一些共享相同「特徵」的行。 下面是一個例子： file_1看起來有點像這樣：

mat1 1000 2000 TEXT  //this means the range is from 1000 - 2000 
mat1 2040 2050 TEXT 
mat3 10000 10010 TEXT 
mat2 20 500 TEXT 

file_2看起來是這樣的：

mat3 10009 TEXT 
mat3 200 TEXT 
mat1 999 TEXT 

TEXT指的是不感興趣的，我字符和數字，mat可以從mat1 - mat50去並沒有順序;也可能有1000x mat2（但下一列中的數字不同）。我需要找到適合的線條：matX在兩條比較線中都相同，file_2中提到的數字符合file_1中提及的範圍。 所以在我的例子中，我會找到一個匹配：file_1的第3行和file_2的第1行（因爲mat3和10009都在10000和10010之間）。 我希望這對你很清楚！

所以我的問題是：你將如何搜索匹配的行？

是的，我使用Java作爲我的編程語言。

編輯 我現在先分了巨大的文件，使我有被淘汰的內存沒有問題。我也認爲將比較（很多）較小的文件比兩個大文件比較快。之後，我可以按照上面提到的方式比較它們。這可能不是完美的方式，但我仍然在學習;-) 但是，所有的方法都對我非常有幫助，謝謝你的回覆！

Answer 1

既然您已經提供了更多細節，我將採用的方法依賴於預分區，並且可以在搜索匹配之前進行排序。

這應該消除大量的比較，否則在天真的蠻力方法中無論如何不會匹配。爲了爭論起見，讓我們把這兩個文件夾在4000萬行。

分區：通讀file_1和發送的所有行與mat1開始file_1_mat1，等等。 file_2也一樣。這是一個小的grep微不足道的，或者你是否應該用Java編程，這是一個初學者的練習。

這是一次讀取總共8000萬行讀取的兩個文件，產生兩組平均每個80萬行的50個文件。

排序：對於每個分區，排序根據僅在第二列中的數字值（從file_1下界和從file_2實際數量）。即使80萬行不能放入內存中，我們也可以調整2路外部合併排序，並且比未排列的空間更快地執行此操作（讀取次數更少）。

比較：現在你只需要遍歷一次通過兩對file_1_mat1和file_2_mat1，而不需要將你的東西在內存中，輸出匹配到輸出文件。依次重複其餘的分區。不需要最終的「合併」步驟（除非您正在並行處理分區）。

即使沒有分類階段你已經做的工作​​應該更快速地50對文件的80萬行，每行，而不是兩個文件各40萬線的幼稚比較。

Answer 2

有一個折衷：如果您讀取了一大塊文件，則會保存光盤seek time，但您可能已經讀取了您不需要的信息，因爲在第一行中遇到了更改。

在平均情況下，您應該運行一些實驗[基準測試]，使用不同的塊大小來找出最佳讀取塊。

Answer 3

儘量避免內存消耗並使其消耗光盤。 我的意思是將每個文件分成可加載大小的部分並進行比較，這可能需要一些額外的時間，但會使您安全地處理內存限制。

Answer 4

我從來沒有使用過如此巨大的文件，但這是我的想法，應該工作。

你可以看看哈希。使用SHA-1散列。

導入以下

import java.io.FileInputStream; 
import java.security.MessageDigest; 

一旦你的文本文件等已加載有它遍歷每一行，並在最後打印出來的哈希值。下面的示例鏈接將更加深入。

StringBuffer myBuffer = new StringBuffer(""); 
//For each line loop through 
    for (int i = 0; i < mdbytes.length; i++) { 
     myBuffer.append(Integer.toString((mdbytes[i] & 0xff) + 0x100, 16).substring(1)); 
    } 
System.out.println("Computed Hash = " + sb.toString()); 

SHA Code example focusing on Text File

SO Question about computing SHA in JAVA (Possibly helpful)

Another sample of hashing code.

簡單讀取每個文件seperatley，如果每個文件的散列值是在所述過程結束時相同，則這兩個文件是相同的。如果沒有，那麼有什麼不對。

然後，如果你有不同的價值，你可以做超級耗時的逐行檢查。

總體而言，似乎逐行讀取逐行等將永遠佔用。如果你試圖找出每個人的差異，我會這樣做。但我認爲散列會更快，看看它們是否相同。

SHA checksum

Answer 5

不知道如何很好的答案，這將是 - 但看看這個頁面：http://c2.com/cgi/wiki?DiffAlgorithm - 總結了幾個差異算法。 Hunt-McIlroy算法可能是更好的實現。從該頁面還有一個指向GNU diff的java實現的鏈接。不過，我認爲在C/C++中編譯爲本地代碼的實現會更快。如果你堅持使用java，你可能會考慮JNI。

Answer 6

在理想的世界中，您可以將file_2的每一行讀入內存（可能使用快速查找對象，如HashSet，具體取決於您的需要），然後從file_1的每行讀取一行並將它與包含file_2行的數據結構進行比較。

正如你所說你用盡了內存，但我認爲一個分而治之類型的策略將是最好的。您可以使用與我上面提到的方法相同的方法，但是從file_2中讀取一半（或三分之一，四分之一...取決於您可以使用多少內存）並存儲它們，然後比較所有行在file_1中。然後在下一個半/三分之一/四分之一讀入內存（替換舊的行）並再次通過file_1。這意味着你必須更多地通過file_1，但你必須處理你的記憶限制。

---

編輯：在回答你的問題的補充細節，我會改變我的答案部分。而不是讀取file_2（或分塊）中的所有內容，並一次讀入file_1中的一行，反之，因爲file_1包含要檢查的數據。

此外，關於搜索匹配線。我認爲最好的辦法是在file_1上做一些處理。創建一個HashMap<List<Range>>，它將字符串（「mat1」 - 「mat50」）映射到Range s的列表（僅用於startOfRange int和endOfRange int的包裝），並使用來自file_1的數據填充它。然後編寫一個函數（忽略錯誤檢查）

boolean isInRange(String material, int value) 
{ 
    List<Range> ranges = hashMapName.get(material); 
    for (Range range : ranges) 
    { 
     if (value >= range.getStart() && value <= range.getEnd()) 
     { 
      return true; 
     } 
    } 
    return false; 
} 

併爲file_2的每個（已分析）行調用它。

Answer 7

事實上，這可能需要一段時間。你必須做1,200.000,000行比較。 有幾種可能性，以加快順序magnifying：

一個將排序file2並做文件級別的二進制搜索。 另一種方法：計算每一行的校驗和，然後搜索它。根據平均線長，有問題的文件會更小，你，如果你存儲在固定格式校驗（即長）

的行數從file_1讀一次真的可以做一個二進制搜索不過不是的事。面對非常複雜的情況，這是微觀優化。

Answer 8

如果你想要一個簡單的方法：你可以散列兩個文件並比較散列。但它可能更快（特別是如果文件不同）使用你的方法。關於內存消耗：只要確保你使用足夠的內存，使用沒有緩衝區這種事情是一個壞主意。

所有那些關於散列，校驗和等的答案：那些不是更快。在這兩種情況下你都必須閱讀整個文件。使用哈希/校驗和，你甚至不得不計算一些東西......

Answer 9

你可以做的是對每個單獨的文件進行排序。例如UNIX中的或類似的。您可以一次讀取一行中的排序文件以執行合併排序。

Answer 10

使用源碼控制如Mercurial怎麼樣？我不知道，也許它不完全是你想要的，但這是一個旨在追蹤修訂之間變化的工具。您可以創建一個存儲庫，提交的第一個文件，然後用另一個覆蓋它的承諾第二個：

hg init some_repo 
cd some_repo 
cp ~/huge_file1.txt . 
hg ci -Am "Committing first huge file." 
cp ~/huge_file2.txt huge_file1.txt 
hg ci -m "Committing second huge file." 

從這裏你可以得到一個差異，告訴你什麼行不同。如果你能以某種方式使用該差異來確定哪些線是相同的，那麼你將全部設置。

這只是一個想法，有人糾正我，如果我錯了。

Answer 11

我想，你的方式是比較合理的。

我能夠想象不同的策略 - 例如，你可以比較前兩個文件進行排序（其中是有效率的執行文件排序，而UNIX排序實用程序可以在幾分鐘內排序幾個GB的文件），並且，同時排序，你可以比較順序閱讀文件，逐行閱讀。

但是這是一種相當複雜的方式 - 你需要運行外部程序（排序），或者在java中編寫類似的文件的高效實現 - 這本身並不是一件容易的事情。所以，爲了簡單起見，我認爲你分塊閱讀的方式是非常有前途的;

至於如何找到合理的塊 - 首先，它可能是不正確的「越多越好」 - 我認爲，所有工作的時間將漸近地增長到一些恆定的線。所以，你可能會更快地接近那條線，然後你會想 - 你需要基準。

下一頁 - 你可以讀取行緩衝像這樣：

final List<String> lines = new ArrayList<>(); 
try{ 
    final List<String> block = new ArrayList<>(BLOCK_SIZE); 
    for(int i=0;i<BLOCK_SIZE;i++){ 
     final String line = ...;//read line from file 
     block.add(line); 
    } 
    lines.addAll(block); 
}catch(OutOfMemory ooe){ 
    //break 
} 

所以，你讀那麼多的行，你可以 - 留下的空閒內存最後BLOCK_SIZE。 BLOCK_SIZE應該是大到你的程序運行沒有OOM

Answer 12

如果你想確切地知道文件是否不同，那麼沒有比你更好的解決方案 - 按順序比較。

然而，如果文件是相同的，你可以做出一些啓發式的方法來告訴你某種概率。 1）檢查文件大小;這是最簡單的。 2）取一個隨機的文件位置並比較兩個文件中從這個位置開始的字節塊。 3）重複步驟2）以達到所需的概率。

您應該計算並測試您的程序有多少次讀取（以及塊的大小）。

Answer 13

我的解決方案是先生成一個文件的索引，然後用它來做比較。這與使用散列的其他一些答案類似。

你提到行數高達約4500萬。這意味着你可以（可能）存儲一個索引，每個條目使用16個字節（128位），它將使用大約45,000,000 * 16 =〜685MB的RAM，這在現代系統中並非不合理。使用我在下面描述的解決方案會有一些開銷，所以您仍然可能會發現需要使用其他技術（如內存映射文件或基於磁盤的表）來創建索引。有關如何將索引存儲在基於磁盤的快速哈希表中的示例，請參見Hypertable或HBase。

因此，在充分，算法會是這樣的：

1. 創建一個哈希地圖，龍映射到多頭的列表（HashMap的<長，名單<龍>>）
2. 獲取第一個文件中每行的散列（Object。的hashCode應該是足夠了）
3. 獲得該行的文件中的偏移，所以你可以再次找到它後
4. 添加的偏移量與在哈希表
5. 匹配哈希碼線的列表進行比較的每一行第二個文件索引
6. 設定線偏移保持具有匹配條目
任何線

編輯： 在回答你的問題，編輯，這不會真正本身幫助。你可以散列該行的第一部分，但它只會創建50個不同的條目。然後，您可以在數據結構中創建另一個級別，它將每個範圍的開始映射到它所來自的行的偏移​​量。

所以像index.get("mat32")這樣的東西會返回一個範圍的TreeMap。您可以查找您要查找的值前面的範圍lowerEntry()。在一起，這將給你一個相當快的檢查，看看一個給定的matX /數字組合是否在你正在檢查的範圍之一。

Answer 14

我會嘗試以下操作：對於您正在比較的每個文件，在磁盤上創建臨時文件（以後稱其爲部分文件），以表示每個字母字母以及其他所有字符的附加文件。然後逐行讀取整個文件。同時這樣做，將行插入到與它開頭的字母相對應的相關文件中。既然你已經完成了這兩個文件，你現在可以限制一次加載兩個較小文件的比較。例如以A開頭的行只能出現在一個部分文件中，並且不需要多次比較每個部分文件。如果生成的文件仍然非常大，則可以對生成的部分文件（字母特定文件）應用相同的方法，通過根據文件中的第二個字母創建文件來進行比較。這裏的交易將暫時使用大磁盤空間，直到該過程完成。在這個過程中，這裏其他帖子中提到的方法可以幫助更有效地處理部分文件。