前言

作为世界上使用人数最多的搜索引擎之一，也是体量最大的广告商之一，谷歌的成功不在于追求广告投放的数量，而是注重广告投放的效果。程序化广告改变了传统的广告投放模式。程序化广告是指利用技术手段进行广告交易和管理。广告商可以程序化地采购媒体资源，利用算法和技术自动实现对广告目标受众的精准定位，极大地提升了广告投放的效率和效果。

工欲善其事，必先利其器。在开始学习程序化广告之前，需要先学习搜索技术，因为搜索技术是程序化广告中的核心技术之一。程序化广告系统中的很多技术源自搜索技术，比如索引、检索和数据分类与定位。信息时代，人们在数据的海洋中快速准确定位信息的需求量越来越大，对程序化广告而言也是如此。程序化广告需要根据分类的数据对目标受众进行定位，通过灵活、快速的搜索返回匹配的广告。

大多数搜索引擎的底层实现技术是相通的。简单来说，实现一个搜索引擎需要掌握的基本知识不外乎如下几个方面：

● 构建倒排索引；

● 使用TF-IDF模型创建文档权重；

● 搜索文档，比如使用常用的跳表、二叉搜索树或者红黑树进行查询，查询语句中可以包含AND、OR和NOT布尔逻辑运算符；

● 使用向量点积计算待查询内容与文档之间的相似度；

● 按相似度由高到低的顺序为用户返回搜索到的文档。

实现一个程序化广告系统所使用的很多技术和实现一个搜索引擎所使用的技术是相通的，比如：

● 构建广告活动的数据及索引；

● 检索广告活动，查询语句中可以包含AND、OR和NOT布尔逻辑运算符，充分表达广告的流量特征；

● 广告过滤与排序。

本书从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，及其各自的典型应用场景。这些数据结构和算法是搜索引擎与程序化广告领域的核心技术，对于构建高效的搜索引擎和程序化广告系统至关重要。

接着，本书介绍Lucene，这是一个提供索引和搜索功能的开源库，可以作为搜索引擎的框架。本书详细分析Lucene的索引结构、分析器、搜索与排名机制，以及Lucene的底层数据结构与算法，帮助读者深入理解Lucene，为讲解程序化广告系统奠定基础。

最后，本书以与搜索技术密切相关的广告检索与定位技术作为切入点，进入程序化广告的主题，介绍程序化广告系统中的各个模块和工作机制，包含广告检索、广告库存预测、广告定位、广告标签模板、广告实时竞价、广告实时数据、广告事件流聚合、广告供应链透明度等内容，帮助读者全面掌握程序化广告技术。

本书在讲解技术内容的过程中，辅以程序源码，其中一部分来自Lucene开源代码，另一部分则是作者自己编写的代码。希望这种理论与实践结合的方式能让读者学有所得、学有所用。

读者对象

本书适合所有软件开发人员阅读，尤其是从事搜索技术、搜索引擎、程序化广告相关工作或对相关内容感兴趣的开发者，包括搜索引擎工程师、程序化广告系统开发工程师、算法工程师等。本书也适合计算机相关专业的学生阅读。在阅读本书之前，读者需要具备基本的编程能力。

章节速览

本书主要由三个部分组成：第1章讲解的搜索技术的算法，第2～5章讲解的Lucene搜索引擎框架，以及第7～8章讲解的程序化广告技术。读者可以根据自己的兴趣和需求单独阅读这3个部分，但更加推荐根据本书的组织方式进行阅读。

第1章，搜索技术的算法。本章介绍各种数据结构的搜索算法。首先介绍字符串搜索算法，包含暴力搜索算法、KMP算法和BM算法。然后介绍二叉搜索树，并重点研究2-3-4树与红黑树的等价关系。最后介绍图搜索算法，主要通过DFS和BFS算法讨论如何解决一些典型的实际应用问题。

第2章，Lucence基础。本章讨论Lucene搜索引擎的基础知识。首先介绍Lucene和传统关系数据库的异同，其次深入分析倒排索引和正排索引的机制，接着讨论有效负载机制，最后分析复合索引文件机制。

第3章，Lucene索引段。本章介绍Lucene索引段的相关知识。索引由多个段组成，每个段包含各自独立的文档子集。要想读懂Lucene源码，首先要充分理解文档子集的4类文件格式：tis、tii、frq和prx。 本章首先剖析索引段的合并策略与实现流程，然后讨论索引段的提交点与快照机制，最后分析索引段删除文档机制。

第4章，Lucene分析器。本章介绍Lucene的分析器机制。Lucene通过自定义分词模块来实现对输入数据的分析与存储。本章首先讨论分析器的工作流程，然后借助一个中文分词器来详细解析双数组前缀树与维特比算法的应用。

第5章，Lucene搜索与排名。本章深入分析Lucene的搜索与排名机制。首先介绍TF-IDF模型和余弦相似度，其次讨论过滤器的工作机制，接着讨论全文搜索的工作流程，包含解析查询文本并生成布尔逻辑表达式、定位分词词典索引并返回倒排列表、计算倒排列表中的文档相关度、收集器收集目标文档集合并返回，最后介绍短语搜索和模糊搜索的工作机制。

第6章，Lucene的底层数据结构与算法。本章深入分析Lucene的底层数据结构与算法，包含编码与压缩算法、跳表结构、ByteSliceReader结构和ByteBlockPool结构，以期展现Lucene的设计之美，并帮助读者更好地理解Lucene。

第7章，广告检索与定位。本章主要介绍与广告检索与定位相关的技术。首先介绍全文索引和检索模型，其次介绍位图索引及其应用，接着讲解如何用Be_indexer开源框架实现广告索引，随后对程序化广告系统进行概述，并分析广告检索与广告库存预测的关键技术——DNF算法和倒排索引，最后介绍广告定位中的常见问题——用户唯一性识别问题，即如何进行用户身份图的构建与搜索。

第8章，程序化广告技术。本章介绍程序化广告系统的相关技术，包含广告标签模板、广告实时竞价、广告实时数据，以及广告事件流聚合，并通过一个典型案例进行深入分析。最后分析广告供应链透明度问题及其解决方案，为程序化广告系统提供安全可靠的服务。

关于勘误

写作之难，在于把网状的思考用树状的结构体现在线性展开的语句中。由于个人能力有限，以及编写时间仓促，书中难免会出现一些错误或不准确的地方，恳请读者为我提供建议和指正，我很期待得到你最真挚的反馈。读者可以发送电子邮件到searchrtb@gmail.com与我联系。

致谢

感谢人民邮电出版社的编辑龚昕岳老师、陈冀康老师等众多工作人员的辛勤工作，使得本书的出版成为可能。

感谢我亲爱的家人，特别是我深爱的妻子阿丽，尽管她对计算机编程世界完全不了解，但正是她的理解、包容和默默支持，才能让我专心完成这本书。

感谢每一个在我成长道路上帮助过我的人。谨以此书献给众多热爱搜索技术的朋友们！

杨敏　　

2023年春于北京