搜索词算法
A. 搜索引擎的排序算法都有哪些是怎么实现的
2.1基于词频统计——词位置加权的搜索引擎
利用关键词在文档中出现的频率和位置排序是搜索引擎最早期排序的主要思想，其技术发展也最为成熟，是第一阶段搜索引擎的主要排序技术，应用非常广泛，至今仍是许多搜索引擎的核心排序技术。其基本原理是：关键词在文档中词频越高，出现的位置越重要，则被认为和检索词的相关性越好。
1）词频统计
文档的词频是指查询关键词在文档中出现的频率。查询关键词词频在文档中出现的频率越高，其相关度越大。但当关键词为常用词时，使其对相关性判断的意义非常小。TF/IDF很好的解决了这个问题。TF/IDF算法被认为是信息检索中最重要的发明。TF（Term Frequency）：单文本词汇频率，用关键词的次数除以网页的总字数，其商称为“关键词的频率”。IDF（Inverse Document Frequency）：逆文本频率指数，其原理是，一个关键词在N个网页中出现过，那么N越大，此关键词的权重越小，反之亦然。当关键词为常用词时，其权重极小，从而解决词频统计的缺陷。
2）词位置加权
在搜索引擎中，主要针对网页进行词位置加权。所以，页面版式信息的分析至关重要。通过对检索关键词在Web页面中不同位置和版式，给予不同的权值，从而根据权值来确定所搜索结果与检索关键词相关程度。可以考虑的版式信息有：是否是标题，是否为关键词，是否是正文，字体大小，是否加粗等等。同时，锚文本的信息也是非常重要的，它一般能精确的描述所指向的页面的内容。
2.2基于链接分析排序的第二代搜索引擎
链接分析排序的思想起源于文献引文索引机制，即论文被引用的次数越多或被越权威的论文引用，其论文就越有价值。链接分析排序的思路与其相似，网页被别的网页引用的次数越多或被越权威的网页引用，其价值就越大。被别的网页引用的次数越多，说明该网页越受欢迎，被越权威的网页引用，说明该网页质量越高。链接分析排序算法大体可以分为以下几类：基于随机漫游模型的，比如PageRank和Repution算法；基于概率模型的，如SALSA、PHITS；基于Hub和Authority相互加强模型的，如HITS及其变种；基于贝叶斯模型的，如贝叶斯算法及其简化版本。所有的算法在实际应用中都结合传统的内容分析技术进行了优化。本文主要介绍以下几种经典排序算法：
1）PageRank算法
PageRank算法由斯坦福大学博士研究生Sergey Brin和Lwraence Page等提出的。PageRank算法是Google搜索引擎的核心排序算法，是Google成为全球最成功的搜索引擎的重要因素之一，同时开启了链接分析研究的热潮。
PageRank算法的基本思想是：页面的重要程度用PageRank值来衡量，PageRank值主要体现在两个方面：引用该页面的页面个数和引用该页面的页面重要程度。一个页面P（A）被另一个页面P（B）引用，可看成P（B）推荐P（A），P（B）将其重要程度（PageRank值）平均的分配P（B）所引用的所有页面，所以越多页面引用P（A），则越多的页面分配PageRank值给P（A），PageRank值也就越高，P（A）越重要。另外，P(B)越重要，它所引用的页面能分配到的PageRank值就越多，P（A）的PageRank值也就越高，也就越重要。
其计算公式为：
PR（A）：页面A的PageRank值；
d：阻尼系数，由于某些页面没有入链接或者出链接，无法计算PageRank值，为避免这个问题（即LinkSink问题），而提出的。阻尼系数常指定为0.85。
R（Pi）：页面Pi的PageRank值；
C（Pi）：页面链出的链接数量；
PageRank值的计算初始值相同，为了不忽视被重要网页链接的网页也是重要的这一重要因素，需要反复迭代运算，据张映海撰文的计算结果，需要进行10次以上的迭代后链接评价值趋于稳定，如此经过多次迭代，系统的PR值达到收敛。
PageRank是一个与查询无关的静态算法，因此所有网页的PageRank值均可以通过离线计算获得。这样，减少了用户检索时需要的排序时间，极大地降低了查询响应时间。但是PageRank存在两个缺陷：首先PageRank算法严重歧视新加入的网页，因为新的网页的出链接和入链接通常都很少，PageRank值非常低。另外PageRank算法仅仅依靠外部链接数量和重要度来进行排名，而忽略了页面的主题相关性，以至于一些主题不相关的网页（如广告页面）获得较大的PageRank值，从而影响了搜索结果的准确性。为此，各种主题相关算法纷纷涌现，其中以以下几种算法最为典型。
2）Topic-Sensitive PageRank算法
由于最初PageRank算法中是没有考虑主题相关因素的，斯坦福大学计算机科学系Taher Haveli-wala提出了一种主题敏感（Topic-Sensitive）的PageRank算法解决了“主题漂流”问题。该算法考虑到有些页面在某些领域被认为是重要的，但并不表示它在其它领域也是重要的。
网页A链接网页B，可以看作网页A对网页B的评分，如果网页A与网页B属于相同主题，则可认为A对B的评分更可靠。因为A与B可形象的看作是同行，同行对同行的了解往往比不是同行的要多，所以同行的评分往往比不是同行的评分可靠。遗憾的是TSPR并没有利用主题的相关性来提高链接得分的准确性。
3）HillTop算法
HillTop是Google的一个工程师Bharat在2001年获得的专利。HillTop是一种查询相关性链接分析算法，克服了的PageRank的查询无关性的缺点。HillTop算法认为具有相同主题的相关文档链接对于搜索者会有更大的价值。在Hilltop中仅考虑那些用于引导人们浏览资源的专家页面（Export Sources）。Hilltop在收到一个查询请求时，首先根据查询的主题计算出一列相关性最强的专家页面，然后根据指向目标页面的非从属专家页面的数量和相关性来对目标页面进行排序。
HillTop算法确定网页与搜索关键词的匹配程度的基本排序过程取代了过分依靠PageRank的值去寻找那些权威页面的方法，避免了许多想通过增加许多无效链接来提高网页PageRank值的作弊方法。HillTop算法通过不同等级的评分确保了评价结果对关键词的相关性，通过不同位置的评分确保了主题（行业）的相关性，通过可区分短语数防止了关键词的堆砌。
但是，专家页面的搜索和确定对算法起关键作用，专家页面的质量对算法的准确性起着决定性作用，也就忽略了大多数非专家页面的影响。专家页面在互联网中占的比例非常低（1.79%），无法代表互联网全部网页，所以HillTop存在一定的局限性。同时，不同于PageRank算法，HillTop算法的运算是在线运行的，对系统的响应时间产生极大的压力。
4）HITS
HITS（Hyperlink Inced Topic Search）算法是Kleinberg在1998年提出的，是基于超链接分析排序算法中另一个最着名的算法之一。该算法按照超链接的方向，将网页分成两种类型的页面：Authority页面和Hub页面。Authority页面又称权威页面，是指与某个查询关键词和组合最相近的页面，Hub页面又称目录页，该页面的内容主要是大量指向Authority页面的链接，它的主要功能就是把这些Authority页面联合在一起。对于Authority页面P，当指向P的Hub页面越多，质量越高，P的Authority值就越大；而对于Hub页面H，当H指向的Authority的页面越多，Authority页面质量越高，H的Hub值就越大。对整个Web集合而言，Authority和Hub是相互依赖、相互促进，相互加强的关系。Authority和Hub之间相互优化的关系，即为HITS算法的基础。
HITS基本思想是：算法根据一个网页的入度（指向此网页的超链接）和出度（从此网页指向别的网页）来衡量网页的重要性。在限定范围之后根据网页的出度和入度建立一个矩阵，通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。
实验数据表明，HITS的排名准确性要比PageRank高，HITS算法的设计符合网络用户评价网络资源质量的普遍标准，因此能够为用户更好的利用网络信息检索工具访问互联网资源带来便利。
但却存在以下缺陷：首先，HITS算法只计算主特征向量，处理不好主题漂移问题；其次，进行窄主题查询时，可能产生主题泛化问题；第三，HITS算法可以说一种实验性质的尝试。它必须在网络信息检索系统进行面向内容的检索操作之后，基于内容检索的结果页面及其直接相连的页面之间的链接关系进行计算。尽管有人尝试通过算法改进和专门设立链接结构计算服务器（Connectivity Server）等操作，可以实现一定程度的在线实时计算，但其计算代价仍然是不可接受的。
2.3基于智能化排序的第三代搜索引擎
排序算法在搜索引擎中具有特别重要的地位，目前许多搜索引擎都在进一步研究新的排序方法，来提升用户的满意度。但目前第二代搜索引擎有着两个不足之处，在此背景下，基于智能化排序的第三代搜索引擎也就应运而生。
1）相关性问题
相关性是指检索词和页面的相关程度。由于语言复杂，仅仅通过链接分析及网页的表面特征来判断检索词与页面的相关性是片面的。例如：检索“稻瘟病”，有网页是介绍水稻病虫害信息的，但文中没有“稻瘟病”这个词，搜索引擎根本无法检索到。正是以上原因，造成大量的搜索引擎作弊现象无法解决。解决相关性的的方法应该是增加语意理解，分析检索关键词与网页的相关程度，相关性分析越精准，用户的搜索效果就会越好。同时，相关性低的网页可以剔除，有效地防止搜索引擎作弊现象。检索关键词和网页的相关性是在线运行的，会给系统相应时间很大的压力，可以采用分布式体系结构可以提高系统规模和性能。
2）搜索结果的单一化问题
在搜索引擎上，任何人搜索同一个词的结果都是一样。这并不能满足用户的需求。不同的用户对检索的结果要求是不一样的。例如：普通的农民检索“稻瘟病”，只是想得到稻瘟病的相关信息以及防治方法，但农业专家或科技工作者可能会想得到稻瘟病相关的论文。
解决搜索结果单一的方法是提供个性化服务，实现智能搜索。通过Web数据挖掘，建立用户模型（如用户背景、兴趣、行为、风格），提供个性化服务。
B. 全文检索算法，请问谁能给我点头绪落，不懂啊。。
全文检索技术
全文检索是指索引程序扫描文章中的每个词并建立对应索引，记录该词出现的位置和次数。当通过搜索引擎查询时，检索程序就在记录的索引进行查找并返回给用户。全文检索又分为基于字的全文索引和基于词的全文索引。基于字的全文索引会对内容中的每个字建立索引并记录，此方法查全率高，但查准率低，特别是对于中文，有时搜索马克，会列出马克思的结果。基于词的全文索引是把一个词语作为一个单位进行索引记录，并能处理同义词。搜索引擎有自己的词库，当用户搜索时，搜索引擎会从词库中抽取关键词作为索引项，这样可以大大提高检索的准确率。
中文分词技术
一直以来大家都比较熟悉网络，网络有自己的中文分词技术。一般采用的包括正向最大匹配，反向最大匹配，最佳匹配法，专家系统方法等。其中最大正向匹配是最常用的分词解决方案，它采用机械式算法，通过建立词典并进行正向最大匹配对中文进行分词。举个简单的例子比如搜索“北京大学在哪里”，则返回结果很多都是包含北京大学，北大等词语的网页，搜索引擎就是采用正向最大匹配去判断，把北京大学当做一个词语来索引记录并返回。当然，正向最大匹配也有不完整性，比如长度过长的词语，搜索引擎有时无法准确的分词，或者对前后都相互关联的词无法准确分词。例如“结合成分子时”，会被返回结合、成分、子时，而有时我们想要的关键词是“分子”。
很多时候网络都会根据自己词库中词语的权重进行拆分，权重的计算基于生活各个方面，比较复杂，搜索引擎要做的就是返回用户最想要的结果，有时站长们做网站要站在用户的角度去考虑问题，其实这也是站在搜索引擎的角度考虑问题，不论在确定目标关键词或者是长尾关键词时，都可以根据中文分词的原理来选择，这样可以最大化的减少无用功。
分词原理不断在变化，不断在更新，我们应该继续学习，只有掌握了本质才能抓住实质。
C. 经典检索算法：BM25原理
本文cmd地址： 经典检索算法：BM25原理
bm25 是一种用来评价搜索词和文档之间相关性的算法，它是一种基于 概率检索模型 提出的算法，再用简单的话来描述下bm25算法：我们有一个query和一批文档Ds，现在要计算query和每篇文档D之间的相关性分数，我们的做法是，先对query进行切分，得到单词$q_i$，然后单词的分数由3部分组成：
最后对于每个单词的分数我们做一个求和，就得到了query和文档之间的分数。
讲bm25之前，我们要先介绍一些概念。
BIM(binary independence model)是为了对文档和query相关性评价而提出的算法，BIM为了计算$P(R|d,q)$，引入了两个基本假设：
假设1
一篇文章在由特征表示的时候，只考虑词出现或者不出现，具体来说就是文档d在表示为向量$vec x=(x_1,x_2,...,x_n)$，其中当词$t$出现在文档d时，$x_t=1$，否在$x_t=0$。
假设2
文档中词的出现与否是彼此独立的，数学上描述就是$P(D)=sum_{i=0}^n P(x_i)$
有了这两个假设，我们来对文档和query相关性建模：
接着因为我们最终得到的是一个排序，所以，我们通过计算文档和query相关和不相关的比率，也可得文档的排序，有下面的公式：
由于每个 xt 的取值要么为 0 要么为 1，所以，我们可得到：
我们接着做下面的等价变换：
其中N是总的文档数，dft是包含t的文档数。
以上就是BIM的主要思想，后来人们发现应该讲BIM中没有考虑到的词频和文档长度等因素都考虑进来，就有了后面的BM25算法，下面按照
3个部分来介绍bm25算法。
，也就是有多少文档包含某个单词信息进行变换。如果在这里使用 IDF 的话，那么整个 BM25 就可以看作是一个某种意义下的 TF-IDF，只不过 TF 的部分是一个复杂的基于文档和查询关键字、有两个部分的词频函数，还有一个就是用上面得到的ct值。
tf-idf中，这个信息直接就用“词频”，如果出现的次数比较多，一般就认为更相关。但是BM25洞察到：词频和相关性之间的关系是非线性的，具体来说，每一个词对于文档相关性的分数不会超过一个特定的阈值，当词出现的次数达到一个阈值后，其影响不再线性增长，而这个阈值会跟文档本身有关。
在具体操作上，我们对于词频做了”标准化处理“，具体公式如下：
其中，tftd 是词项 t 在文档 d 中的权重，Ld 和 Lave 分别是文档 d 的长度及整个文档集中文档的平均长度。k1是一个取正值的调优参数，用于对文档中的词项频率进行缩放控制。如果 k 1 取 0，则相当于不考虑词频，如果 k 1取较大的值，那么对应于使用原始词项频率。b 是另外一个调节参数 （0≤ b≤ 1），决定文档长度的缩放程度：b = 1 表示基于文档长度对词项权重进行完全的缩放，b = 0 表示归一化时不考虑文档长度因素。
如果查询很长，那么对于查询词项也可以采用类似的权重计算方法。
其中，tftq是词项t在查询q中的权重。这里k3 是另一个取正值的调优参数，用于对查询中的词项tq 频率进行缩放控制。
于是最后的公式是：
gensim在实现bm25的时候idf值是通过BIM公式计算得到的：
然后也没有考虑单词和query的相关性。
此处 EPSILON 是用来表示出现负值的时候怎么获取idf值的。
总结下本文的内容：BM25是检索领域里最基本的一个技术，BM25 由三个核心的概念组成，包括词在文档中相关度、词在查询关键字中的相关度以及词的权重。BM25里的一些参数是经验总结得到的，后面我会继续介绍BM25的变种以及和其他文档信息（非文字）结合起来的应用。
BM25 算法浅析
搜索之 BM25 和 BM25F 模型
经典搜索核心算法：BM25 及其变种
信息检索导论
D. 淘宝搜索排名怎么算的
一、 taobao首页的搜索规律
此处考虑的是商品关于普通关键字的排名。在关键字的选择上，为了避免taobao对部分热门关键字商品的排序进行人为影响，我们选择一组比较冷的关键字进行测试。在taobao首页搜索栏搜索商品，通过对结果的对比，可以得出以下几个规律
1、无关因素规律
排名先后与售出量、浏览量、价格、卖家好评率、先行赔付、所在地、商品页面的排版布局和单一关键字在商品名称中出现的先后顺序、次数等因素基本无关。例如“火星湖专卖，火星湖折扣电影”的商品和名为“火星湖电影票”的商品比较，在搜索“火星湖”关键字的时候，前一种商品不会因为“火星湖”关键字出现了两次或者售出量多等因素而在搜索结果中排名靠前。
2、搜索结果排名规律
影响商品排名的关键因素有两个，分别是“剩余时间”和“是否推荐商品”。其中的剩余时间＝宝贝有效期－（当前时间－发布时间）。宝贝有效期有两种取值，分别是14和7，对应与产品发布时选择的有效期，发布时间就是你的宝贝上架的时间。“推荐商品”这个因素对应于我们发布商品时的“橱窗推荐”选项。搜索结果根据是否“橱窗推荐”商品这个因素，被划分为两个区段，无论剩余时间是多少，推荐商品的区段排名都在未推荐商品区段的前面，同一区段内，剩余时间越短，排名越靠前。例如：即便“火星湖电影票”商品还有5分钟就要下架了，如果它没有被勾选为橱窗推荐商品，他的排名还是比刚刚发布出来的橱窗推荐商品“火星湖折扣电影票”靠后。如果同样都是橱窗推荐商品，那么快要下架的“火星湖电影票”会排在前面。
3、等效搜索词规律
1） 第一关键词＋第二关键词＝第一关键词＋特殊字符＋第二关键词即紧密排列规律，搜索时特殊字符将被忽略，搜索结果不含拆分（即搜索结果中多个关键词按照顺序紧密相连）。
2） 第一关键词＋空格＋第二关键词＝第二关键词＋空格＋第一关键词，即顺序无关规律，用空格分割两个关键词搜索的结果中含拆分（即搜索结果中既有多个关键词紧密相连又有多个关键词不紧密相连的情况），关键词出现顺序和搜索时的顺序无关。例如搜索“火星湖 电影票”，那么标题为“电影票5折珠海火星湖”和“珠海火星湖电影票5折”这两种情况都将被搜索到。同时无论搜索的结果含不含拆分，排名一定严格按照搜索结果排名规则来排序。
经过大量测试，taobao基本没有对关键字排名进行干预，搜索符合上述三条规律
二、高级搜索页搜索规律
Taobao高级搜索页搜索所得出的结果和首页搜索的结果很大差别，搜索不再以剩余时间为主要的排名依据，通过分析结果得到以下一些规律。首先，通过高级搜索页搜出来的结果默认显示的是“人气宝贝”列表中的宝贝，这个列表的排名显然不是以剩余时间来排序的，经过测试，我们发现影响人气宝贝列表排名的因素主要是浏览量、售出量、卖家等级（信誉值）这几个因素。淘宝经过一定的权值计算后，给出了最终列表的顺序。并且这个顺序十分不稳定，顺序经常发生变化，这主要是由于商品浏览量的变化导致的。由此可以说明，浏览量对排名因素的作用高于其他因素。此外，页面上还有“所有宝贝”选项，经过分析，所有宝贝选项卡中的商品排列顺序完全符合第一点中的三条规律.
三、淘宝商家应对的优化策略
实际进入高级搜索页来搜索商品的买家相对较少，大部分买家一般都在首页搜索栏进行搜索。并且在高级搜索页面进行第二次搜索时，实际上采用的仍然是首页搜索的机制，所以在考虑店铺优化时，可先暂时规避因为高级搜索规律所带来的复杂度，集中考虑普通搜索的三个规律的优化策略。