文件支持Trie（或前綴樹）實現

Question

我必須在C++ map中存儲大量字符串以保持唯一字符串，並且當發生重複字符串時，我只需要增加計數器（pair.second）。我用過C++ map，它非常適合這種情況。由於處理現在已經消失的文件達到30gig，我試圖將它保存在文件而不是內存中。

在這種情況下，我還遇到了比map快的trie。任何人都知道文件支持的實施？我遇到Trie類似於我正在尋找的實現，但似乎沒有錯誤。

Answer 1

如果你能排序你的文件包含字符串，然後閱讀排序列表和計數重複將是容易的。 （您可以保留原始文件並創建一個新的排序字符串文件。）有效地排序大文件是舊技術。你應該能夠找到一個實用程序。

如果你不能排序，那麼考慮digesting的字符串。 MD5可能是爲了你的目的而矯枉過正。你可以拼湊一些東西。對於數十億字符串，您可以使用8個字節的摘要。使用摘要樹（可能是BST）。對於每個摘要，存儲產生該摘要的唯一字符串的文件偏移量。

當您讀取一個字符串時，計算它的摘要並查找它。如果你沒有找到摘要，你就知道這個字符串是唯一的。將它存儲在樹中。如果您找到摘要，請檢查每個關聯的字符串是否匹配並進行相應處理。

要比較字符串，您需要轉到該文件，因爲您存儲的所有文件都是文件偏移量。

重要的是要記住，如果兩個摘要不同，產生它們的字符串必須不同。如果摘要相同，字符串可能不一樣，所以您需要檢查。當重複字符串較少時，此算法效率更高。

Answer 2

你打算如何一次加載30GB的內存？而且，由於它是一種基於字典的行爲，我想可以在每次插入或增量時加載整個文件（即便是逐件）以進行查找。

我建議使用數據庫。這就是他們的目的......