如何估计 trie 树的大小？

Question

我有一个包含 62 位字母数字键的 trie，长度为 100B。我有 5 x 10 ^ 11 个键。我如何估计存储此 trie 需要多少 RAM / 磁盘 space？

Answer 1

使用简单的前缀树，space 要求应该是 O(N*C)，其中 C 是每个单词的平均字符数，N 是单词数。这是因为在最坏的情况下，Trie 将存储每个单词中的每个字符。

Answer 2

这将取决于您如何表示 trie 以及您执行的 space 节省优化。它还将取决于您存储的特定字符串。

对于初学者，请注意，如果您的 trie 树中包含 w 个单词，则您需要对该 trie 树进行编码的最少节点数是 w，一个节点代表您要存储的每个单词。我们将使用它作为编码 trie 所需的 space 的下限。

让我们从一个简单的 trie 表示策略开始。想象一下，每个节点都有以下形式：

struct Node {
    bool isWord;
    Node* children[62];
};

在 64 位系统上，这至少需要 8 × 62 大约每个节点 500 字节。假设你只需要存储 5 × 10¹¹ 个节点那么

5 × 10¹¹ × 500b = 250TB

这完全不切实际。

由于您有一个静态特里树，另一种选择是让每个节点存储一个固定大小的 character/pointer 对数组，如下所示：

struct Node;

struct Child {
    char letter;
    Node* child;
};

struct Node {
    uint8_t numChildren;
    Child children[]; // Flexible array member
};

由于您假设所有字符串都具有相同的长度，因此您可以识别哪些节点是单词，因为它们没有子节点。

现在，我们需要多少 space？在 64 位系统上，考虑到填充，每个 Node 将占用 8 个字节加上它的每个子项额外的 8 个字节。如果我们在 trie 中有 n 个节点，则对所有 trie 节点的所有子节点计数求和将得到 n - 1，因为除根节点之外的每个节点都是另一个节点的子节点。这给出了 16n 字节的 space 用法来保存 trie。存储 100 个字符长的 5×10¹¹ 字符串所需字节数的保守上限是我们需要 5×10¹³ 个节点，每个节点 16 个字节，净总数 800TB。那还是不切实际。

当然假设每个字符串都会增加100个新的节点是不合理的，会涉及到很多分享。但它仍然表明我们需要更多的压缩才能实现这一点。

这里的另一种选择是使用 Patricia trie。如果您之前没有看过 Patricia 的尝试，基本思路如下：

添加一个代表 "end of string," 的新字符，然后将该字符附加到每个字符串的末尾。惯例是使用 $ 表示该字符。
对于 trie 中只有一个子节点的每个节点，将该节点合并到其父节点中。这意味着 trie 边现在可以有多个字符。

例如，这里是字符串 "ant," "ante," "anteater," "antelope," 和 "antique":

的 Patricia trie

关于 Patricia 树有一个有用的定理：包含 w 个单词的 Patricia 树最多有 2w 个节点。（证明背后的基本思想是 Patricia trie 中不是叶子节点的每个节点都有多个子节点，因此内部节点的数量不能超过叶子的数量）。

我们可以用以下方式简洁地表示帕特里夏树。首先，将存储在 trie 中的所有字符串作为一个巨大的字符串一个接一个地写出。在上面的示例中，它可能看起来像这样：

ant$anteater$ante$antique$antelope$

然后，将每条边表示为一对整数，表示构成该边的字符的起点和终点的起点和终点。例如，上面 Patricia trie 中标记为 "ant" 的边可以编码为 [0, 2] 对。整体编码可能如下所示：

struct Node;

struct Child {
    size_t start;
    size_t end;
    Node* child;
};

struct Node {
    uint8_t numChildren;
    Child children[];
};

每条边需要 24 字节的存储空间。每个节点需要 8 个字节的存储空间。而且我们还必须记下所有字符串中的所有字符。这意味着 space 用法是

(space for all characters of the strings) + (space for all nodes) + (space for all edges)

= (100w bytes) + (16w bytes) + (24 w bytes)

= 140 w bytes

= 140 × 5 × 10¹¹ bytes

70TB.

情况正在好转，但还不够好。但是让我们看看我们是否可以减少一些 space.

首先，上面的计算假设我们将所有 2w 个节点存储在 trie 中。但是这些节点中有 w 是叶子，我们可以将它们编码为 Child struct 中的空指针。这将要编码的节点数减少了一半，给出了这个 space 用法：

(space for all characters of the strings) + (space for all nodes) + (space for all edges)

= (100w bytes) + (8w bytes) + (24 w bytes)

= 132 w bytes

= 132 × 5 × 10¹¹ bytes

66TB.

到目前为止最大的 space 问题是写出所有字符所需的 space。我们可以减少一点吗？

您提到您的字符串都是 100 个字符长，并且字符来自大小为 62 的字母表。添加空终止符可以得到 63 个可能的字符，因此我们可以用六位写出每个字符。这意味着我们不需要每个字符一个完整的字节；六位就足够了。这样就减少了我们的 space 用法，如下所示：

(space for all characters of the strings) + (space for all nodes) + (space for all edges)

= (75w bytes) + (8w bytes) + (24 w bytes)

= 107 w bytes

= 107 × 5 × 10¹¹ bytes

53.5TB.

现在，这假设我们按原样存储所有字符串，但这不一定是执行此操作的最佳方法。你只需要写出足够多的字符来确保每条边都有一些字符子范围指向。这可能会节省大量资金，但我不知道如何精确量化，因为这取决于所使用的特定字符串。我猜 (?) 你会减少一半的 space，剩下大约 30TB 的 space 需要。

总的来说，如果您将 Patricia trie 用于您的字符串，您可能会得到 30TB 的 space。一些更多的优化要看：

能否将索引从 64 位减少到 48 位？这可以为每条边节省一些 space，进一步降低成本。
能不能将压缩后的文本存储起来，然后根据需要解压？这可能会将事情进一步推低。

希望对您有所帮助！

如何估计 trie 树的大小？

How to estimate the size of a trie?

data-structures

trie

space-complexity

estimation