c++ - 来自文本的字数统计..是否可以使用 trie？

Question

我知道字数统计问题已被问过很多次，而 MAP 似乎是一致的选择。

但我觉得如果文本很大并且唯一单词的数量非常多，MAP 可能会占用很多空间。那么为什么不使用 Trie 树呢？叶节点将存储每个单词的频率。

或者与 trie 相比，Map 明显更胜一筹？

请帮助我理解。

附言SDE面试时问到的。

Answer 1

来自 here我们可以估计英语中的单词约为 1M。来自 here我们得到了 map 内存使用的公式。现在我们可以计算出，如果你的文本都是该语言的单词，你的 map 将占用大约(平均单词长度 6 个字符)(32 字节短字符串(Windows)+ 4 字节 int)* 1M +(可忽略的开销)= 36M ~ 34MB 内存。

所以我想说，除非您使用的是嵌入式系统，否则您无需担心。