搜索引擎与程序化广告:原理、设计与实战

第 1 章 搜索技术的算法 1

1.1 背景 1

1.2 字符串搜索 2

1.2.1 概述 2

1.2.2 基础字符串搜索算法：暴力搜索算法 2

1.2.3 中级字符串搜索算法：KMP 算法 4

1.2.4 高级字符串搜索算法：BM 算法 9

1.2.5 字符串精确搜索：Grep 12

1.2.6 字符串模糊搜索 12

1.3 树搜索 19

1.3.1 概述 19

1.3.2 二叉搜索树 21

1.3.3 2-3-4 树 22

1.3.4 2-3-4 树与红黑树的等价关系 28

1.3.5 红黑树操作 34

1.3.6 红黑树典型应用场景 50

1.4 图搜索 50

1.4.1 概述 50

1.4.2 图建模中，邻接矩阵和邻接表哪种结构更好？ 51

1.4.3 DFS 在图搜索和树搜索中的应用 53

1.4.4 DFS 无向图连通分量问题 55

1.4.5 DFS 单源路径问题 58

1.4.6 BFS 单源（*短）路径问题 61

1.4.7 DFS 检测无向图中的环 64

1.4.8 二分图检测与染色算法 66

1.4.9 拓扑排序 68

1.4.10 动态规划和递归之间的关系 72

1.5 小结 73

第 2 章 Lucene 基础 75

2.1 背景 75

2.2 Lucene 与传统关系数据库 76

2.2.1 Lucene 与传统关系数据库的异同 76

2.2.2 Lucene 的全文搜索机制 77

2.2.3 倒排索引的使用场景 78

2.3 Lucene 与 Elasticsearch 79

2.4 Lucene 的倒排索引设计 80

2.4.1 倒排索引 80

2.4.2 Posting 数据结构 80

2.4.3 ByteBlockPool 动态数组 81

2.4.4 Posting 与 ByteBlockPool 的关系 83

2.4.5 ThreadState 结构 84

2.4.6 DocumentsWriter 结构 85

2.5 Lucene 的正排索引设计 92

2.5.1 正排索引与倒排索引 92

2.5.2 Lucene 的正排索引与数学中的向量的关系 93

2.5.3 正排索引存储 94

2.5.4 索引数据的写流程 96

2.6 有效负载 97

2.6.1 有效负载的结构 97

2.6.2 有效负载的格式 98

2.6.3 文档权重与域权重 99

2.6.4 权重与有效负载 99

2.6.5 有效负载的应用场景 100

2.7 复合索引文件 103

2.7.1 复合索引的文件格式 104

2.7.2 写复合索引文件 105

2.8 小结 106

第 3 章 Lucene 索引段 108

3.1 背景 108

3.2 不同索引结构的比较 108

3.2.1 MySQL：B 树 109

3.2.2 MySQL：哈希索引 109

3.2.3 Redis：跳表 109

3.2.4 Lucene：倒排索引 111

3.3 索引段的基础知识 112

3.3.1 概述 112

3.3.2 SegmentInfos 容器 113

3.3.3 IndexReader 116

3.3.4 SegmentReader 118

3.3.5 倒排索引格式 119

3.3.6 索引段的读流程 124

3.4 索引段的合并 126

3.4.1 概述 126

3.4.2 段合并的典型问题 127

3.4.3 段合并的策略 129

3.4.4 段合并的简单流程 132

3.4.5 合并段内域：mergeFields 135

3.4.6 合并段内分词：mergeTerms 143

3.4.7 合并段内词向量：mergeVectors 154

3.5 索引段提交点与快照 155

3.5.1 概述 155

3.5.2 提交点 155

3.5.3 快照 158

3.5.4 触发快照的场景 159

3.6 索引段删除文档 160

3.6.1 概述 160

3.6.2 del 扩展文件 160

3.6.3 位向量 162

3.6.4 索引段删除分词 164

3.6.5 索引段查询分词 165

3.7 小结 166

第 4 章 Lucene 分析器 167

4.1 背景 167

4.2 Field、Token 与 Term 概念 168

4.3 JavaCC 与查询解析器 170

4.3.1 Yacc 与 JavaCC 170

4.3.2 在 JavaCC 中扩展正则表达式 171

4.3.3 JavaCC 的输入文件之XX.jj 172

4.3.4 Lucene 中 Token 的正则表达式定义 173

4.3.5 Lucene 语法产生式：分析与生成查询 175

4.3.6 getFieldQuery 公共函数 181

4.4 分析器 184

4.4.1 概述 184

4.4.2 分析器的组成：分词器和过滤器 185

4.4.3 分析器的两个典型场景 187

4.4.4 索引的构建流程 188

4.4.5 QueryParse 查询流程 188

4.4.6 位置增量 190

4.5 中文分词器 195

4.5.1 概述 195

4.5.2 中文分词器的思想 196

4.5.3 sego 中文分词器 198

4.5.4 双数组前缀树算法 204

4.5.5 维特比算法 210

4.5.6 迪杰斯特拉算法 210

4.6 小结 213

第 5 章 Lucene 搜索与排名 214

5.1 背景 214

5.2 搜索结果排名 215

5.2.1 TF-IDF 模型 215

5.2.2 余弦相似性 219

5.3 过滤器 220

5.3.1 概述 220

5.3.2 过滤 220

5.3.3 CachingWrapperFilter 225

5.3.4 创建自定义过滤器 226

5.3.5 过滤与查询的区别 227

5.4 全文搜索 227

5.4.1 概述 227

5.4.2 Query、Weight 和 Scorer 对象树 228

5.4.3 搜索流程（关闭过滤器） 230

5.5 短语搜索：相关性搜索 246

5.5.1 概述 246

5.5.2 一个查询短语举例 246

5.5.3 TermPositions 与 TermDocs 250

5.5.4 PhraseQuery 类体系 250

5.5.5 PhraseScorer 工作流 251

5.5.6 MultiPhraseQuery 259

5.6 模糊搜索：利用模糊性改善搜索性能 259

5.6.1 概述 259

5.6.2 编辑距离算法 259

5.6.3 FuzzyQuery 工作流 261

5.7 小结 265

第 6 章 Lucene 的底层数据结构与算法 266

6.1 背景 266

6.2 编码与压缩算法 268

6.2.1 概述 268

6.2.2 前缀编码 268

6.2.3 增量编码 269

6.2.4 变长字节编码 270

6.3 跳表结构：分层有序链表 271

6.3.1 概述 271

6.3.2 跳表的定义与规则 272

6.3.3 从单链表到跳表 273

6.3.4 跳表的特点 274

6.3.5 frq 索引文件中的跳表设计 275

6.3.6 索引的设计思想：空间换时间 276

6.3.7 MultiLevelSkipListWriter 类的相关状态 277

6.3.8 MultiLevelSkipListWriter 类的相关操作 279

6.3.9 MultiLevelSkipListReader 类的相关状态和操作 285

6.4 ByteSliceReader 结构 288

6.4.1 概述 288

6.4.2 ByteBlockPool 数据结构 289

6.4.3 ByteBlockPool 使用数组来模拟链表 293

6.4.4 Posting 倒排列表与 ByteBlockPool 的关系 294

6.4.5 ByteSliceReader 数据结构 295

6.5 ByteBlockPool 结构：数组模拟链表 296

6.5.1 概述 296

6.5.2 数组如何模拟链表 296

6.5.3 链表与数组 298

6.5.4 线性与非线性结构 298

6.5.5 ByteBlockPool 再思考 299

6.6 小结 300

第 7 章 广告检索与定位 302

7.1 背景 302

7.2 全文索引和检索 302

7.2.1 概述 302

7.2.2 全文索引模型 303

7.2.3 检索模型 303

7.2.4 关系数据库中索引的设计 305

7.2.5 一个简单倒排索引的设计 306

7.3 位图索引 307

7.3.1 概述 307

7.3.2 位图索引结构 307

7.3.3 位图索引中的编码 309

7.3.4 位图索引的构建与查询 310

7.3.5 对倒排文本进行位图索引 313

7.4 用 Be_indexer 开源框架实现广告索引 313

7.4.1 文档类体系 313

7.4.2 FieldDesc 类体系 315

7.4.3 字典编码 315

7.4.4 Be_indexer 框架的基本流程 318

7.4.5 Be_indexer框架的倒排索引 325

7.5 程序化广告概述 326

7.5.1 程序化广告是什么？ 326

7.5.2 程序化广告系统的主要模块 327

7.6 广告检索 328

7.6.1 概述 328

7.6.2 广告选择：用布尔逻辑表达式实现 328

7.6.3 广告选择：用 DNF 实现 329

7.6.4 用 Clorisearch 开源框架实现广告检索 332

7.7 广告库存预测 342

7.7.1 概述 342

7.7.2 定向广告和重定向广告 342

7.7.3 命题逻辑基础 343

7.7.4 DNF 的应用 347

7.7.5 广告库存预测：用 DNF 算法实现 350

7.8 广告定位：用户身份图构建与搜索 351

7.8.1 概述 351

7.8.2 Cookie 352

7.8.3 同一用户在不同平台中的身份匹配：用户匹配表 354

7.8.4 演进 1：集中式 Cookie 同步技术 355

7.8.5 演进 2：用户身份图 357

7.9 广告定位：通过 DMP 帮助用户匹配正确的广告 361

7.9.1 概述 361

7.9.2 DMP 的基础知识 361

7.9.3 DMP 分段 362

7.9.4 DMP 和 DSP 的协同工作 364

7.9.5 DMP 的用户数据在 DSP 中的使用场景 364

7.10 小结 367

第 8 章 程序化广告技术 369

8.1 背景 369

8.2 广告标签模板 370

8.2.1 VAST 工作流程 371

8.2.2 VAST 格式 371

8.3 广告实时竞价 373

8.3.1 RTB 工作流程 373

8.3.2 投标请求 374

8.3.3 投标响应 378

8.4 广告实时数据 380

8.4.1 广告日志数据 380

8.4.2 广告生命周期：事件流 381

8.4.3 广告数据聚合 382

8.5 广告事件流聚合 384

8.5.1 概述 384

8.5.2 需求 384

8.5.3 解决思路：数据管道架构 385

8.5.4 方案 1 - 数据管道：Kafka 385

8.5.5 方案 2 - 数据管道：Kafka Cassandra 386

8.5.6 方案 3 - 数据管道：Kafka Spark Cassandra 387

8.5.7 方案 4 - 数据管道：Kafka Spark Cassandra Data-Version 390

8.6 广告供应链透明度分析 392

8.6.1 Ads.txt 392

8.6.2 Seller.json 394

8.6.3 供应链对象 394

8.6.4 Ads.txt、Seller.json 和供应链对象的关系 395

8.7 小结 396