自製搜尋引擎 自制搜索引擎

山田浩之

信息工程學博士。
先後於日本IBM、雅虎從事分佈式搜索引擎的研發工作。
目前在東京大學生產技術研究所從事高性能並行數據庫的研發工作。

　　
末永匡

開源搜索引擎Senna/Groonga的開發者。
每天都在奮鬥，夢想著能創建一個更加自由、更加無拘無束的，而不是一家獨大的應用程序平台。

　　
胡屹

多年從事Web開發工作。
熱愛編程，關注設計模式，致力於提升軟件開發的質量。
曾獲得SCJP和PHP ZCE證書。
譯有《計算機是怎樣跑起來的》。

目錄
第1章搜索引擎是如何工作的1
1-1理解搜索引擎的構成3
什麼是搜索引擎3
構成搜索引擎的組件4
與搜索引擎相關的組件5
1-2實現了快速全文搜索的索引結構7
全文搜索的兩種方法7
倒排索引的結構8
倒排索引的構建方法9
倒排索引中的術語10
1-3深入理解倒排索引12
倒排索引=詞典+倒排文件12
從倒排索引中查找單詞13
將單詞的位置信息加入倒排文件中13
從倒排索引中查找短語14
1-4製作中文文檔的倒排索引16
分割中文句子的方法16
權衡分割方法17
1-5實現倒排索引19
實現詞典19
實現倒排文件22
1-6使用倒排索引進行檢索24
布爾檢索24
使用倒排索引的檢索處理流程24
關聯度的計算方法26
信息檢索中的檢索27
1-7構建倒排索引29
使用內存構建倒排索引29
使用二級存儲構建倒排索引29
靜態索引構建和動態索引構建32
1-8準備要檢索的文檔34
收集數據34
數據規範化35

第2章準備全文搜索引擎的檢索樣本37
2-1全文搜索引擎wiser 39
wiser的構成39
準備用於檢索的文檔40
2-2安裝wiser 42
構建wiser 42
啟動wiser 43
解壓縮Wikipedia的副本44
2-3運行wiser 45
構建倒排索引45
使用倒排索引查詢46
比較grep和wiser的運行速度46

第3章構建倒排索引49
3-1複習有關倒排索引的知識51
提取詞元51
為每個詞元創建倒排列表53
3-2構建倒排索引54
在存儲器上創建倒排列表54
倒排列表和倒排文件的數據結構54
從源代碼級別梳理倒排索引的構建順序56
進一步閱讀源代碼59
專欄根據實際情況設計搜索引擎（系統） 68

第4章開始檢索吧71
4-1檢索處理的大致流程73
充分理解檢索處理的流程73
4-2使用倒排索引進行檢索75
從源代碼級別梳理檢索處理的流程75
解讀split_query_to_tokens()函數的具體實現76
使用具體示例加深對檢索處理流程的理解77
解讀函數search_docs()的實現細節80
解讀函數search_phrase()的實現84
專欄如何實現標籤檢索88

第5章壓縮倒排索引89
5-1壓縮的基礎知識90
壓縮倒排索引的好處90
專欄壓縮的目的90
倒排索引的壓縮方法91
倒排文件的壓縮方法91
壓縮的原理94
5-2實現wiser中的壓縮功能97
壓縮功能源代碼的概要97
了解無需進行壓縮時的操作99
抓住Golomb編碼的要點101
解讀Golomb編碼中的編碼處理105
解讀Golomb編碼的解碼處理108

第6章挑戰wiser的優化及參數的調整113
6-1提高檢索處理的效率115
優化檢索處理115
將查詢分割為無重複部分的詞元序列116
6-2禁用短語檢索119
分析對2字符的字符串進行檢索時的行為119
分析對3字符的字符串進行檢索時的行為120
6-3改變檢索結果的輸出順序122
作為檢索結果排序核心的指標122
按照文檔大小降序排列的檢索結果124
專欄排名欺詐128
6-4讓1個字符的查詢也能檢索出結果29
獲取以特定字符開頭的詞元的列表129
合併檢索到的結果131
專欄如何實現相似文檔的檢索131
6-5調整控制倒排索引更新的緩衝區容量133
確認由緩衝區容量的差異帶來的不同效果133
用sar命令分析負載134
6-6調整隻有英文字母的詞元的分割方法135
如何避免用英文單詞檢索時準確率下降的問題135
如何判斷某字符是否屬於索引對象135
修改負責分割詞元的函數136
6-7確認壓縮的效果138
觀察Golomb編碼的效果138
對比壓縮啟用前後的索引大小138
專欄避免濫用全文搜索引擎139

第7章為今後更加深入的學習做準備141
7-1 wiser沒能實現的功能143
倒排索引之外的全文搜索索引143
高效處理大規模數據的存儲器143
利用緩存提高檢索的速度143
使用各種各樣的壓縮方法144
優化搜索結果的排名144
調整準確率和召回率145
降低檢索結果排序處理的負載147
並行處理147
結合對屬性的篩選過濾148
分面搜索148
專欄時延和吞吐量149
7-2全文搜索引擎Groonga的特點150
通過詞元的部分一致檢索提升召回率150
使用內存映射文件151
片段152
專欄宣傳活動的重要性152
7-3實現出考慮到用戶意圖的搜索引擎153
引入停用詞153
應對詞素解析的錯誤153
專欄斷句錯誤154
處理全角字符和半角字符155
對查詢進行歸一化156
留意布爾檢索的解析過程156
通過詞素解析器適當地解析查詢157
對錯誤的輸入進行修正157
輸入補全158
建議用戶檢索相關的關鍵詞159
7-4收集、提取文檔時的要點160
製作爬蟲時的處理要點160
在提取文本時需要處理的要點163
Appendix附錄165
A -1深度話題166
近幾年的壓縮方法166
動態索引構建169
分佈式索引174
A-2 wiser中的文本提取和存儲178
用於處理XML的2種API——DOM和SAX 178
提取文檔的標題和正文179
掌握狀態的遷移182
構建文檔數據庫187
後記191