输入:正整数K和大文本.实际上,文本可以被视为单词序列.因此,我们不必担心如何将其分解为单词序列.
输出:文本中最常见的K字.
我的想法是这样的.
使用哈希表来记录所有单词的频率,同时遍历整个单词序列.在此阶段,键是"字",值是"字频".这需要O(n)时间.
对(字,字 - 频率)对进行排序; 关键是"字频".这需要使用正常排序算法的O(n*lg(n))时间.
排序后,我们只取第一个K字.这需要O(K)时间.
总而言之,总时间是O(n + n lg(n)+ K),因为K肯定小于N,所以它实际上是O(n lg(n)).
我们可以改善这一点.实际上,我们只想要前K个词.换句话说,频率对我们来说并不重要.因此,我们可以使用"部分堆排序".对于步骤2)和3),我们不仅仅进行排序.相反,我们改变它
2')构建一堆(word,word-frequency)对,以"word-frequency"为关键.构建堆需要花费O(n)时间;
3')从堆中提取前K个单词.每次提取为O(lg(n)).所以,总时间是O(k*lg(n)).
总而言之,该解决方案花费时间O(n + k*lg(n)).
这只是我的想法.我还没有找到改进步骤1)的方法.
我希望一些信息检索专家可以更多地了解这个问题.
我有许多网页访问日志文件,其中每次访问都与用户ID和时间戳相关联.我需要确定最受欢迎(即最常访问)的三页序列.日志文件太大,无法立即保存在主内存中.
示例日志文件:
User ID Page ID
A 1
A 2
A 3
B 2
B 3
C 1
B 4
A 4
相应的结果:
答:1-2-3,2-3-4
B:2-3-4
2-3-4是最受欢迎的三页序列
我的想法是使用两个哈希表.用户ID的第一个哈希并存储其序列; 第二个散列三页序列并存储每个序列出现的次数.这需要O(n)空间和O(n)时间.
但是,由于我必须使用两个哈希表,因此内存不能同时保存所有内容,而且我必须使用磁盘.经常访问磁盘效率不高.
我怎么能做得更好？