內容簡介

本書從源碼的角度講解搜索技術與程式化廣告系統，將技術與業務結合、理論與實踐並重，幫助讀者更好地理解並掌握相關知識。

本書首先從基礎的數據結構出發，帶領讀者深入理解線性結構、樹結構和圖結構的搜索演算法，以及它們的典型應用場景。其次詳細分析全文檢索搜尋引擎工具包Lucene，包括其索引結構、分析器、搜索與排名機制，以及Lucene的底層數據結構與演算法。最後，本書從搜索技術過渡到程式化廣告，介紹程式化廣告系統中的各個模組和工作機制，包含廣告檢索、廣告庫存預測、廣告定位、廣告標籤範本、廣告即時競價、廣告即時數據、廣告事件流聚合、廣告供應鏈透明度等內容。

本書適合從事搜索技術、程式化廣告相關工作或對相關內容感興趣的軟體發展人員閱讀。在閱讀本書之前，讀者需要具備基本的程式設計能力。

作者介紹

楊敏，畢業于浙江大學電腦科學與技術專業，目前就職於一家專門提供互聯網視頻廣告投放、預測和增值等解決方案的公司——Freewheel，擔任廣告供應方平臺（Supply Side Platform，SSP）的技術負責人、軟體架構師。他曾在美國道富銀行、微軟、Thought works等公司工作，擁有豐富的程式化廣告產品開發與設計經驗。他曾參與或主持開發過的專案有：·美國道富銀行的普林斯頓金融系統；·普華永道全球派遣服務軟體系統；·微軟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

看更多