求助经典算法题:单词的频度统计
一篇英语文章,有没有什么好办法能够得到出现频度最高的10个单词?
貌似百度面试就有这个题目,请高人赐教!
请不要贴代码,说明算法的思想就可以了!希望分析时间效率和空间效率
[解决办法]
不是这个意思,其实真正这个题目的意思是
“给定一篇文章,找出最能表达这篇文章意思的10个单词”。这个是Information Retrieval领域的问题。
这里的出现频度并不是指简单的出现次数,而是最有意义的出现次数。也就是说,英文中'a'代表'一个'的意思,或者'the'代表'这个',这些单词出现在文章中的次数当然最多,但是不能表明这个文章的中心思想。
现在是如何提出中心思想的词,也就是说通过这些词,让没有看过这篇文章的人,也大概可以知道这篇文章是讲什么的。听起来这个问题好像听玄的。不过解决的方法非常多。
最简单的就是一个叫做TF-IDF的算法。这个在IR领域中已经相当成熟。
你可以google一下,可以找到大量的这样的文章。
对于中文的话,可能情况要复杂一些,主要是因为中文还需要分词后才能使用tf-idf算法。
[解决办法]
这个就更简单了,建立一个HASH表,查表。 O(n)算法。