如何估计一个trie的大小?

对于初学者,请注意,如果您有一个trie,其中包含w个单词,那么您需要编码该trie的最小节点数为w,存储的每个单词对应一个节点。我们要用它作为编码trie所需空间的下限。

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

在64位系统上,每个节点至少需要8×62约500字节。假设你只需要储存5×10 然后是节点

5 × 10 ¹¹ ×500b= 250兆字节

这是完全不切实际的。

struct Node;

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

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

因为假设所有字符串的长度都相同,所以可以确定哪些节点是单词,因为它们没有子节点。

现在,我们需要多少空间?在64位系统上,考虑到填充,每个 Node ^{11 13} 每个节点有16个字节,总计为 800兆字节

当然,假设每个字符串将导致添加100个新节点是不合理的,而且会涉及到大量的共享。但它仍然表明,我们需要更多的压缩,使之可行。

另一种选择是使用帕特里夏提尔。如果你以前没见过帕特里夏尝试过,基本思路如下:

1. 添加一个表示“字符串结尾”的新字符,然后将该字符固定到每个字符串的结尾。惯例是用$来表示那个字符。

2. 对于trie中只有一个子节点的每个节点,将该节点合并到其父节点中。这意味着trie边现在可以有多个字符。

举个例子,这里有一个Patricia trie,代表字符串“ant”、“ante”、“anteater”、“antelope”和“antic”:

关于Patricia tries有一个有用的定理:一个Patricia trie持有w个单词,最多有2w个节点。(证明背后的基本思想是Patricia trie中的每个节点(不是叶子节点)都有多个子节点,因此内部节点的数量不能超过叶子的数量)。

我们可以用下面的方式紧凑地表示Patricia trie。首先,把存储在trie中的所有字符串一个接一个地写成一个巨大的字符串。在上面的例子中,可能是这样的:

蚂蚁$羚羊$羚羊$古董$羚羊$

然后,将每条边表示为一对整数,表示组成该边的字符的起点和终点的起点和终点。例如,上述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字节的存储空间。我们还要写下所有字符串中的所有字符。这意味着空间使用是

(字符串的所有字符的空格)+(所有节点的空格)+(所有边的空格)

=140 w字节

¹¹ 字节

70 TB .

这是越来越好,但它仍然不是很好。但是让我们看看能不能减少一些空间。

首先,上面的计算假设我们在trie中存储所有2w节点。但是这些节点中的w是叶子,我们可以在 Child struct

(字符串的所有字符的空格)+(所有节点的空格)+(所有边的空格)

=132 w字节

= 132 × 5 × 10 ¹¹ 字节

66兆字节 .

您提到您的字符串都有100个字符长,并且都是从大小为62的字母表中提取的字符。加上空终止符可以得到63个可能的字符,所以我们可以把每个字符写成6位。这意味着我们不需要每个字符有一个完整的字节;6位就足够了。这样就减少了我们的空间使用:

=(75w字节)+(8w字节)+(24W字节)

=107 w字节

= 107 × 5 × 10 ¹¹ 字节

53.5兆字节

现在,假设我们按原样存储所有字符串,但这不一定是最好的方法。您只需要写出足够的字符,以确保每个边都有一些字符的子范围指向。这可能是一个巨大的节省,但我不知道如何精确地量化它,因为它将取决于所使用的特定字符串。我猜(?)你会把一半的空间都砍掉 所需的空间。

所以总的来说,如果你使用Patricia trie作为你的字符串,你可能会得到30TB的空间。需要进一步优化:

2. 你能把文本压缩后储存起来,然后根据需要解压吗?这可能会把事情推得更远。

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