在大文件中查找重複的字符串

文件包含大量（例如10億）字符串，您需要查找重複的字符串。你有N個系統可用。如何找到重複的文件在大文件中查找重複的字符串

2010-10-09 Tushar Gupta

這功課嗎？這聽起來像是作業。 – SoapBox 2010-10-09 18:23:55

將文件拆分爲N個部分。在每臺機器上，儘可能多地將內容加載到內存中，然後對字符串進行排序。將這些塊寫入該機器的大容量存儲器中。在每臺機器上，將塊合併成單個流，然後將來自每臺機器的流合併到包含按排序順序排列的所有字符串的流中。將每個字符串與前一個比較如果它們相同，則是重複的。

來源

2010-10-09 18:26:14 erickson

要將塊合併爲單個流，您必須加載內存中的所有記錄。對於一個1mil的記錄文件，所有1mil記錄必須在上述算法的最後一個合併步驟的內存中？如果是的話，那就違背了目的。 – 2012-12-18 07:38:48

@AndyDufresne「要將塊合併爲單個流，您必須加載內存中的所有記錄。」不，你不會的。您只需要足夠的內存一次加載來自每個塊的下一個字符串，以便比較它們。一旦比較完成，下一個字符串將佔用該內存空間。 – erickson 2012-12-18 17:48:18

我不明白你的合併算法。假設我們有1密耳的記錄文件，並且只有5k條記錄可以加載到內存中。根據我的理解，我需要首先將文件分成N份，每份5K記錄。然後對每個5k記錄文件中的所有記錄進行排序並回寫。要合併兩個5k記錄文件，我必須在內存中加載10k記錄嗎？如果這不是你的意思，你可以解釋一下在1mil記錄文件中找到重複記錄的步驟，只加載5k記錄的內存限制。 – 2012-12-19 09:31:03

埃裏克森的答案可能是任何人設置這個問題的預期。

你可以使用每個N個機組的在一個哈希表中的桶：對於每個字串

（比方說串號我按順序）計算散列函數就可以了，H。
將i和h的值發送到機器編號爲n的存儲器，其中n = h％N，其中來自每個機器的n = h％N
，一起檢索收到多於一個索引的所有散列值h的列表，與索引列表。
檢查具有相同散列值的字符串集合，以查看它們是否實際相等。

老實說，儘管如此，對於100億個字符串，你可以在1臺PC上做到這一點。哈希表可能會佔用80-120 GB和32位哈希值，具體取決於哈希表的實現方式。如果你正在尋找一個高效的解決方案，你必須更具體一些你的意思是「機器」，因爲它取決於每個人擁有多少存儲空間以及網絡通信的相對成本。

來源

2010-10-09 19:27:41

在大文件中查找重複的字符串

回答

相關問題