深入搜索引擎原理( 二 ) _搜索引擎

3.词干还原（Stemming）
通常指的就粗略的去除单词两端词缀的启发式过程

automate(s), automatic, automation -> automat.
高高兴兴 -> 高兴 [中文重叠词还原]
明明白白 -> 明白

英文的常见词干还原算法，Porter算法。
Part2、倒排索引要了解倒排索引，先看一下什么是正排索引。比如有下面两句话：

id1, “搜索引擎提供检索服务”
id2, “搜索引擎是信息检索系统”

正排索引
正排索引就是 MySQL 里的 B+ Tree，索引的结果是：

“搜索引擎是信息检索系统” -> id2
“搜索引擎提供检索服务” -> id1

表示对完整内容按字典序排序，得到一个有序的列表，以加快检索的速度。
倒排索引
第一步分词

“搜索引擎-提供-检索-服务” -> id1
“搜索引擎-信息-检索-系统” -> id2

第二步将分词项构建一个词典

搜索引擎
提供
检索
服务
信息
系统

第三步构建倒排链

搜索引擎 -> id1, id2
提供 -> id1
检索 -> id1, id2
服务 -> id1
信息 -> id2
系统 -> id2

由此，一个倒排索引就完成了，搜索 “检索” 时，得到 id1, id2，说明这两条数据都有，搜索 “服务” 只有 id1 存在。但如果搜索 “检索系统”，此时会先建搜索词按照与构建同一种策略分词，得到 “检索-系统”，两个词项，分别搜索检索 -> id1, id2 和系统 -> id2，然后对其做一个交集，得到 id2 。同理，通过求并集可以支持更复杂的查询。
倒排索引到此也就讲清楚了吧。
存储结构

文章插图

以 Lucene 为例，简单说明一下 Lucene 的存储结构。从大到小是Index -> Segment -> Doc -> Field -> Term，类比 MySQL 为 Database -> Table -> Record -> Field -> Value 。
Part 3、查询结果排序搜索结果排序是根据关键字和 Document 的相关性得分排序，通常意义下，除了可以人工的设置权重 boost，也存在一套非常有用的相关性得分算法，看完你会觉得非常有意思。
TF-IDF
TF(词频)-IDF(逆文档频率) 在自动提取文章关键词上经常用到，通过它可以知道某个关键字在这篇文档里的重要程度。其中 TF 表示某个 Term 在 Document 里出现的频次，越高说明越重要；DF 表示在全部 Document 里，共有多少个 Document 出现了这个词，DF 越大，说明这个词很常见，并不重要，越小反而说明他越重要，IDF 是 DF 的倒数(取log)，IDF 越大，表示这个词越重要。
TF-IDF 怎么影响搜索排序，举一个实际例子来解释：
假定现在有一篇博客《Blink 实战总结》，我们要统计这篇文章的关键字，首先是对文章分词统计词频，出现次数最多的词是--"的"、"是"、"在"，这些是“停用词”，基本上在所有的文章里都会出现，他对找到结果毫无帮助，全部过滤掉。
只考虑剩下的有实际意义的词，如果文章中词频数关系： “Blink” > “词频” = “总结”，那么肯定是 Blink 是这篇文章更重要的关键字。但又会遇到了另一个问题，如果发现 "Blink"、"实战"、"总结"这三个词的出现次数一样多。这是不是意味着，作为关键词，它们的重要性是一样的？
不是的，通过统计全部博客，你发现含关键字总博客数： “Blink” < “实战” < “总结”，这时候说明 “Blink” 不怎么常见，一旦出现，一定相比 “实战” 和 “总结”，对这篇文章的重要性更大。
BM25
上面解释了 TF 和 IDF，那么 TF 和 IDF 谁更重要呢，怎么计算最终的相关性得分呢？那就是 BM25 。
BM25算法，通常用来作搜索相关性平分。一句话概况其主要思想：对Query进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。
BM25算法的一般性公式如下：