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

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

第1章 搜索技术的算法
1.1 背景
1.2 字符串搜索
1.2.1 概述
1.2.2 基础字符串搜索算法：暴力搜索算法
1.2.3 中级字符串搜索算法：KMP算法
1.2.4 高级字符串搜索算法：BM算法
1.2.5 字符串精确搜索：Grep
1.2.6 字符串模糊搜索
1.3 树搜索
1.3.1 概述
1.3.2 二叉搜索树
1.3.3 2-3-4树
1.3.4 2-3-4树与红黑树的等价关系
1.3.5 红黑树操作
1.3.6 红黑树典型应用场景
1.4 图搜索
1.4.1 概述
1.4.2 图建模中，邻接矩阵和邻接表哪种结构更好？
1.4.3 DFS在图搜索和树搜索中的应用
1.4.4 DFS无向图连通分量问题
1.4.5 DFS单源路径问题
1.4.6 BFS单源（最短）路径问题
1.4.7 DFS检测无向图中的环
1.4.8 二分图检测与染色算法
1.4.9 拓扑排序
1.4.10 动态规划和递归之间的关系
1.5 小结
第2章 Lucene基础
2.1 背景
2.2 Lucene与传统关系数据库
2.2.1 Lucene与传统关系数据库的异同
2.2.2 Lucene的全文搜索机制
2.2.3 倒排索引的使用场景
2.3 Lucene与Elasticsearch
2.4 Lucene的倒排索引设计
2.4.1 倒排索引
2.4.2 Posting数据结构
2.4.3 ByteBlockPool动态数组
2.4.4 Posting与ByteBlockPool的关系
2.4.5 ThreadState结构
2.4.6 DocumentsWriter结构
2.5 Lucene的正排索引设计
2.5.1 正排索引与倒排索引
2.5.2 Lucene的正排索引与数学中的向量的关系
2.5.3 正排索引存储
2.5.4 索引数据的写流程
2.6 有效负载
2.6.1 有效负载的结构
2.6.2 有效负载的格式
2.6.3 文档权重与域权重
2.6.4 权重与有效负载
2.6.5 有效负载的应用场景
2.7 复合索引文件
2.7.1 复合索引的文件格式
2.7.2 写复合索引文件
2.8 小结
第3章 Lucene索引段
3.1 背景
3.2 不同索引结构的比较
3.2.1 MySQL：B+树
3.2.2 MySQL：哈希索引
3.2.3 Redis：跳表
3.2.4 Lucene：倒排索引
3.3 索引段的基础知识
3.3.1 概述
3.3.2 SegmentInfos容器
3.3.3 IndexReader
3.3.4 SegmentReader
3.3.5 倒排索引格式
3.3.6 索引段的读流程
3.4 索引段的合并
3.4.1 概述
3.4.2 段合并的典型问题
3.4.3 段合并的策略
3.4.4 段合并的简单流程
3.4.5 合并段内域：mergeFields
3.4.6 合并段内分词：mergeTerms
3.4.7 合并段内词向量：mergeVectors
3.5 索引段提交点与快照
3.5.1 概述
3.5.2 提交点
3.5.3 快照
3.5.4 触发快照的场景
3.6 索引段删除文档
3.6.1 概述
3.6.2 del扩展文件
3.6.3 位向量
3.6.4 索引段删除分词
3.6.5 索引段查询分词
3.7 小结
第4章 Lucene分析器
4.1 背景
4.2 Field、Token与Term概念
4.3 JavaCC与查询解析器
4.3.1 Yacc与JavaCC
4.3.2 在JavaCC中扩展正则表达式
4.3.3 JavaCC的输入文件之XX.jj
4.3.4 Lucene中Token的正则表达式定义
4.3.5 Lucene语法产生式：分析与生成查询
4.3.6 getFieldQuery公共函数
4.4 分析器
4.4.1 概述
4.4.2 分析器的组成：分词器和过滤器
4.4.3 分析器的两个典型场景
4.4.4 索引的构建流程
4.4.5 QueryParse查询流程
4.4.6 位置增量
4.5 中文分词器
4.5.1 概述
4.5.2 中文分词器的思想
4.5.3 sego中文分词器
4.5.4 双数组前缀树算法
4.5.5 维特比算法
4.5.6 迪杰斯特拉算法
4.6 小结
第5章 Lucene搜索与排名
5.1 背景
5.2 搜索结果排名
5.2.1 TF-IDF模型
5.2.2 余弦相似性
5.3 过滤器
5.3.1 概述
5.3.2 过滤
5.3.3 CachingWrapperFilter
5.3.4 创建自定义过滤器
5.3.5 过滤与查询的区别
5.4 全文搜索
5.4.1 概述
5.4.2 Query、Weight和Scorer对象树
5.4.3 搜索流程（关闭过滤器）
5.5 短语搜索：相关性搜索
5.5.1 概述
5.5.2 一个查询短语举例
5.5.3 TermPositions与TermDocs
5.5.4 PhraseQuery类体系
5.5.5 PhraseScorer工作流
5.5.6 MultiPhraseQuery
5.6 模糊搜索：利用模糊性改善搜索性能
5.6.1 概述
5.6.2 编辑距离算法
5.6.3 FuzzyQuery工作流
5.7 小结
第6章 Lucene的底层数据结构与算法
6.1 背景
6.2 编码与压缩算法
6.2.1 概述
6.2.2 前缀编码
6.2.3 增量编码
6.2.4 变长字节编码
6.3 跳表结构：分层有序链表
6.3.1 概述