查找文档中每个单词的数量？

Question

我在一次面试中被问到这个问题。面试官告诉我，假设存在一个函数--比如getNextWord() --返回给定文档中的下一个单词。我的任务是设计一个数据结构来实现这个任务，并给出一个算法来构造一个包含所有单词及其频率的列表。

作为一个C++背景，我的回答是创建一个multimap of string，然后插入其中的所有单词，然后显示它的count。不过，后来有人告诉我，要以一种更通用的方式来做这件事。泛泛而谈，他的意思是他不想让我使用库功能。另外，我想multimap在内部是作为2-3树实现的，所以要使multimap解决方案成为通用的，我还需要对2-3树进行编码。

虽然我确实想到了尝试，但在面试中实施一项对我来说是不可能的。所以，我只想知道是否有更好的方法来实现它？或者是否有一种方法可以使用尝试以平滑的方式实现它？

Answer 1

在这里，任何基于直方图的算法都是有效的和通用的。这个想法很简单:根据数据构建一个直方图。直方图的通用接口是一个Map<String,Integer> ()

迭代文档一次(使用nextDoc()方法)，同时维护直方图。

就大O符号而言，这个接口的最佳实现可能是使用一个 trie，并且在每个叶节点中添加发生计数器。

从trie中获取实际的(word,number)对将由trie上的一个简单的DFS完成。

此解决方案为您提供了O(n * |S|)时间复杂度，其中，x_s_s是字符串的平均大小。

每个单词的插入算法：

每次添加一个新单词时:检查它是否已经存在，如果已经存在--增加计数器，否则--将该单词添加到计数器值为1的字典中。

Answer 2

我会尝试实现一个B-树 (或smth非常类似)来存储所有的单词。因此，我可以很容易地找到下一个单词，如果已经有了它并在节点中增加关联计数器。或者只是插入一个新的。

在这种情况下，时间的复杂性应该是：O(nlogn)，n是所有单词的计数，而logn是这样的树。

Answer 3

我认为最简单的解决方案是一个特瑞。在这种情况下，O(N)是给出的(用于插入和获取计数)。只需将计数存储在每个节点的附加空间中即可。

基本上，树中的每个节点包含到26个可能的子节点的26个链接(每个字母一个)+一个计数器(对于在当前节点中终止的单词)。只需查看链接，以获得一个trie的图形图像。