设计一个算法，找到书中最常用的单词

Question

面试问题：

找出书中最常用的单词。

我的想法：

使用哈希表，遍历并标记哈希表。

如果已知书本的大小，如果发现有使用过的单词> 50%，则在接下来的遍历中跳过任何新单词，只计算旧单词。如果书籍尺寸未知怎么办？

时间和空间都是O(n)和O(n)。

还有更好的想法吗？

谢谢

Answer 1

为了确定复杂性，我认为您需要考虑两个变量，n = 单词总数，m = 唯一单词数。我想最好的情况复杂度将接近 O(n log(m)) 的速度和 O(m) 的存储，假设每次迭代 n 个单词中的每一个，并基于哈希表构建和搜索或最终包含 m 个元素的其他此类结构。

Answer 2

这实际上是map reduce的经典示例。

维基百科页面中的示例将为您提供每个唯一单词的字数，但是您可以轻松地在减少步骤中添加一个步骤来跟踪当前最常见的单词（使用某种互斥体来处理并发问题）。

如果您有分布式机器集群或高度并行化的计算机，这将比使用哈希表运行得快得多。

Answer 3

通常，当我们必须确定诸如最/最少使用。

甚至 Python;s Counter.nlargest 这是用于这些目的是通过堆数据结构实现的。

二叉堆数据结构具有以下复杂性

CreateHeap - O(1)
FindMin - O(1)
deleteMin - O(logn)
Insert - O(logn)

我对哈希（使用Python中的默认字典）和堆（使用Python中的Collections.Counter.nlargest）进行了比较，哈希比堆稍好一些。

>>> stmt1="""
import collections, random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
somehash=collections.defaultdict(int)
for d in somedata:
    somehash[d]+=1
maxkey=0
for k,v in somehash.items():
    if somehash[maxkey] > v:
        maxkey=k
"""
>>> stmt2="""
import collections,random
somedata=[random.randint(1,1000) for i in xrange(1,10000)]
collections.Counter(somedata).most_common(1)
"""
>>> t1=timeit.Timer(stmt=stmt1)
>>> t2=timeit.Timer(stmt=stmt2)
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=10)/10)
38168.96 usec/pass
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=10)/10)
33600.80 usec/pass

Answer 4

您的优化有一个概括 - 如果书籍大小已知并且您看到的任何单词的计数 >剩余单词数 + 次高计数，当前计数最高的单词就是答案。

Answer 5

从实际的角度来看，您的解决方案是正确的、快速的，并且可能是最好/最简单的。

其他发帖者的解决方案的时间复杂度比您的解决方案更差。对于您正在使用的哈希，时间复杂度确实是 O(n)。每次插入的时间复杂度为 O(1)，并且有 n 个单词，因此插入阶段的成本为 O(n)。迭代并找到最大值则为 O(n)。正如你提到的，空间也是 O(n) 。

请注意，您将无法使用 Chris 的解决方案提前终止算法，因为搜索哈希表的成本很高，并且您无法在每次插入后在 O(1) 时间内执行此操作。

堆会花费更多的时间，因为您需要在每次插入期间维护堆。堆插入的时间复杂度为 O(log(n))，因此插入的总成本将为 O(nlog(n))。

Answer 6

如果您正在看一本书，那么您就知道其中的词汇和大概的词频。即使您没有预先获得此信息，您也可以通过扫描随机样本来获得良好的估计。

对于确切的答案，我将使用 k 个最常见单词的完美哈希函数。完美的哈希函数需要 O(k) 内存并保证最坏情况下的快速 O(1) 查找。

对于不常见的单词，我会使用作为堆或自平衡树实现的优先级队列。常规哈希表也可能是一个不错的选择。