文件支持Trie（或前缀树）实现

Question

我必须在C++ map中存储大量字符串以保持唯一字符串，并且当发生重复字符串时，我只需要增加计数器（pair.second）。我用过C++ map，它非常适合这种情况。由于处理现在已经消失的文件达到30gig，我试图将它保存在文件而不是内存中。

在这种情况下，我还遇到了比map快的trie。任何人都知道文件支持的实施？我遇到Trie类似于我正在寻找的实现，但似乎没有错误。

Answer 1

如果你能排序你的文件包含字符串，然后阅读排序列表和计数重复将是容易的。 （您可以保留原始文件并创建一个新的排序字符串文件。）有效地排序大文件是旧技术。你应该能够找到一个实用程序。

如果你不能排序，那么考虑digesting的字符串。 MD5可能是为了你的目的而矫枉过正。你可以拼凑一些东西。对于数十亿字符串，您可以使用8个字节的摘要。使用摘要树（可能是BST）。对于每个摘要，存储产生该摘要的唯一字符串的文件偏移量。

当您读取一个字符串时，计算它的摘要并查找它。如果你没有找到摘要，你就知道这个字符串是唯一的。将它存储在树中。如果您找到摘要，请检查每个关联的字符串是否匹配并进行相应处理。

要比较字符串，您需要转到该文件，因为您存储的所有文件都是文件偏移量。

重要的是要记住，如果两个摘要不同，产生它们的字符串必须不同。如果摘要相同，字符串可能不一样，所以您需要检查。当重复字符串较少时，此算法效率更高。

Answer 2

你打算如何一次加载30GB的内存？而且，由于它是一种基于字典的行为，我想可以在每次插入或增量时加载整个文件（即便是逐件）以进行查找。

我建议使用数据库。这就是他们的目的......