搜索引擎,对很多人来说,熟悉又陌生。熟悉,是因为每个人每天都能接触到,比如百度、google、淘宝内部搜索;陌生,是因为鲜有人了解他的原理。
因为工作需要,有幸参与负责了一个站内搜索的项目。所以可以从实现的角度来讲讲怎么去实现一个站内检索系统。
1、为什么要使用检索系统
可能有些人会这么想,站内搜索我直接用数据库的like就可以实现。这种想法其实在实际中不太可行。首先,like语句很可能用不到搜索,因此性能低下;其次,like语句只能做比较精确的比配,相关性比较低下。比如,"我在北京玩的很好"这句话,如果你用"北京市"去搜索,肯定搜不出来,用帝都也是搜索不出来的,但是,实际上"北京市"和"帝都"以及"北京"都是一个意思;最后,站内检索系统可以做非常复杂的rank、打散以及屏蔽策略。
综上,正确认识一个检索系统是非常重要的。
2、实现最简单的检索系统
基于此,现在给大家来讲诉怎么快速搭建一个检索系统。
2.1、准备材料。
我们现在有3篇文本
D0: "it is what it is" D1: "what is it" D2: "it is a banana"
2.2、整理分析文本
搜索引擎整理信息的过程称为“创建索引”,常见的索引数据结构可以有多种,比如kd-tree等,我个人认为用的最多的数据结构当属倒排索引(Inverted_index)。
2.2.1 倒排索引的概念
倒排索引,也常被称为反向索引、置入档案或反向档案,是一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构(来自于wiki)。
2.2.2 实现倒排索引
现在去实现2.1里面的倒排索引,可以看出a 在D2里面出现过,banana也在D2中出现过,is和it在D0、D1、D2都出现过,what在D0和D1出现过。所以索数据如下:
"a": {2} "banana": {2} "is": {0, 1, 2} "it": {0, 1, 2} "what": {0, 1}
2.3 搜索
-
检索query为 "what is it",找到全部出现这些单词的文本(不考虑次序)
-
拉链:what为{0,1}, "is"为{0,1,2}, "it"为{0,1,2};
-
归并:为{0,1},也就是D0和D1
3、额外的考虑
3.1、相关性的考虑
任何一个搜索引擎都必须考虑相关性。
比如现在文本对象是oschina的一篇博客。那么在标题或者摘要的词语肯定比在内容中出现的更相关。比如这篇文章中标题有"搜索"关键字,而博客内容中有很多"相关性",很明显这篇文章"搜索"关键字要比"相关性"更相关。
现在,我们可以发现这篇文章出现很多"出现"这个词语,"相关性"这个词语则相对较少,相对这篇文章,哪个更相关呢。"出现"显然比"相关性"出现次数要多。但是我们不能认为"出现"比"相关性"更相关(这篇文章至少还有一段是描写相关性的)。这时候需要借助一个模型:tf-idf模型(这个模型有很多变种名字)。简要介绍下,tf(词频.term frequency)为指的是某一个给定的词语在该文件中出现的频率, idf(逆向文件频率,inverse document frequency)为一个词语的重要性。明显"出现的"idf要远小于"相关性",所以可以用 tf * idf来表明一个词语的相关性。那么"相关性"比"出现"更相关。
那么考虑这个case,2篇文章,一篇中有20个字,里面有5个"北京",另外一篇有10000字,出现8个"北京",那么这2个哪个更相关呢。按照tf-idf,明显是第二个更好,但是实际上第一篇更相关。这种case可以考虑相对词频,第一个tf=5/20,第二个为8/10000。
最后需要考虑一些特殊case,比如同义词的case,比如"北京"和"北京市"和"帝都"说的都是北京,需要放在一起考虑。一篇文章出现了"帝都",理论上它和"北京"也是相关的。
其他case都在后文讲诉。
3.2 召回率与准确率考虑
什么是召回率和准确率呢,下面举个例子。假设1个query结果如下:
相关 | 不相干 | |
召回数目 | A | B |
未召回数目 | C | D |
那么召回率为 A/(A+C),即正确召回相关的数目除以所有相关的数目。
准确率为 A/(A+B),即正确召回的数目所以所有召回的数目。
召回率和准确率是一对天敌。扩大召回最好的办法是全部召回,扩大准确率最好的方法是一个都不召回。
所以需要我们在召回和准确上做好一个评估。
3.3 rank
排序是搜索引擎必须关注的点,降价排名,人工干预大部分做的就是这部分。大家挤破头都像排名更加考前。对于搜索引擎而言。这部分设计策略太多。但是如果仅仅是站内检索,我们相对而言就简单很多。比如我们提前将文本标注好属性,打好分。比如文章1字数多,文章优秀,给100分;文章2文章 凑合,只能给50分。那么当拉链有文章1和文章2时候,文章1排在前面就好。
rank策略很多,在以后的文章中会叙述。在这仅仅叙述一个时效性。
3.4、时效性的考虑
对于2篇博客,2个加权差不多,1篇是14年的,1篇是10年的。显然,出14年的则更加好。那么则需要加入一个时效性的权重。这个时候,问题又出现了,我新写了一篇文章,可能非常烂,但是因为时效性加权比较高导致rank比较高,这种case也属于badcase。因此需要时效性加权做一些策略,保证在正常rank的情况下使用时效性加权。
3.5 筛选
搜索的结果必须可以排序,比如按照时间排序等等。这个时候可以借助资源的熟悉进行排序。在以后会讲到,这个地方就不再讲了。
3.6、打散
当我们同时有几家资源就可能需要打散了,比如做百度团购检索,团购接入了美团、糯米、去哪等多家团购资源,不能因为美团资源好全面都全部出美团的,这样不科学,所以需要有打散策略。
3.7、人工干预
再好的检索系统都会有badcase,所以肯定需要人工干预,比如加很名单等等,所以一个优秀的检索系统肯定得支持人工干预。