我有一個不會更改的大型靜態二進制文件（10GB）。字符串出現在另一個字符串中的次數
我希望能夠輸入小字符串（每個15字節或更低），然後確定哪個字符串是最不頻繁的。
我明白，如果沒有真正搜索整個二進制文件，我無法完全確定這一點，所以我知道這將是一個近似值。
構建一個樹/哈希表是不可行的，因爲它需要大約256^15字節，這是ALOT。
我有大約100GB的磁盤空間和8GB RAM將專門用於此任務，但我似乎無法找到任何方式來實現此任務，而不會實際上通過該文件。
我有儘可能多的時間，因爲我想準備大二進制文件，然後我需要決定哪些是最不頻繁的字符串很多次。
任何想法？
謝謝！ 丹尼爾。
（順便說一句：如果它很重要，我使用Python）
也許建立與計數哈希表儘可能多的n元組，你可以買得起的存儲呢？您可以修剪不再出現的樹木。我不會稱之爲「逼近」，但可能是「上限」，並保證檢測不出現的字符串。
因此，假設您可以構建所有4元組。
然後爲「ABCDEF」的出現次數計算最小計數（ABCD），計數（BCDE），計數（CDEF）。如果其中任何一個爲零，則保證字符串不出現。如果它是一個，它最多隻會出現一次（但也許根本不會）。
因爲你有一個不變的大靜態字符串，你可以區分一次性工作預處理這個字符串，這個字符串永遠不需要從回答查詢的工作中重複。在更強大的機器上做一次性工作可能會很方便。
如果你可以找到一個數量級或更多的內部存儲器的機器，你可以建立一個後綴數組 - 一個以偏移量開始的後綴排序順序的偏移數組。這可以存儲在外部存儲器中用於查詢，並且可以在二分搜索中使用該查找來查找排序順序中的第一個和最後一個位置，其中出現查詢字符串。顯然，兩者之間的距離會給出出現次數，而二進制搜索將需要大約34個二進制文件才能完成16G字節，假設16G字節是2^34字節，因此每個查詢應該花費大約68個磁盤搜索。
指望你找到那麼多的內部存儲空間可能是不合理的，但我剛買了一個1TB的USB硬盤大概50磅，所以我認爲你可以增加一次外部存儲工作。在外部存儲器中有後綴數組構造的算法，但是因爲你的查詢字符串被限制爲15個字節，所以你不需要任何複雜的東西。通過寫出在每個偏移量處找到的15字節字符串，然後是5字節偏移量數字，然後通過外部排序對這些20字節記錄進行排序，創建200GB數據。這將爲您提供50GB的索引到排序順序的字符串中，以便您將其放入外部存儲以回答查詢。
如果您事先知道所有查詢，或者準備對它們進行批處理，另一種方法是從它們構建http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm樹。這在查詢的總大小中花費時間線性。然後，您可以在時間上流過10GB數據，並按時間成比例地與數據大小和任何字符串找到匹配的次數之和成比例。
既然您正在尋找哪個頻率最低，並且願意接受近似的解決方案。您可以使用一系列Bloom filters而不是散列表。如果你使用足夠大的數據，你不需要擔心查詢的大小，因爲你可能保持低誤報率。
這個想法是通過所有可能的查詢大小並使子字符串不在其中。例如，如果查詢將在3到100之間，那麼它將花費（N *（從i = 3到i = 100的（i）的總和））。然後逐個將子集添加到布隆過濾器之一，以便查詢不存在於過濾器中，如果需要，創建具有相同哈希函數的新布隆過濾器。您可以通過遍歷每個過濾器並檢查查詢是否存在於其中。每個查詢然後簡單地通過每個過濾器並檢查它是否在那裏，如果是，則它向計數加1。
您需要嘗試平衡誤報率以及過濾器的數量。如果其中一個濾波器的誤報率過高，那麼它就沒有用了，同樣，如果您擁有數萬億個布隆濾波器（如果您對每個子濾波器進行一次濾波，則很有可能）。有幾種方法可以處理這些問題。
你可能最終不得不實施scalable bloom filters讓事情變得可管理的，這聽起來類似於我建議無論如何，所以應該很好地工作。
你確定你真的想要近似嗎？取決於這是什麼類型的文件，不完整的抽樣可能是相當具有誤導性的。 – Thilo 2013-04-21 06:41:16
也許可以構建一個包含儘可能多的前綴的散列表，因爲您可以負擔得起存儲空間？您可以修剪不再出現的樹木。我不會稱之爲「逼近」，但可能是「上限」，並保證檢測不出現的字符串。 – Thilo 2013-04-21 06:45:26
我將不得不每次運行算法大約20,000次，以決定大約15個字符串（以選擇理想的字符串）。 （大10gb文件將始終保持不變）。 關於哈希表和前綴 - 我想過。我將回答這個問題作爲對下面提出的答案的評論 – Avenger 2013-04-21 07:00:37