给定一组单词，如何计算 trie 中的节点数

Question

想知道是否有通用算法或技术来计算 trie 中有多少节点（以及多少字节）。

假设有一个这样开始的 trie：

   a        t
   p        h
e  p        e  i
   l  s  r  i  s
   e     e  r

ape
apps
apple
the
their
there
this

然后想象有一个包含数千个单词的大词典。每个单词由字母表 A 中的一组字母 L 组成。所以基本上我们可以生成 n 个 L 的（单词），比如说 100,000 个，不同的长度。它们在某些情况下会重叠，因此它在最终 trie 中占用的字节数不会只是 100,000 x（平均长度）之类的东西。相反，它将是总数的一小部分。

我想知道如何计算这个。如果您需要实际生成数据然后对其进行测量，或者是否有一种数学技术可以快速对其进行近似建模。

Answer 1

我认为输入数据的变化可能太大，因此您必须扫描它才能得出答案。如果您可以先对输入数据进行排序，您实际上不必构造尝试：给定排序后的输入，您只需计算扫描的每一行中最后一个公共字母的新字母。只需记住最后一个字符串，无需任何分配，一次扫描即可找到正确答案。

以您为例，处理排序后的列表：

1. "ape" - 三个新字母
2. "apps" - 走回普通'p'，然后两个新字母= 5 so far
3. "apple" - 回到第二个 'p' 这是最后一个普通字母，然后两个新字母 = 7
4. "the" - 没有共性所以回到开头和三个字母 = 10
5. "their" - 两个新字母 = 12
6. "there" - 背二，二新=14
7. "this"-后三，二新=16

这与你的图相匹配，它有 16 个节点。