这就是搜索引擎：核心技术详解

2019-05-01
16 min read
techs , reads

本文为阅读《这就是搜索引擎：核心技术详解》的读书笔记

graph TD
	A[搜索引擎]
	style A fill:#cc66ff
	A --> B[4阶段]
	A --> C[爬虫]
	A --> D[倒排索引<br/><b>单文</b>矩阵]
	C --> E[作弊:<br/>内容<br/>链接<br/>隐藏<br/>web2.0]
	B --> G[暗网 <br/> 两大难点]
	D --> I[分词<br/>NLP]
	D --> K[动态索引<br/>三模块]
	K --> L[分布式<br/>文档&单词]
	I --> M[短语查询]
	A --> N[检索<br/>压缩]
	N --> O[布尔<br/>向量<br/>概率<br/>语言<br/>学习]
	A --> P[链接分析]
	P --> Q[PageRank <br/> OPIC<br/>HITS:<br/>Authority,<br/>Hub]
	I --> R[多字段索引]
	I --> T[意图分析<br/>发展趋势]
	B --> U[Lucene<br>Solr<br>ES<br/>IKA..]

[TOC]

搜索引擎是互联网重要的组成部分，搜索引擎技术也是当前解决信息过载问题主要的手段

可以按照使用的技术将搜索引擎的发展分为四个阶段：

  1. 分类目录，和 PC 机上的文件目录类似，相同种类的网址由人工整理并汇聚在一起
  2. 文本检索，使用信息检索模型匹配用户的搜索和页面，例如在所有文档中搜索用户输入的单词，返回含有搜索词的文档
  3. 链接分析，在文本检索的基础上同时考虑网页之间的链接关系，使用网页之间的关系衡量网页的流行（重要）性。如果没有作弊，那么大部分网页使用超链指向的页面其重要性一般大于其他页面，向用户展示时优先返回这类多入链的网页
  4. 用户中心，以用户为中心，理解并满足用户的个性化需求，例如用户搜索 苹果，但其实其可能要搜索 iphone 11

搜索引擎的目标是：更全、更快、更准

搜索引擎的技术架构

graph LR
	A((互联网))
	style A fill:#00ff00
	A --> B(网络爬虫<br/>网页去重)
	B --> D[倒排索引<br/><链接关系>]
	C[云平台] --> D
	E[反作弊] --> D
	style E fill:#cc66ff
	D --> F[内容相似性<br/>链接分析]
	F --> G((网页排序))
	H((用户))
	style H fill:#00ff00
	H --> I[Cache]
	I --> G

相关概念

  • 种子 URL & 网络爬虫，启动网络爬虫时需要提供初始 URL，这些 URL 就是种子 URL
  • 网页分类 & 网络爬虫，已下载、已过期、待下载（已加入爬虫 URL 队列）、可知页面、不可知页面
  • 爬虫分类，批量型（达到目标即停止）、增量型（不停的抓取）、垂直型（关注特定领域的爬虫）
  • 爬虫的友好性，履行爬虫禁抓协议以保护网站的部分私密性；尽量减少被抓网站的网络负载
  • 爬虫爬取策略，因为爬虫资源有限而网页资源接近无限，故不同类型网页的抓取与更新其策略不同
    • 宽度优先遍历
    • 非完全 PageRank ，抓取部分页面与 URL 后分析这些 URL，随后只抓取比较重要的网页。一个简单的方法：将网页看作是图的节点，被链接指向次数越多的网页其重要性一般也越大（咱不考虑作弊）。全网的 PageRank 几乎不可能，所以只能部分处理
    • OPIC（online page importance computation），和非完全 PageRank 思路一致。每个新抓的页面都会被赋予相同的 cash（现金），这些 cash 会均分给当前页面中的 URL，系统中已有URL 按照 cash 大小进行排序。OCIP 相对于 PageRank 而言优势在于速度与实时性
    • 大站优先
  • 已爬网页更新策略
    • 历史参考，过去频繁更新的网页将来频繁更新的概率比较大，泊松过程
    • 用户体验策略，影响大的页面应尽早更新
    • 聚类抽样策略，不同种类页面更新频率不同
  • 分布式爬虫
    • 主从式爬虫
    • 对等式爬虫

暗网

所谓的暗网指的是那些存储在数据库里，不能通过超链接访问的资源集合。简单点说所谓的暗网就是不能或者很难被搜索引擎收录的网络资源。携程的机票数据需要通过组合的方式才能查询出来，对于网络爬虫而言这个过程难以实现自动化，普通的暴力抓取将对被抓网站带来较大的压力而且效率非常低下

暗网爬虫的技术难点有两个：

  • 组合太多（始发地、目的地、出行时间、班次等），如何精心挑选查询组合？
  • 查询大部分是文本框，爬虫如何输入合适的内容？

上面两个技术难点有部分解决方案，可以参考《这就是搜索引擎》的第 2.6 节

索引

索引是搜索引擎的核心技术之一，是搜索引擎快速查找的基础

一些概念

  • 文档（Doc），以文本形式存在的对象，或者说能被分词系统解析的独立存储单元，例如 PDF、Word、html、xml 等
  • 倒排索引（inverted index），倒排索引是下面单词—文档矩阵的一种存储形式。通过倒排索引可以根据单词快速获得包含这个单词的文档列表。倒排索引常用的实现方法有哈希表和多叉树
  • 单词词典，搜索引擎通常的索引单位是单词，单词词典是文档集合中出现过的所有单词构成的字符串集合
  • 倒排列表，同一个单词可能出现在了不同的文档中，且在同一个文档中也可能出现多次，倒排列表用来保存单词与文档之间的关联信息
  • 倒排文件，存储所有单词和其对应倒排列表的文件
  • 文档频率，表明某个单词出现在了当前文档集合中的多少个文档中

单词——文档 矩阵

单词文档矩阵用来表示某一个文档中是否存在某一个单词，例如：

文档 1 文档 2 … 文档 n
词汇 1 包含 不包含
… … … … …
词汇 n 包含 …

分词系统

在英文的行文中，单词之间是以空格作为自然分界符的，而中文只有字、句和段能通过明显的分界符来简单划界，而词没有一个形式上的分界符，分词处理就是将连续的字序列按照一定的规范重新组合成词序列的过程

单词是搜索引擎的基本搜索元素，为了创建单词文档矩阵，需要先使用分词系统提取文档中所有的单词

文档的分词处理是自然语言处理（NLP）的核心工具之一，而 NLP 则是大数据时代极为重要的工具。本文不对分词算法做介绍，详细信息可以参考其他文档

倒排索引示例

示例文档

文档编号 文档内容
1 谷歌地图之父跳槽Facebook
2 谷歌地图之父加盟Facebook
3 谷歌地图创始人拉斯离开谷歌加盟Facebook
4 谷歌地图之父跳槽Facebook与Wave项目取消有关
5 谷歌地图之父拉斯加盟社交网站Facebook

倒排索引示例

单词 ID 单词 文档频率 倒排列表（文档编号、词频、位置）
1 谷歌 5 (1;1;<1>),(2;1;<1>),(3;2;<1;6>),(4;1;<1>),(5;1;<1>)
2 创始人 1 (3;1;<3>)
… … … …

单词“谷歌”出现在了 5 个文档中，并且在第三个文档中出现了 2 次，分别在文档第一个单词处和第 6 个单词处

索引的建立与更新

常见的索引建立方法有三种：两遍文档法、排序法和归并法，比较常用的是归并算法

在数据量大到不能使用内存存储时只能使用外排算法：归并

动态索引

搜索动态变化的文档集合时需要创建动态索引，此时系统中有三个关键部分：倒排索引、临时索引和已删除文档列表

变化的文档会先建立临时索引。文档的更新按照删除&重新添加进行处理，删除的文档需要在删除文档列表中进行维护，返回查询结果时需要使用删除文档列表过滤查询结果

graph LR
	A((查询))
	style A fill:#00ff00
	A --> C[临时索引<br/><新增文档>]
	A --> D[倒排索引]
	C --> E[已删除文档列表<过滤>]
	D --> E
	E --> F((查询结果))

索引更新有多种策略：完全重构、再合并、原地更新及混合策略，具体解释参考原书 3.6 节。与爬虫策略类似，不同属性的单词其索引更新策略也可以不同

多字段索引

有些文档有一定的结构，例如邮件有发件人、收件人、标题和正文等，有些搜索指明了搜索结构文档中的某一部分，例如只在收件人列表中搜索。实现多字段索引需要使用一定途径获得文档的结构信息和单词与文档结构间的信息

多字段索引常见三种方法：

  • 多索引，即对结构化文档的每一个部分建立一个索引。对于邮件而言就是同时对标题、正文等不同部分建立独立的索引
  • 倒排列表，只对文档建立一个索引，不过在倒排列表中添加单词所在结构的信息，后续使用这些信息过滤非指定位置的结果
  • 扩展列表方式，和上面第二种方式类似，不过位置信息并非保存在倒排列表中。例如扩展列表详细描述了某一篇文档的结构：第 1 个单词到第 21 个单词是发件人信息，那么如果查询结果中的单词不是位于1~21单词，则可以知道这个结果不位于发件人信息中。这种方式比第二种方式可扩展性更强

分布式索引

对于搜索引擎而言建立分布式索引的方案有两种：按文档划分、按单词划分

按文档划分就是所有机器的功能都是相同的，不同机器对不同文档建立索引，每次查询的时候会发广播给所有机器

按单词划分则不同机器对不同的单词建立索引，一次查询只会涉及到部分机器

常用的方法是按文档进行索引，因为按单词进行索引有以下缺点：

  • 可扩展性差，每增加一个文档就会涉及到很多不同的机器，因为一个文档中包含了大量单词，这些单词又被不同机器索引
  • 负载均衡能力差，有些单词很常见，索引这类单词的机器比其他机器需要更多的资源
  • 容错性差，任何一台机器失效，某些单词的检索就会失败，因为不同机器索引不同单词
  • 查询方式限制，按单词划分只能使用一次一单词（下面介绍）的方式进行查询，而有些搜索需要按一次一文档的方式

查询

索引建立之后就可以使用索引来查询了，使用索引进行查询有两大类方法：一次一文档、一次一单词

查询的目的在于获得与查询信息相关的文档，如果查询结果有多个，还需对结果文档按照相关度进行排序。对文档相关度的计算可以从两个角度进行，一种是计算完一个文档后再计算另一个文档，另一种是先计算每个文档关于某个单词的相关度得分，最后把得分累加，即为文档的最终得分

  • 一次一文档

    以倒排列表中包含的文档为单位，每次计算一个文档和查询字段的最终相似性，然后计算余下文档，最后对文档得分进行排序

  • 一次一单词

    以查询单词为单位，每次查询一个文档关于一个单词的得分，查询完一个单词所涉及的所有文档后再查下一个单词。累加所有单词得分即为文档的最终得分

短语查询

常见的短语查询方法

  1. 位置信息索引方式很直观，单词在文档中出现的顺序和短信中的顺序相同即认为匹配，但当短信中包含的单词比较多时效率不高

  2. 双词索引在常见的双词短信中的两个单词之间建立连接，可以通过双词的首词快速的找到下词。双词索引会消耗大量的存储空间，故一般只对常见短语使用这种方式

  3. 短语索引就是将短语当作单词看待并为其建立索引，短语索引一般需要结合数据挖掘来获得热门短语

短语亦有属性与类别，不同属性的短信可以使用不同的索引方式

索引压缩（略）

检索模型&搜索排序

检索模型

布尔模型

布尔模型是检索模型中最简单的一种，其数学基础是集合论。在布尔模型中，文档与用户查询由其包含的单词集合来表示，两者 的相似性则通过布尔代数运算来进行判定，例如：Query = apple AND ( Jobs OR Ipad2 )，单词文档矩阵结果为 true 时返回对应的文档 ID

向量空间模型

常见的方式是以单词作为特征，使用 t 维带权重向量表示一个文档。检索时将用户查询信息也当做一个特殊的文档亦转化为特征向量，使用向量距离度量查询与文档的相关性

概率检索模型

概率检索模型是当前效果最好的模型之一，大部分商用搜索引擎都使用这种方式。BM25 是当前效果最好的概率搜索模型

看完贝叶斯之后再看一遍

语言模型方法

判断由文档生成用户查询的可能性有多大，然后按照这种生成概率由高到低排序，作为搜索结果

机器学习排序

当排序因子比较多时使用机器学习方法较好

用户点击可以看做是一种标签，点击率高说明当前页面和查询相关性高

链接分析

搜索引擎在检索信息时常用的两大特征：

  1. 网页和查询的相关性

  2. 网页的重要性

概念

入链、出链、锚文字

PageRank & HITS & SALSA

PageRank

PageRank 算法主要使用网页的入链（个数与质量）作为依据来给网页打分，PageRank 算法与用户查询无关

其他改进算法：

  • 主题敏感 PageRank

HITS

HITS 算法有两个主要的概念： Hub 页面和 Authority 页面。Authority 页面指与某个领域或者话题相关度高的网页，例如与视频相关度高的网页有腾讯视频、优酷视频等；Hub 页面指的是包含很多出链指向高质量 Authority 页面的页面。HITS 算法在海量网页中找到与用户查询主题相关的高质量 Authority 页面和 Hub 页面并以此为结果返回给用户

HITS 算法与用户查询密切相关

SALSA & Hilltop

SALSA 和 Hilltop 算法是 PageRank 和 HITS 算法的结合与改进

网页反作弊

常见作弊手段

内容作弊

关键词重复、网页标题作弊、网页重要标签作弊、内容农场等

链接作弊

链接农场、google 轰炸（精心设计锚文字）、链接购买等

页面隐藏作弊

用户看见的内容和搜索引擎收录的内容不同，例如 IP 地址作弊、页面内容隐藏等

web 2.0 作弊手段

web 2.0 指的是一个利用 Web 平台，由用户主导而生成内容的互联网产品模式，区别传统（web 1.0）由网站雇员主导生成内容的互联网模式

常见作弊手段有：博客作弊、点评作弊、微博作弊等

反作弊手段

信任传播模型（信任知网，则检索知网所有内容）、不信任传播模型（剔除部分不可靠的网站）、异常发现模型、综合模型等

用户搜索意图分析

分析用户意图以向用户展示更准确的搜索内容

常见手段：

  1. 用户搜索日志挖掘
  2. 点击图分析，用户优先点击与自己搜索意图相近的页面
  3. 查询图，用户会根据搜索引擎的返回修改检索词汇
  4. 相关搜索，返回类似内容
  5. 查询纠错等
  6. 等等

发展趋势

  • 个性化搜索
  • 社会化搜索，社会化搜索的本质是信息过滤与推荐，社会化搜索通过社交关系选择可信赖的用户和答案
  • 实时搜索
  • 移动搜索
  • 地理位置感知搜索
  • 跨语言搜索，输入中文，显示英文相关结果
  • 多媒体搜索
  • 情景搜索

搜索引擎工具

graph TB
	A((Lucene))
	A --> B[Solr]
	A --> C[ElasticSearch]
	A --> H[Java]
	B --> D[RESTful & Admin]
	B --> E[Core & Field]
	B --> F[IKAnalyzer]
	C --> F
	C --> G[Kibana]

Lucene

Lucene (['lu:si:n]) 是基于 java 的开源全文索引工具包

本文内容参考 how2j，感谢~

示例代码

// 1. 准备中文分词器
IKAnalyzer analyzer = new IKAnalyzer();

// 2. 使用测试数据创建索引
List<String> productNames = new ArrayList<>();
productNames.add("飞利浦led灯泡e27螺口暖白球泡灯家用照明超亮节能灯泡转色温灯泡");
productNames.add("飞利浦led灯泡e14螺口蜡烛灯泡3W尖泡拉尾节能灯泡暖黄光源Lamp");
productNames.add("雷士照明 LED灯泡 e27大螺口节能灯3W球泡灯 Lamp led节能灯泡");
productNames.add("飞利浦 led灯泡 e27螺口家用3w暖白球泡灯节能灯5W灯泡LED单灯7w");
productNames.add("飞利浦led小球泡e14螺口4.5w透明款led节能灯泡照明光源lamp单灯");
productNames.add("飞利浦蒲公英护眼台灯工作学习阅读节能灯具30508带光源");
productNames.add("欧普照明led灯泡蜡烛节能灯泡e14螺口球泡灯超亮照明单灯光源");
productNames.add("欧普照明led灯泡节能灯泡超亮光源e14e27螺旋螺口小球泡暖黄家用");
productNames.add("聚欧普照明led灯泡节能灯泡e27螺口球泡家用led照明单灯超亮光源");		
Directory index = new RAMDirectory();
IndexWriterConfig config = new IndexWriterConfig(analyzer);
IndexWriter writer = new IndexWriter(index, config);

for (String name : productNames) {
    Document doc = new Document();
    doc.add(new TextField("name", name, Field.Store.YES));
    writer.addDocument(doc);
}
writer.close();

// 3. 查询器
String keyword = "护眼带光源";
Query query = new QueryParser("name", analyzer).parse(keyword);

// 4. 搜索
IndexReader reader = DirectoryReader.open(index);
IndexSearcher searcher = new IndexSearcher(reader);
int numberPerPage = 1000;
System.out.printf("当前一共有%d条数据%n",productNames.size());
System.out.printf("查询关键字是：\"%s\"%n",keyword);
System.out.printf("查询字符串分词结果：\"%s\"%n",query);
ScoreDoc[] hits = searcher.search(query, numberPerPage).scoreDocs;

// 5. 显示查询结果 
for (int i = 0; i < hits.length; ++i) {
    ScoreDoc scoreDoc= hits[i];
    int docId = scoreDoc.doc;
    Document d = searcher.doc(docId);
    List<IndexableField> fields = d.getFields();
    System.out.print((i + 1));
    System.out.print("\t" + scoreDoc.score);
    for (IndexableField f : fields) {
        System.out.print("\t" + d.get(f.name()));
    }
    System.out.println();
}

// 6. 关闭查询
reader.close();

执行结果 1：

查询关键字是："护眼带光源"
查询字符串分词结果："name:护眼 name:带 name:光源"
1	5.159822	飞利浦蒲公英护眼台灯工作学习阅读节能灯具30508带光源
2	0.43331528	欧普照明led灯泡蜡烛节能灯泡e14螺口球泡灯超亮照明单灯光源
3	0.425806	飞利浦led灯泡e14螺口蜡烛灯泡3W尖泡拉尾节能灯泡暖黄光源Lamp
4	0.425806	飞利浦led小球泡e14螺口4.5w透明款led节能灯泡照明光源lamp单灯
5	0.425806	欧普照明led灯泡节能灯泡超亮光源e14e27螺旋螺口小球泡暖黄家用
6	0.425806	聚欧普照明led灯泡节能灯泡e27螺口球泡家用led照明单灯超亮光源

执行结果 2：

查询关键字是："led 黄色"
查询字符串分词结果："name:led name:黄色"
1	0.22168216	飞利浦led小球泡e14螺口4.5w透明款led节能灯泡照明光源lamp单灯
2	0.22168216	聚欧普照明led灯泡节能灯泡e27螺口球泡家用led照明单灯超亮光源
3	0.21906272	雷士照明 LED灯泡 e27大螺口节能灯3W球泡灯 Lamp led节能灯泡
4	0.20684227	飞利浦 led灯泡 e27螺口家用3w暖白球泡灯节能灯5W灯泡LED单灯7w
5	0.1634743	飞利浦led灯泡e27螺口暖白球泡灯家用照明超亮节能灯泡转色温灯泡
6	0.1634743	欧普照明led灯泡蜡烛节能灯泡e14螺口球泡灯超亮照明单灯光源
7	0.16064131	飞利浦led灯泡e14螺口蜡烛灯泡3W尖泡拉尾节能灯泡暖黄光源Lamp
8	0.16064131	欧普照明led灯泡节能灯泡超亮光源e14e27螺旋螺口小球泡暖黄家用

执行结果 3：

查询关键字是："led 黄"
查询字符串分词结果："name:led name:黄"
1	2.0358434	欧普照明led灯泡节能灯泡超亮光源e14e27螺旋螺口小球泡暖黄家用
2	0.22168216	飞利浦led小球泡e14螺口4.5w透明款led节能灯泡照明光源lamp单灯
3	0.22168216	聚欧普照明led灯泡节能灯泡e27螺口球泡家用led照明单灯超亮光源
4	0.21906272	雷士照明 LED灯泡 e27大螺口节能灯3W球泡灯 Lamp led节能灯泡
5	0.20684227	飞利浦 led灯泡 e27螺口家用3w暖白球泡灯节能灯5W灯泡LED单灯7w
6	0.1634743	飞利浦led灯泡e27螺口暖白球泡灯家用照明超亮节能灯泡转色温灯泡
7	0.1634743	欧普照明led灯泡蜡烛节能灯泡e14螺口球泡灯超亮照明单灯光源
8	0.16064131	飞利浦led灯泡e14螺口蜡烛灯泡3W尖泡拉尾节能灯泡暖黄光源Lamp

仔细查看执行结果 2 和 3，这两次搜索意图其实很相近，但 Lucene 却返回了完全不同的结果。实际的搜索引擎会考虑用户的搜索意图，例如自动修改用户查询字符串以获得语义（意图）相似的查询字符串然后进行查询，最后向用户展示综合后的查询结果

IKAnalyzer

Lucene 和其他基于 Lucene 的搜索工具默认不包含中文分词其，默认环境下这些工具会将中文语句、段落或者文章分解为一个个单字，无法实现中文词语检索。IKAnalyzer 是一个三方中文分词器

以 “研究生命科学” 为例，使用默认的 Lucene 分词器，分词结果为 6 个独立的汉字：

研 | 究 | 生 | 命 | 科 | 学

使用 IKAnalyzer 作为分词器，分词结果为 5 个汉语单词：

研究生 | 研究 | 生命科学 | 生命 | 科学

Solr

Solr ( ['səulə])是一个开源搜索平台，用于构建搜索应用程序。它建立在 Lucene 之上

Solr 提供了类似 RESTful-API 的方式以便于其他系统与 Solr 进行通信，同时 Solr 提供了 web Admin 界面，便于用户操作与管理

概念

  • Core

    如果说 Solr 相当于一个数据库的话，那么 Core 就相当于一张表

  • Field，查询时需要指定字段名

    Core 相当于表，接下来就要为这个表设置字段，用于存放数据。使用 Solr 进行查询时需要指明查找的字段与查询的词，例如：SolrUtil.query("name:小米 电视 平板",0,10)、SolrUtil.query("category:家电",0,10)

常用命令（windows）

  • solr.cmd start
  • solr.cmd stop -all
  • solr.cmd create -c how2java -p 8983，创建 core
  • solr.cmd delete -c core1

ElasticSearch

和 Solr 一样， ElasticSearch 基于 Lucene，提供了更为便利的访问和调用

ES 和 Solr 一样没有默认的中文分词器，需要三方工具，安装命令：

elasticsearch-plugin.bat install file:.\elasticsearch-analysis-ik-6.2.2.zip

Kibana

Kibana 是一个开源的分析和可视化平台，设计用于和 Elasticsearch 一起工作。Kibana 是分析 ES 中数据的工具，Kibana 提供了 Dev tools 工具，便于用户使用 RESTful 风格方式向 ES 服务发送请求

默认访问端口：127.0.0.1:5601

索引

索引相当于就是一个数据库服务器上的某个数据库，所以索引也可以看成是 Elastic Search 里的某个数据库

使用 RESTful 风格操控 ES
PUT /how2java?pretty  
GET /_cat/indices?v   
DELETE /how2java?pretty

PUT /how2java/product/1?pretty
{
  "name": "蜡烛"
}
#搜索引擎 #search #ES #lucene
Next C++ STL