（1）理論與實踐並重——本書是市面上少有的從源碼角度講解搜索引擎與程序化廣告技術的圖書。（2）技術與業務相結合——繫統性地介紹程序化廣告相關的各項業務及其用到的技術知識。（3）知識深入淺出——從基礎的數據結構出發，循序漸進講解搜索算法及其應用。（4）內容繫統全面——涵蓋Lucene索引創建、查詢解析、搜索排名，以及底層數據結構與算法。（5）作者經驗豐富——本書作者在專門提供互聯網視頻廣告投放、預測、增值等解決方案的公司Freewheel擔任廣告供應方平臺（Supply Side Plat等

●第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.2 ting數據結構80
2.4.3ByteBlockPool動態數組81
2.4.4 ting與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.3Term itions與TermDocs250
5.5.4PhraseQuery類體繫250
5.5.5PhraseScorer工作流251
5.5.6 ltiPhraseQuery259
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.7 ltiLevelSkipListWriter類的相關狀態277
6.3.8 ltiLevelSkipListWriter類的相關操作279
6.3.9 ltiLevelSkipListReader類的相關狀態和操作285
6.4ByteSliceReader結構288
6.4.1概述288
6.4.2ByteBlockPool數據結構289
6.4.3ByteBlockPool使用數組來模擬鏈表293
6.4.4 ting倒排列表與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

本書從源碼的角度講解搜索技術與程序化廣告繫統，將技術與業務結合、理論與實踐並重，幫助讀者更好地理解並掌握相關知識。
本書首先從基礎的數據結構出發，帶領讀者深入理解線性結構、樹結構和圖結構的搜索算法，以及它們的典型應用場景。其次詳細分析全文搜索引擎工具包Lucene，包括其索引結構、分析器、搜索與排名機制，以及Lucene的底層數據結構與算法。最後，本書從搜索技術過渡到程序化廣告，介紹程序化廣告繫統中的各個模塊和工作機制，包含廣告檢索、廣告庫存預測、廣告定位、廣告標簽模板、廣告實時競價、廣告實時數據、廣告事件流聚合、廣告供應鏈透明度等內容。
本書適合從事搜索技術、程序化廣告相關工作或對相關內容感興趣的軟件開發人員閱讀。在閱讀本書之前，讀者需要具備基本的編程能力。

楊敏 著