《管理海量數據（壓縮索引和查詢第2版經典再現全新修訂版）》編著者威頓、莫夫特、貝爾。
海量信息的存儲、壓縮、檢索一直是令程序員們頭疼的問題，但它們的確是某些應用程序必須實現的關鍵功能。本書就是關於這個技術主題的理論巨著，並且解說實際問題，全面討論了技術主題涉及的各方面。三位作者為本書第二版添加不少新內容，包括*近的新技術，比如字組分類、新索引技術、新無損壓縮策略等等。本書全面地綜述了文本和圖像壓縮、索引和查詢技術。相關算法的發展歷史及其面臨的實際難題、該算法的不足和特別解決方案，在本書中都有詳細的論述。

《管理海量數據（壓縮索引和查詢第2版經典再 現全新修訂版）》編著者威頓、莫夫特、貝爾。 《管理海量數據（壓縮索引和查詢第2版經典再 現全新修訂版）》是斯坦福大學信息檢索和挖掘課程 的首選教材之一，並已成為全球主要大學信息檢索的 主要教材。本書理論和實踐並重，深入淺出地給出了 海量信息數據處理的整套解決方案，包括壓縮、索引 和查詢的方方面面。其最大的特色在於不僅僅滿足信 息檢索理論學習的需要，更重要的是給出了實踐中可 能面對的各種問題及其解決方法。 本書作為斯坦福大學信息檢索課程的教材之一， 具有一定的閱讀難度，主要面向信息檢索專業高年級 本科生和研究生、搜索引擎業界的專業技術人員和從 事海量數據處理相關專業的技術人員。

第1章 概覽 1
1.1 文檔數據庫（document databases） 7
1.2 壓縮（compression） 10
1.3 索引（indexes） 12
1.4 文檔索引 16
1.5 MG海量文檔管理繫統 20
第2章 文本壓縮 23
2.1 模型 26
2.2 自適應模型 29
2.3 哈夫曼編碼 32
範式哈夫曼編碼 38
計算哈夫曼編碼長度 44
總結 52
2.4 算術編碼 52
算術編碼是如何工作的 53
實現算術編碼 57
保存累積計數 60
2.5 符號模型 61
部分匹配預測 62
塊排序壓縮 65
動態馬爾科夫壓縮 69
基於單字的壓縮 72
2.6 字典模型 73
自適應字典編碼器的LZ77繫列 75
LZ77的Gzip變體 78
自適應字典編碼器的LZ78繫列 80
LZ78的LZW變體 82
2.7 同步 84
創造同步點 85
自同步編碼 87
2.8 性能比較 90
壓縮性能 92
壓縮速度 95
其他性能方面的考慮 98
第3章 索引 99
3.1 樣本文檔集合 103
3.2 倒排文件索引 107
3.3 壓縮倒排文件 112
無參模型（Nonparameterized models） 114
全局貝努裡模型 117
全局觀測頻率模型（Global observed frequency model） 120
局部貝努裡模型（Local Bernoulli model） 121
有偏貝努裡模型（Skewed Bernoulli model） 122
局部雙曲模型（Local hyperbolic model） 124
局部觀測頻率模型（Local observed frequency model） 125
上下文相關壓縮（Context-sensitive compression） 127
3.4 索引壓縮方法的效果 129
3.5 簽名文件和位圖 131
簽名文件 132
位片簽名文件（Bitsliced signature files） 136
簽名文件分析 141
位圖 144
簽名文件和位圖的壓縮 145
3.6 索引方法的比較 148
3.7 大小寫折疊、詞根化和停用詞 150
大小寫折疊 151
詞根化 151
影響索引長度的因素 152
停用詞（stop word） 153
第4章 查詢 157
4.1 訪問字典的方法 161
訪問數據結構 162
前端編碼（Front coding） 165
*小**哈希函數 168
**哈希函數的設計 171
基於磁盤的字典存儲 176
4.2 部分指定的查詢術語 177
字符串暴力匹配（Brute-force string matching） 177
用n-gram索引 178
循環字典（Rotated lexicon） 180
4.3 布爾查詢（BOOLEAN QUERY ） 182
合取查詢（conjunctive query） 182
術語處理順序 183
隨機訪問和快速查找 185
分塊倒排索引 187
非合取查詢（Nonconjunctive Query） 190
4.4 信息檢索和排名 191
坐標匹配（Coordinate matching） 191
內積相似度 192
向量空間模型 197
4.5 檢索效果評價 200
召回率和**率 200
召回率——**率曲線 203
TREC項目 204
萬維網搜索（World Wide Web Searching） 208
其他有效性評價方法 211
4.6 餘弦法實現 212
文檔內頻率 212
餘弦值的計算方法 216
文檔權重所需的內存 217
累加器內存 222
快速查詢處理 224
按頻率排序的索引 225
排序 228
4.7 交互式檢索 232
相關性反饋 232
概率模型 235
4.8 分布式檢索 237
第5章 索引構造 243
計算模型 246
索引構造方法概覽 247
5.1 基於內存的倒排 248
5.2 基於排序的倒排 251
5.3 索引壓縮 255
壓縮臨時文件 256
多路歸並 259
原地多路歸並 260
5.4 壓縮的內存內倒排 266
大內存倒排 266
基於字典的切分（Lexicon-based partitioning） 271
基於文本的切分 273
5.5 倒排方法的比較 276
5.6 構造簽名文件和位圖 277
5.7 動態文檔集合 279
擴展文本（Expanding the text） 279
索引擴展（Expanding the index） 280
第6章 圖像壓縮 287
6.1 圖像類型 288
6.2 CCITT二值圖像的傳真標準 292
6.3 二值圖像的上下文壓縮 296
上下文模型 299
二值上下文模型 302
“超視力”壓縮（Clairvoyant compression） 304
6.4 JBIG：二值圖像標準 305
分辨率降低（Resolution reduction） 306
模板和自適應模板 311
編碼及概率估計 312
6.5 連續色調圖像的無損壓縮 313
GIF和PNG無損圖像格式 314
FELICS：快速、有效且無損圖像壓縮繫統 316
CALIC：基於上下文自適應無損圖像解碼器 320
JPEG-LS：無損圖像壓縮新標準 321
6.6 JPEG：連續色調圖像標準 323
6.7 圖像的遞增傳輸 328
金字塔編碼 329
金字塔編碼的壓縮 330
中位數聚合 332
誤差模型 333
6.8 圖像壓縮技術總結 334
第7章 文本圖像 337
7.1 文本圖像壓縮概念 339
7.2 有損壓縮和無損壓縮 343
7.3 標記抽取 345
跟蹤標記的邊界 345
清除圖像中的標記 348
按自然閱讀順序排序標記 350
7.4 模板匹配 351
全局模板匹配 352
局部模板匹配 354
基於壓縮的模板匹配 355
庫模板篩法 358
評價模板匹配方法 359
7.5 從標記到符號 363
庫構造 363
符號及其偏移量 365
7.6 編碼文本圖像分量 366
庫 366
符號數 367
符號偏移 367
原始圖像 368
7.7 效果：有損和無損的模式 370
7.8 繫統考慮 376
7.9 JBIG2：圖像文本壓縮標準 377
第8章 混合圖文 381
8.1 方向 383
用Hough變換檢測直線 384
左側留白查找 386
投影輪廓 387
從斜率直方圖到文本譜 392
8.2 切分 396
自下向上的切分方法 396
自上向下的組合的切分方法 398
基於標記的切分 399
使用短文本字符串切分 401
利用文本句法切分 404
8.3 分類 405
第9章 繫統實現 409
9.1 文本壓縮 410
選擇壓縮模型 411
選擇編碼器 414
哈夫曼編碼的限制 416
長度限制的編碼 422
9.2 文本壓縮效果 427
壓縮有效性 427
解壓速度 431
解壓內存 431
動態文檔集合 434
9.3 圖像和文本圖像 436
壓縮二值圖像 438
壓縮灰度圖像 439
壓縮文本圖像 439
9.4 構造索引 441
9.5 索引壓縮 443
9.6 查詢處理 445
布爾查詢 445
排名查詢 448
附錄A mg繫統指南 451
A.1 安裝MG繫統 451
A.2 一個簡單的存儲和檢索例子 453
A.3 數據庫創建 458
A.4 對一個索引文檔集合進行查詢 462
A.5 非文本文件 464
A.6 圖像壓縮程序 466
附錄B 新西蘭圖書館 467
B.1 什麼是NZDL 467
計算機科學報告（Computer Science Technical Reports） 467
其他文檔集合 470
文檔集合的發展 476
音頻集合（audio collections） 476
音調索引（Melody Index） 477
B.2 NZDL是如何工作的 479
原始文檔 479
搜索和索引 480
B.3 影響 482
參考文獻 483