查找出现次数最多的字词

搜索文档中出现次数最多的单词的最佳方式（算法）是什么？查找出现次数最多的字词

2011-09-24 Saket

发生什么事的最大次数？ – DeCaf

该文档中出现**字**的最大次数 – Saket

您是否正在查找文档中发生最多的单词？一个简单的直方图将在O（n）中实现。 – amit

查找有occures最次文档中的字可以在O（n）的一个简单histogram来完成[哈希基于]：

histogram <- new map<String,int> 
for each word in document: 
    if word in histogram: 
     histogram[word] <- histogram[word] + 1 
    else: 
     histogram[word] <- 1 
max <- 0 
maxWord<- "" 
for each word in histogram: 
    if histogram[word] > max: 
    max <- histogram[word] 
    maxWord <- word 
return maxWord

这是O（n）的溶液中，并且由于问题显然是Omega（n）问题，它在big O notation方面是最优的。

来源

2011-09-24 16:54:19 amit

无论如何，这是理想的预期情况。 –

A [特里结构（http://en.wikipedia.org/wiki/Trie）代替哈希映射给出确定性为O（n）的最坏情况，但是很可能是在实践中更慢。 – comco

扫描一次文档，记录您看过每个独特单词的次数（可能使用散列表或树来完成此操作）。
执行步骤1时，请跟踪目前为止所看到的所有单词中计数最高的单词。

来源

2011-09-24 16:51:55 NPE

查找出现次数最多的字词

回答

相关问题