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

（1）理论与实践并重——本书是市面上少有的从源码角度讲解搜索引擎与程序化广告技术的图书。 （2）技术与业务相结合——系统性地介绍程序化广告相关的各项业务及其用到的技术知识。 （3）知识深入浅出——从基础的数据结构出发，循序渐进讲解搜索算法及其应用。 （4）内容系统全面——涵盖Lucene索引创建、查询解析、搜索排名，以及底层数据结构与算法。 （5）作者经验丰富——本书作者在专门提供互联网视频广告投放、预测、增值等解决方案的公司Freewheel担任广告供应方平台（Supply Side Platform，SSP）的技术负责人、软件架构师。 （6）业内大咖推荐——微软Bing首席工程师、阿里P9技术总监、FreeWheel技术副总裁等多位技术专家鼎力推荐。

本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。
本书首先从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，以及它们的典型应用场景。其次详细分析全文搜索引擎工具包Lucene，包括其索引结构、分析器、搜索与排名机制，以及Lucene的底层数据结构与算法。最后，本书从搜索技术过渡到程序化广告，介绍程序化广告系统中的各个模块和工作机制，包含广告检索、广告库存预测、广告定位、广告标签模板、广告实时竞价、广告实时数据、广告事件流聚合、广告供应链透明度等内容。
本书适合从事搜索技术、程序化广告相关工作或对相关内容感兴趣的软件开发人员阅读。在阅读本书之前，读者需要具备基本的编程能力。

杨敏，毕业于浙江大学计算机科学与技术专业，目前就职于一家专门提供互联网视频广告投放、预测和增值等解决方案的公司——Freewheel，担任广告供应方平台（Supply Side Platform，SSP）的技术负责人、软件架构师。他曾在美国道富银行、微软、Thoughtworks等公司工作，拥有丰富的程序化广告产品开发与设计经验。他曾参与或主持开发过的项目有： ·美国道富银行的普林斯顿金融系统； ·普华永道全球派遣服务软件系统； ·微软SharePoint平台的搜索系统； ·Freewheel的广告供应方平台Stickyads.tv。 他目前专注于Python/Java虚拟机、分布式搜索引擎Elasticsearch、MySQL内核等相关技术领域的研究。

第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字符串准确搜索：Grep12
1.2.6字符串模糊搜索12
1.3树搜索19
1.3.1概述19
1.3.2二叉搜索树21
1.3.32-3-4树22
1.3.42-3-4树与红黑树的等价关系28
1.3.5红黑树操作34
1.3.6红黑树典型应用场景50
1.4图搜索50
1.4.1概述50
1.4.2图建模中，邻接矩阵和邻接表哪种结构更好？51
1.4.3DFS在图搜索和树搜索中的应用53
1.4.4DFS无向图连通分量问题55
1.4.5DFS单源路径问题58
1.4.6BFS单源（最短）路径问题61
1.4.7DFS检测无向图中的环64
1.4.8二分图检测与染色算法66
1.4.9拓扑排序68
1.4.10动态规划和递归之间的关系72
1.5小结73
第2章Lucene基础75
2.1背景75
2.2Lucene与传统关系数据库76
2.2.1Lucene与传统关系数据库的异同76
2.2.2Lucene的全文搜索机制77
2.2.3倒排索引的使用场景78
2.3Lucene与Elasticsearch79
2.4Lucene的倒排索引设计80
2.4.1倒排索引80
2.4.2Posting数据结构80
2.4.3ByteBlockPool动态数组81
2.4.4Posting与ByteBlockPool的关系83
2.4.5ThreadState结构84
2.4.6DocumentsWriter结构85
2.5Lucene的正排索引设计92
2.5.1正排索引与倒排索引92
2.5.2Lucene的正排索引与数学中的向量的关系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.1MySQL：B+树109
3.2.2MySQL：哈希索引109
3.2.3Redis：跳表109
3.2.4Lucene：倒排索引111
3.3索引段的基础知识112
3.3.1概述112
3.3.2SegmentInfos容器113
3.3.3IndexReader116
3.3.4SegmentReader118
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合并段内域：mergeFields135
3.4.6合并段内分词：mergeTerms143
3.4.7合并段内词向量：mergeVectors154
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.2del扩展文件160
3.6.3位向量162
3.6.4索引段删除分词164
3.6.5索引段查询分词165
3.7小结166
第4章Lucene分析器167
4.1背景167
4.2Field、Token与Term概念168
4.3JavaCC与查询解析器170
4.3.1Yacc与JavaCC170
4.3.2在JavaCC中扩展正则表达式171
4.3.3JavaCC的输入文件之XX.jj172
4.3.4Lucene中Token的正则表达式定义173
4.3.5Lucene语法产生式：分析与生成查询175
4.3.6getFieldQuery公共函数181
4.4分析器184
4.4.1概述184
4.4.2分析器的组成：分词器和过滤器185
4.4.3分析器的两个典型场景187
4.4.4索引的构建流程188
4.4.5QueryParse查询流程188
4.4.6位置增量190
4.5中文分词器195
4.5.1概述195
4.5.2中文分词器的思想196
4.5.3sego中文分词器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.1TF-IDF模型215
5.2.2余弦相似性219
5.3过滤器220
5.3.1概述220
5.3.2过滤220
5.3.3CachingWrapperFilter225
5.3.4创建自定义过滤器226
5.3.5过滤与查询的区别227
5.4全文搜索227
5.4.1概述227
5.4.2Query、Weight和Scorer对象树228
5.4.3搜索流程（关闭过滤器）230
5.5短语搜索：相关性搜索246
5.5.1概述246
5.5.2一个查询短语举例246
5.5.3TermPositions与TermDocs250
5.5.4PhraseQuery类体系250
5.5.5PhraseScorer工作流251
5.5.6MultiPhraseQuery259
5.6模糊搜索：利用模糊性改善搜索性能259
5.6.1概述259
5.6.2编辑距离算法259
5.6.3FuzzyQuery工作流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.5frq索引文件中的跳表设计275
6.3.6索引的设计思想：空间换时间276
6.3.7MultiLevelSkipListWriter类的相关状态277
6.3.8MultiLevelSkipListWriter类的相关操作279
6.3.9MultiLevelSkipListReader类的相关状态和操作285
6.4ByteSliceReader结构288
6.4.1概述288
6.4.2ByteBlockPool数据结构289
6.4.3ByteBlockPool使用数组来模拟链表293
6.4.4Posting倒排列表与ByteBlockPool的关系294
6.4.5ByteSliceReader数据结构295
6.5ByteBlockPool结构：数组模拟链表296
6.5.1概述296
6.5.2数组如何模拟链表296
6.5.3链表与数组298
6.5.4线性与非线性结构298
6.5.5ByteBlockPool再思考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.2FieldDesc类体系315
7.4.3字典编码315
7.4.4Be_indexer框架的基本流程318
7.4.5Be_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.4DNF的应用347
7.7.5广告库存预测：用DNF算法实现350
7.8广告定位：用户身份图构建与搜索351
7.8.1概述351
7.8.2Cookie352
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.2DMP的基础知识361
7.9.3DMP分段362
7.9.4DMP和DSP的协同工作364
7.9.5DMP的用户数据在DSP中的使用场景364
7.10小结367
第8章程序化广告技术369
8.1背景369
8.2广告标签模板370
8.2.1VAST工作流程371
8.2.2VAST格式371
8.3广告实时竞价373
8.3.1RTB工作流程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-数据管道：Kafka385
8.5.5方案2-数据管道：Kafka+Cassandra386
8.5.6方案3-数据管道：Kafka+Spark+Cassandra387
8.5.7方案4-数据管道：Kafka+Spark+Cassandra+Data-Version390
8.6广告供应链透明度分析392
8.6.1Ads.txt392
8.6.2Seller.json394
8.6.3供应链对象394
8.6.4Ads.txt、Seller.json和供应链对象的关系395
8.7小结396