c++ - 文件支持的 Trie（或前缀树）实现

Question

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

在这种情况下，我还遇到了比 map 更快的 trie。有人知道文件支持的 trie 实现吗？我遇到了一个类似于我正在寻找的Trie实现，但似乎不是没有错误的..

Answer 1

您如何一次将 30GB 加载到内存中？而且由于它是您想要的基于字典的行为，我想每次您插入或增加时，您都需要加载整个文件（即使是一块一块地）以进行查找。

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

Answer 2

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

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

当你读取一个字符串时，计算它的摘要，然后查找它。如果您没有找到摘要，您就知道该字符串是唯一的。把它存放在树上。如果您确实找到了摘要，请检查每个关联的字符串是否匹配并相应地处理。

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

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