从百万关键字中提取前K个关键字

标签: 百万 关键字 关键字 | 发表时间:2014-03-22 17:51 | 作者:mxway
出处:http://blog.csdn.net

转f载请注明出处:http://blog.csdn.net/mxway/article/details/21776727

      在搜索引擎中经常需要对最近一段时间关键字的搜索次数进行统计,并找出搜索次数最多的前K个关键字。在上一篇文章中我们分析了用stl map及使用字典树进行统计的优缺点。对随机生成的100万个关键字进行统计后,还剩大概70万个关键字;也就是有大约30万的关键字与其它重复。下面就讨论几种方法来实现从70万个单词中找出“搜索次数”最高的K个单词。无论使用上篇文章中的哪种方法进行统计,其最后的结果都是以字母表(a-z)的顺序输出到文件中;但是出现的次数却不是有序排列的。

      方法一、用数组开辟N个空间,将关键字存储到这N个空间中用选择排序的方法,进行N*K次比较就可以将出现次数最多的K个关键字存储到数组的将K个单元中;时间复杂度为O(K*N)。也可以使用快速排序对N个关键字进行全排序;其时间复杂度为O(NlgN)。

     方法二、使用最小堆实现,最小堆的思想是,一边从外部文件中读取,一边将读取到的关键字个数与最小堆的堆顶关键字个数进行比较;如果堆的元素大于读取到的那个单词,那么刚从文件中读到的那个关键字就不需要加入到堆中;如果刚读到的那个关键字次数大于堆顶元素,将堆顶元素直接用刚读到的那个关键字替换,并进行堆的下移操作。在这我们并没有使用最大堆来实现;因为使用最大堆不好控制关键字什么时候加入到堆中。

首先定义一个结构体用于存放关键字及其出现次数

struct Node{
	string word;//存储关键字
	int    cnt;//存储关键字出现次数
};

使用最小堆可以实现边读取边比较,不需要额外的空间。而在K个元素的最小堆中进行下移操作其时间复杂度为O(lgK),要在N个关键字中找出前K个关键字其时间复杂度为O(NlgK)。空间复杂度为O(K)。

当文件中的所有关键字读取完后,最小堆中的K个元素就是搜索次数最多的K个关键字。如果需要对关键字按出现次数从高到低进行输出,只需要另外申请K个空间就可以将关键字按出现次数从高到低进行输出。下面给出最小堆实现的C++源码。

#include<iostream>
#include<fstream>
#include<ctime>
#include<string>
using namespace std;

//找出单词出现次数最多的前K个单词
const int K = 10;
struct Node{
	string word;//存储关键字
	int    cnt;//存储关键字出现次数
	bool operator <(const struct Node &b)
	{
		return cnt < b.cnt;
	}
	void operator=(const struct Node &b)
	{
		word = b.word;
		cnt  = b.cnt;
	}
};

struct Node data[K];

/*
*
*初始化堆中的数据
*
*/
void Init()
{
	int i;
	for(i=0; i<K; i++)
	{
		data[i].cnt = 0;
	}
}

/*
*
* 将数据插入到最小堆中。
*
*/
void InsertData(Node &elem, const int MAXNum)
{
	int pos = 0;
	int cur = 2*pos+1;
	while(cur < MAXNum)
	{
		if(cur < MAXNum-1 && (data[cur+1] < data[cur]) )//找到两个子树中较小的那个节点。
		{
			//右子树较小
			cur++ ;
		}
		if(elem < data[cur])break;//不需要再移动数据了。
		else
		{
			data[pos] = data[cur];
			pos = cur;
			cur = 2*pos+1;//先指向左子树
		}
	}
	data[pos] = elem;
}

/*
*
* 按单词出现次数的从小到大输出单词.
*
*/
void outPutWord()
{
	int i;
	for(i=0; i<K; i++)
	{
		cout<<data[0].word<<" "<<data[0].cnt<<endl;//堆顶的元素一定是最小的元素。
		//将堆顶元素用最后一个元素覆盖。然后将堆顶元素向下调整。
		Node temp = data[K-i-1];
		//将最后一个元素删除,然后将最后一个元素重新加入到堆中。
		InsertData(temp, K-i-1);//元素减少了1个
	}
}

int main()
{
	struct Node tempNode;
	clock_t start,end;
	ifstream in("result.dat");
	Init();
	start = clock();
	while(in>>tempNode.word>>tempNode.cnt)
	{
		if(data[0] < tempNode)//堆顶的单词出现次数小于现在单词出现的次数
		{//单词出现次数小于堆顶的不需要考虑了。
			InsertData(tempNode,K);
		}
	}
	end = clock();
	cout<<"找前K个关键字的时间:"<<end-start<<"毫秒"<<endl;
	//输出前K个关键字
	outPutWord();
	return 0;
}
运行结果:

作者:mxway 发表于2014-3-22 9:51:38 原文链接
阅读:11 评论:0 查看评论

相关 [百万 关键字 关键字] 推荐:

从百万关键字中提取前K个关键字

- - CSDN博客推荐文章
转f载请注明出处:http://blog.csdn.net/mxway/article/details/21776727.       在搜索引擎中经常需要对最近一段时间关键字的搜索次数进行统计,并找出搜索次数最多的前K个关键字. 在上一篇文章中我们分析了用stl map及使用字典树进行统计的优缺点.

Google疑遭关键字屏蔽

- 深深浅浅 - 月光博客
  今天下午7时左右,大量网友反馈Google无法访问,我在深圳电信实地测试,验证Google全系列网站均无法访问.   经分析,google.com的域名已经被加入黑名单,疑似遭到关键字屏蔽,导致全部Google.com下的网站都无法访问. 从yahoo,flickr等网站搜索Google域名均会显示连接被重置.

正确理解javascript的this关键字

- BeerBubble - 三水清
javascript有this关键字,this跟javascript的执行上下文密切相关,很多前端开发工程师至今对this关键字还是模棱两可,本文将结合代码讲解下javascript的this关键字. 定义了一个person对象,对象中包含了name、gender属性,还包括了一个getName的方法,其作用是输出person对象的name.

Lucene5学习之Suggest关键字提示

- - 编程语言 - ITeye博客
         首先需要搞清楚Suggest模块是用来解决什么问题的. Google我想大家都用过,当我们在搜索输入框里输入搜索关键字的时候,紧贴着输入框下方会弹出一个提示框,提示框里会列出Top N个包含当前用户输入的搜索关键字的搜索热词,如图:. 在Lucene中,这种搜索关键字自动提示功能是由Suggest模块提供的.

在 Google Reader 中高亮显示你关注的关键字

- Krevy - 谷奥——探寻谷歌的奥秘
如果你关注某个品牌或者是个人的博客声望,你可能希望通过Google订阅之后,知道都有哪些新闻或者是文章提到了你. 之前我们在搜索了一通之后,可能没有办法一眼看出这些结果中和我们关注的关键字相关的选项,现在好了,新的工具来鸟:Google Reader Filter. Google Reader Filter是一个很实用的产品,是Javascript的客户端代码,它可以高亮显示你订阅的并且关心的项目.

高效的关键字过滤及查找算法

- kongshanzhanglao - 博客园-首页原创精华区
最近做游戏服务器需要使用到关键字查找和过滤的功能. 首先想到的是使用HashSet 的方式..         int m_maxLen=8; //关键字最大长度.         /// 插入新的Key.         /// 检查是否包含非法字符.         /// 找到的第1个非法字符.没有则返回string.Empty.

Java线程同步中关键字synchronized详述

- - 编程语言 - ITeye博客
synchronized关键可以修饰函数、函数内语句. 无论它加上方法还是对象上,它取得的锁都是对象,而不是把一段代码或是函数当作锁. 1,当两个并发线程访问同一个对象object中的这个synchronized(this)同步代码块时,一段时间只能有一个线程得到执行,而另一个线程只有等当前线程执行完以后才能执行这块代码.

Java 慎用方法级别的synchronized关键字

- - 编程语言 - ITeye博客
为什么要这么说呢, 因为笔者被这个坑过(其实是自己坑自己)╮(╯_╰)╭. 先看一段synchronized 的详解:. synchronized 是 java语言的关键字,当它用来修饰一个方法或者一个代码块的时候,能够保证在同一时刻最多只有一个线程执行该段代码. 一、当两个并发线程访问同一个对象object中的这个synchronized(this)同步代码块时,一个时间内只能有一个线程得到执行.

为 Google+ 按照关键字过滤信息流的 Chrome 扩展 Stream Filter

- 安得米 - 谷奥——探寻谷歌的奥秘
随着Google+的流行,你可能发现自己的timeline越来越混乱了,但又不忍心丢掉那些圈养的好友,怎么办呢. 你可以选择Stream Filter这枚Chrome扩展,它可以帮助你设置设置关键字. 比如有人老是爱发点阿猫阿狗的萌图,非常无聊,但为了不错过此人的重要言论,你可以针对这个特点加入“猫”和“狗”的关键字,这样整个世界就清净了.