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

本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。

◎ 编辑推荐：

◆理论与实践并重——本书是市面上少有的从源码角度讲解搜索引擎与程序化广告技术的图书。

◆技术与业务相结合——系统性地介绍程序化广告相关的各项业务及其用到的技术知识。

◆知识深入浅出——从基础的数据结构出发，循序渐进讲解搜索算法及其应用。

◆内容系统全面——涵盖Lucene索引创建、查询解析、搜索排名，以及底层数据结构与算法。

◆作者经验丰富——本书作者在专门提供互联网视频广告投放、预测、增值等解决方案的公司Freewheel担任广告供应方平台（Supply Side Platform，SSP）的技术负责人、软件架构师。

◆业内大咖推荐——微软Bing首席工程师、阿里P9技术总监、FreeWheel技术副总裁等多位技术专家...

(展开全部)

本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。

◎ 编辑推荐：

◆理论与实践并重——本书是市面上少有的从源码角度讲解搜索引擎与程序化广告技术的图书。

◆技术与业务相结合——系统性地介绍程序化广告相关的各项业务及其用到的技术知识。

◆知识深入浅出——从基础的数据结构出发，循序渐进讲解搜索算法及其应用。

◆内容系统全面——涵盖Lucene索引创建、查询解析、搜索排名，以及底层数据结构与算法。

◆作者经验丰富——本书作者在专门提供互联网视频广告投放、预测、增值等解决方案的公司Freewheel担任广告供应方平台（Supply Side Platform，SSP）的技术负责人、软件架构师。

◆业内大咖推荐——微软Bing首席工程师、阿里P9技术总监、FreeWheel技术副总裁等多位技术专家鼎力推荐。

◎ 内容简介：

本书首先从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，以及它们的典型应用场景。其次详细分析全文搜索引擎工具包Lucene，包括其索引结构、分析器、搜索与排名机制，以及Lucene的底层数据结构与算法。最后，本书从搜索技术过渡到程序化广告，介绍程序化广告系统中的各个模块和工作机制，包含广告检索、广告库存预测、广告定位、广告标签模板、广告实时竞价、广告实时数据、广告事件流聚合、广告供应链透明度等内容。

◎ 专家推荐：

本书深入浅出，先讲解基础的搜索算法，再过渡到行业广为应用的产品级搜索引擎Lucene的底层原理，还介绍了众多辅助搜索的技术，如分词、索引、相关性计算、布尔逻辑表达式等。通过阅读本书，读者能够学习构造一个基础搜索系统的完整技术栈，并且可以从理论上对比不同的技术路线、认识不同算法之间的差异，让实践过程事半功倍。

——陈甫鸼

Microsoft Bing团队首席工程师（Principal Engineer）

本书作者是一名“互联网老兵”，一名在程序化广告行业工作多年的资深程序员，一名广告供应方平台的架构师，他对搜索算法有深刻的理解和把握。本书从基础的字符串匹配算法出发，到程序化广告交易平台的实战，是学习搜索技术和程序化广告系统开发的优秀读物。

——党政法

FreeWheel技术副总裁（Engineering Vice President）

作为一名写了多年“增删改查”的“业务开发者”，我在阅读本书之前从未发现程序化广告的业务如此有趣。通过阅读本书，你不仅可以了解高级的技术技巧、实现高性能的搜索引擎内核，还可以知道这对于上层的广告业务意味着什么。

——陶文

曾任滴滴首席架构师

在互联网世界里，搜索和广告是一个商业闭环中非常重要的组成部分，与之相关的技术也自然而然地成为互联网从业人员需要具备的重要知识。本书从专业技术从业人员的角度深入剖析搜索和程序化广告的技术体系、技术细节以及典型应用场景，相信读者学习和实践完本书的内容后一定会有所收获。

——王强

FreeWheel技术副总裁（Engineering Vice President）

本书深入解析了搜索和广告领域的核心原理和技术，包括大量的数据结构、算法和开源类库。除了理论之外，本书还包含大量示例代码，可以让读者更好地理解和应用这些技术。本书深入浅出，具有很强的实用性和指导性，对于想要深入学习搜索引擎和程序化广告技术的读者来说是一本非常有价值的参考书。

——徐宁

阿里菜鸟国际物流技术总监（P9）

搜索引擎技术和程序化广告技术对于设计一个良好的广告引擎非常重要。本书作者在这两个领域都有多年的开发经验，并且非常善于总结和乐于分享。所以我相信，无论你是搜索或广告行业的开发人员、产品设计师，或者仅仅是想了解搜索和程序化广告的相关技术，本书都能让你有所收获。

——张晗

FreeWheel技术副总裁（Engineering Vice President）

第 1 章 搜索技术的算法 1
1.1 背景 1
1.2 字符串搜索 2
1.2.1 概述 2
1.2.2 基础字符串搜索算法：暴力搜索算法 2
1.2.3 中级字符串搜索算法：KMP 算法 4
· · · · · · (更多)

第 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
· · · · · · (收起)