[
-
内容大纲
本书从源码的角度讲解搜索技术与程序化广告系统，将技术与业务结合、理论与实践并重，帮助读者更好地理解并掌握相关知识。
本书首先从基础的数据结构出发，带领读者深入理解线性结构、树结构和图结构的搜索算法，以及它们的典型应用场景。其次详细分析全文搜索引擎工具包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 概述
6.3.2 跳表的定义与规则
6.3.3 从单链表到跳表
6.3.4 跳表的特点
6.3.5 frq索引文件中的跳表设计
6.3.6 索引的设计思想：空间换时间
6.3.7 MultiLevelSkipListWriter类的相关状态
6.3.8 MultiLevelSkipListWriter类的相关操作
6.3.9 MultiLevelSkipListReader类的相关状态和操作
6.4 ByteSliceReader结构
6.4.1 概述
6.4.2 ByteBlockPool数据结构
6.4.3 ByteBlockPool使用数组来模拟链表
6.4.4 Posting倒排列表与ByteBlockPool的关系
6.4.5 ByteSliceReader数据结构
6.5 ByteBlockPool结构：数组模拟链表
6.5.1 概述
6.5.2 数组如何模拟链表
6.5.3 链表与数组
6.5.4 线性与非线性结构
6.5.5 ByteBlockPool再思考
6.6 小结
第7章 广告检索与定位
7.1 背景
7.2 全文索引和检索
7.2.1 概述
7.2.2 全文索引模型
7.2.3 检索模型
7.2.4 关系数据库中索引的设计
7.2.5 一个简单倒排索引的设计
7.3 位图索引
7.3.1 概述
7.3.2 位图索引结构
7.3.3 位图索引中的编码
7.3.4 位图索引的构建与查询
7.3.5 对倒排文本进行位图索引
7.4 用Be_indexer开源框架实现广告索引
7.4.1 文档类体系
7.4.2 FieldDesc类体系
7.4.3 字典编码
7.4.4 Be_indexer框架的基本流程
7.4.5 Be_indexer框架的倒排索引
7.5 程序化广告概述
7.5.1 程序化广告是什么？
7.5.2 程序化广告系统的主要模块
7.6 广告检索
7.6.1 概述
7.6.2 广告选择：用布尔逻辑表达式实现
7.6.3 广告选择：用DNF实现
7.6.4 用Clorisearch开源框架实现广告检索
7.7 广告库存预测
7.7.1 概述
7.7.2 定向广告和重定向广告
7.7.3 命题逻辑基础
7.7.4 DNF的应用
7.7.5 广告库存预测：用DNF算法实现
7.8 广告定位：用户身份图构建与搜索
7.8.1 概述
7.8.2 Cookie
7.8.3 同一用户在不同平台中的身份匹配：用户匹配表
7.8.4 演进1：集中式Cookie同步技术
7.8.5 演进2：用户身份图
7.9 广告定位：通过DMP帮助用户匹配正确的广告
7.9.1 概述
7.9.2 DMP的基础知识
7.9.3 DMP分段
7.9.4 DMP和DSP的协同工作
7.9.5 DMP的用户数据在DSP中的使用场景
7.10 小结
第8章 程序化广告技术
8.1 背景
8.2 广告标签模板
8.2.1 VAST工作流程
8.2.2 VAST格式
8.3 广告实时竞价
8.3.1 RTB工作流程
8.3.2 投标请求
8.3.3 投标响应
8.4 广告实时数据
8.4.1 广告日志数据
8.4.2 广告生命周期：事件流
8.4.3 广告数据聚合
8.5 广告事件流聚合
8.5.1 概述
8.5.2 需求
8.5.3 解决思路：数据管道架构
8.5.4 方案1-数据管道：Kafka
8.5.5 方案2-数据管道：Kafka+Cassandra
8.5.6 方案3-数据管道：Kafka+Spark+Cassandra
8.5.7 方案4-数据管道：Kafka+Spark+Cassandra+Data-Version
8.6 广告供应链透明度分析
8.6.1 Ads.txt
8.6.2 Seller.json
8.6.3 供应链对象
8.6.4 Ads.txt、Seller.json和供应链对象的关系
8.7 小结
同类热销排行榜
[an error occurred while processing this directive]推荐书目
-
孩子你慢慢来/人生三书 华人世界率性犀利的一枝笔，龙应台独家授权《孩子你慢慢来》20周年经典新版。她的《...
-
时间简史(插图版) 相对论、黑洞、弯曲空间……这些词给我们的感觉是艰深、晦涩、难以理解而且与我们的...
-
本质(精) 改革开放40年，恰如一部四部曲的年代大戏。技术突变、产品迭代、产业升级、资本对接...