如何估计特里的大小？

Question

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

Answer 1

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