搜索引擎相似度计算方法之arctan方法

firstboy05132014-03-24 17:56:11搜索引擎 / 搜索功能

搜索引擎相似度的计算有很多种方法,相似度是对搜索结果进行排序的一种方式,是指所输入的搜索关键字与搜索结果每一条记录之间的"相似程度",我们知道百度的竞价排名就是一种"有名"的相似度排名方法,这里使用arctan函数来计算不同次数相邻关键字的相似度计算,仅仅在于获取不同关键字出现次数以达到完全分隔在不同相似度等级分数的需求。在搜索引擎的设计与实现中,除了存储速度、数据量大小等硬性指标外,搜索引擎的相似度排名成为搜索引擎好坏的重要指标,虽然目前Google、Baidu等国内外搜索引擎企业的相似度排名算法没有实际公开,但一些搜索关键字得出的结果好坏可以直接看出来,附录中会继续调侃这些互联网通用搜索引擎的优劣之处。

从SEO的经验来看,这些互联网通用搜索引擎的相似度计算并不是很简单的构造,往往考量了很多个因素,还要反作弊等更多的处理。而在某些情况下的设计,比如企业搜索引擎,用户需要搜索的结果中,把相邻关键字命中的记录一定要排在没有相邻关键字命中的记录前面,也就是相似度要高于后者。

虽然这个要求对于互联网搜索来说是非常不正常的需求,正常的需求应该是要求相邻关键字命中的记录权重要高一些而已,并没有绝对性可言。但不妨考虑一下这样的需求,一些线性权重调整很容易因为一些无相邻关键字命中但词很多的情况下最终相似度分数超过相邻关键字的情况,所以单独靠经验值从理论上也是无法避免这样的情况发现的。为了达到这个绝对性,考虑到arctan函数曲线的特殊性,我们设计了如下阶梯型arctan函数来达到这种要求。

因为y=arctan(x)的值永远无法超过π/2,利用这个特性,我们设计了如果没有相邻关键字的情况下就使用y=arctan(x)函数来计算,具体x值可以取关键词在记录中出现次数为值;如果出现1次相邻则使用y=arctan(x)+π/2来计算,这样就可以达到出现1次相邻关键字的记录永远比没有出现相邻关键字的记录相似度值要大。出现更多次的相邻情况依此类推,如上图所示。

另外,在实现的过程中,参考如下代码来看,xvalue就是arctan(x)里面的x,在这里面,有多个相邻关键字的权重设计为单个关键字的5倍。而yvaluie表示连续相邻次数决定是否要加π/2的因子,所以整体相似度公式应该如下:

S_{similarity}=arctan(x_{xvalue})+y_{yvalue}*\pi /2

相关伪代码如下图所示,其中为了加入不同关键词判断,引入了bloomfilter,如下代码所示。

PRIVATE double eggCalc(HDOCOFFSETTABLE peggDoc, int len)
{
	// A Bloom filter is a space-efficient probabilistic data structure that is 
	// used to test whether an element is a member of a set. False positive 
	// retrieval results are possible, but false negatives are not.
	// Note that bloom size 2500 is an empirical value.
	_EGG_BLOOM *bloom;
	if (!(bloom=_egg_bloom_create(2500, 2, _egg_sax_hash, _egg_sdbm_hash)))
	{
		fprintf(stderr, "[ERROR] -- Could not create bloom filter!\n");
		return EXIT_FAILURE;
	}
	
	_egg_bloom_add(bloom, peggDoc[0].echKey);
	
	// Using the arctan function to calculate the similarity, which makes the 
	// adjacent more Keywords documentation scores higher scores than 
	// non-adjacent Keywords documentation. However Note, face level adjacent 
	// Keywords alone keywords ratio 5 is an empirical value.
	int _f_series = 0, _max_series = 0;
	double yvalue = .0, xvalue = 1.0;
	int _i = 0, _j = 0;
	for (_i = 0, _j = _i + 1; _j < len; _i ++, _j ++)
	{
		if (peggDoc[_i].echKey != peggDoc[_j].echKey 
			&& peggDoc[_i].off + 1 == peggDoc[_j].off 
			&& !_egg_bloom_check(bloom, peggDoc[_j].echKey) )
		{
			_egg_bloom_add(bloom, peggDoc[_j].echKey);
			if (_f_series >= _max_series)
			{
				yvalue += (M_PI/2);
				_max_series ++;
			}
			else
			{
				// the value of one pair of adjacent term weight compared to 
				// a single word.
				xvalue += 5;
			}
			_f_series ++;
		}
		else
		{
			xvalue ++;
			_f_series = 0;
		}
	}
	
	_egg_bloom_destroy(bloom);
	
	#ifdef _EGG_SIMILAR_SCORE_DEBUG_INFO
	printf("[INFO] -- yvalue + atan(xvalue) = %.1f (PI/2) + atan(%f)\n", 
		(yvalue/(M_PI/2)), xvalue);
	#endif // _EGG_SIMILAR_SCORE_DEBUG_INFO
	
	return (yvalue + atan(xvalue));
}

这个简单的方法只是简单粗暴地解决了上面这种绝对相似充排序的要求,其缺陷很多,下面罗列出若干条已知的缺陷:

  1. 搜索相似度在多不字段不同权重的计算情况目前不支持。
  2. 查询速度会慢一点点。
  3. 没有考虑搜索关键词的顺序的权重。
  4. 中间有空格或符号的时候,因为没有词而视为相临情况。
  5. 理论上会有极小概率导致排序不正确,这个概率有多小现在没实验数据。
  6. 另外,考虑命中关键字之间的距离因素需要赋予不同的权重也是很关键的。
  7. 没有考虑完全匹配的长度比部分匹配长度小的情况下权重不同,也就是内容越长,权重越小的因素。

下面我们看看三个不同搜索引擎对一个搜索结果的相似度排名质量进行不同评论一下,举个例子,我们来搜索“postmaster@aliyun.com”这个关键字,看看Google、Baidu、360三个搜索引擎的搜索结果。

1. Google 搜索结果

2. Baidu搜索结果

3. 360搜索结果

从上面的搜索结果来看,360的比较“极品”,出来的结果有540,是这三个搜索结果数最多的一个了。不过仔细认真一看,发现有同一个页面出来N个抓取结果,去看了这个页面:http://bbs.aliyun.com/read.php?tid=118237。360人为地加上了fpage的参数,然后抓取了N次,所以导致这样的结果,还真不能赶鸭子上架,不过360做的时间来看,已经不错了。

百度的排名还是相当有问题的,这里面的搜索结果为什么第二条有相邻的关键字却没有排在第一条无相邻关键字前面呢,这就导致结果不好了。爬虫抓取下来的数据量还是不够全,全而准,是这搜索引擎的必杀技呀。国内这方面其实还是有提高的空间,所以发展的并不止境,大企业也不要太懒散有点小优越感就太高傲了。不过百度的中文搜索方面在国内还是很有用的。

Google相对来说还好一点,不过提到“活在未来”的很多需求,Google也是不完善的,不过它已经解决了基础的搜索,至少能让专业人士使用解决一些基础问题了。

文章评论
比咕搜索引擎定制与数据分析技术服务
最新评论
比咕网移动端APP下载

iPhone、Android 手机
扫描二维码下载安装

(可以使用QQ,微博等的扫描二维码功能)