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

图书标准信息

• 作者 杨敏
• 出版社 人民邮电出版社
• 出版时间 2023-09
• 版次 1
• ISBN 9787115617002
• 定价 109.80元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 396页
• 字数 540千字

【内容简介】

本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。
  本书首先从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，以及它们的典型应用场景。其次详细分析全文搜索引擎工具包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 字符串精确搜索：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