包含所有英文单词的前缀树（Trie）有多大？

Question

了解英语词典中有大约20万个单词，而字母表只有26个字母左右。

- Raul

---

你的估计有点低。根据牛津词典网站，英语单词至少有25万个，这还不包括字典没有收录的技术词汇。 - Jim Mischel

Answer 1

在这篇文章中，作者从一个约有935,015字节长的文件中构建了一个英语单词的Trie。它需要25万个节点。他声称压缩比约为73％，这与我在使用这些数据结构时记得的非常接近。

请注意，他的实现浪费了很多内存，因为对于每个节点，它都存储了26个子指针的数组。更便宜的实现方法将维护仅需要的指针，按使用频率排序。例如，对于单词中的字符q来说，存储26个子节点指针是有点疯狂的，因为在q之后的字符几乎不可能是除了u以外的其他字符。

顺序搜索需要的时间略长于直接索引数组，但它可以节省大量内存。内存的节约可以导致较少的缓存未命中，这可能完全弥补线性搜索的成本增加。

如果你想节省更多的空间，可以创建一个有向无环单词图(Directed Acyclic Word Graph)，它还利用了常见的单词结束方式以及其他一些优化方式。例如，可以将悬挂的结束压缩到一个单独的节点中。

- Jim Mischel

Answer 2

使用简单的前缀树，空间要求应为 O(N*C)，其中 C 是每个单词平均字符数，N 是单词数量。这是因为在最坏情况下，Trie 将存储每个单词中的每个字符。因此，公平的估计值应该在存储大约100万个字符左右，或者大约1MB左右。

- Nuclearman

---

你有这方面的参考资料吗？一个包含600,000个英文单词的trie树将存储比600,000个节点少得多。我所知道的任何trie树都不会为单词“cat”存储“c”，“ca”和“cat”。我认为你需要了解一下trie树是什么以及它是如何存储的。http://en.wikipedia.org/wiki/Trie - Jim Mischel

足够正确，我在考虑一种更复杂的数据结构，用于子字符串搜索，它基于 Trie。尽管如此，现在我想起来，那也可能是 O(NC)。在这种情况下，它只有在 C 是平均字符数且很高时才为 O(NC)。 - Nuclearman

是的。(N*C) 是最坏情况，只有在没有共同前缀的情况下才会发生。 - Jim Mischel

鉴于平均字符数是恒定的，字符和单词的数量都是O(N)。所以我知道你的意思，即使我没有捕捉到错误。我大致看了两遍600,000，浏览了你的答案，并转到你提供的链接上进行更详细的审查。 - Nuclearman

考虑以下实现 http://goo.gl/J5i2brTrie中的链接数量在CN和CNk之间，其中k是平均键长度。 Trie中的每个键都有一个包含其关联值的节点，该节点还具有L个链接，因此链接数量至少为LN。如果所有键的第一个字符都不同，则对于每个键字符都有一个具有L个链接的节点，因此链接数量为L乘以总键字符数，即LNk。 - Raul

Answer 3

Wolfram Alpha 表示，单词的平均长度为 5.1 个字符 http://www.wolframalpha.com/input/?i=average+english+word+length

如果 L=26，字母表中的字母数目， 而 K=5.1，则英语单词的平均长度

=> 我预计空间复杂度大约在 O(L^K) 左右 (L 的 K 次方)

实际语言中的实现可能会有所不同，我想。

- Raul

---

你的估计似乎没有根据。L^K 是由 L 个符号组成的所有 K 长度字符串的数量，也就是它可能估计的唯一相关数字是单词的数量，但这已经给出了，这不是我们要找到的数量。此外，即使是在这个目的上，它也是错误的，无论是在理论上（它计算了所有可能的与平均英语单词长度相同的字符串，但大多数并不是英语单词，许多英语单词长度不同），还是在实践中（它给出的是约 88 亿而不是 20 万）。 - user395760

除了@delnan所反对的内容，L^k的数量假设没有共同的前缀。前缀树的整个意义在于利用共同的前缀。快速搜索显示实证结果范围在(N*K)/4到(N*K)/3个节点之间，其中N是单词数量，K是单词的平均长度。 - Jim Mischel