【美】Ian H.Witten【美】Alistair Moffat【美】Timothy C.Bell 著
梁斌楊青譯
ISBN 978-7-121-21933-7
2014年1月出版
定價：108元
540頁
16開
編輯推薦
大數據時代，這是一本給海量數據處理的從業人員的聖經——它教會您如何高效和有效地處理大量的信息，以便能方便、廉價地定位和抽取對企業對自己有效的信息。
內容提要
《管理海量數據——壓縮、索引和查詢（第2版）》是史丹福大學信息檢索和挖掘課程的首選教材之一，並已成為全球主要大學信息檢索的主要教材。《管理海量數據——壓縮、索引和查詢（第2版）》理論和實踐並重，深入淺出地給出了海量信息數據處理的整套解決方案，包括壓縮、索引和查詢的方方面面。其最大的特色在於不僅僅滿足信息檢索理論學習的需要，更重要的是給出了實踐中可能面對的各種問題及其解決方法。
《管理海量數據——壓縮、索引和查詢（第2版）》作為史丹福大學信息檢索課程的教材之一，具有一定的閱讀難度，主要面向信息檢索專業高年級本科生和研究生、搜尋引擎業界的專業技術人員和從事海量數據處理相關專業的技術人員。
目錄
第1章概覽 1
1.1文檔資料庫（document databases） 7
1.2壓縮（compression） 10
1.3索引（indexes） 12
1.4文檔索引 16
1.5MG海量文檔管理系統 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
無參模型（Nonparameterizedmodels） 114
全局貝努里模型117
全局觀測頻率模型（Globalobserved frequency model） 120
局部貝努里模型（LocalBernoulli model） 121
有偏貝努里模型（SkewedBernoulli model） 122
局部雙曲模型（Localhyperbolic model）124
局部觀測頻率模型（Localobserved frequency model）125
上下文相關壓縮（Context-sensitivecompression） 127
3.4索引壓縮方法的效果 129
3.5簽名檔案和點陣圖 131
簽名檔案 132
位片簽名檔案（Bitslicedsignature files） 136
簽名檔案分析 141
點陣圖 144
簽名檔案和點陣圖的壓縮 145
3.6索引方法的比較 148
3.7大小寫摺疊、詞根化和停用詞 150
大小寫摺疊151
詞根化151
影響索引長度的因素152
停用詞（stop word） 153
第4章查詢 157
4.1訪問字典的方法 161
訪問數據結構 162
前端編碼（Frontcoding） 165
最小完美哈希函式 168
完美哈希函式的設計171
基於磁碟的字典存儲176
4.2部分指定的查詢術語 177
字元串暴力匹配（Brute-forcestring matching） 177
用n-gram索引 178
循環字典（Rotatedlexicon） 180
4.3布爾查詢（BOOLEAN QUERY）182
合取查詢（conjunctivequery） 182
術語處理順序 183
隨機訪問和快速查找185
分塊倒排索引 187
非合取查詢（NonconjunctiveQuery）190
4.4信息檢索和排名 191
坐標匹配（Coordinatematching） 191
內積相似度192
向量空間模型 197
4.5檢索效果評價 200
召回率和精確率200
召回率——精確率曲線 203
TREC項目 204
全球資訊網搜尋（WorldWide 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-basedpartitioning） 271
基於文本的切分273
5.5倒排方法的比較 276
5.6構造簽名檔案和點陣圖 277
5.7動態文檔集合 279
擴展文本（Expandingthe text）279
索引擴展（Expandingthe index） 280
第6章圖像壓縮 287
6.1圖像類型 288
6.2CCITT二值圖像的傳真標準 292
6.3二值圖像的上下文壓縮 296
上下文模型299
二值上下文模型302
“超視力”壓縮（Clairvoyantcompression） 304
6.4JBIG：二值圖像標準 305
解析度降低（Resolutionreduction）306
模板和自適應模板 311
編碼及機率估計312
6.5連續色調圖像的無損壓縮 313
GIF和PNG無損圖像格式 314
FELICS：快速、有效且無損圖像壓縮系統 316
CALIC：基於上下文自適應無損圖像解碼器 320
JPEG-LS：無損圖像壓縮新標準 321
6.6JPEG：連續色調圖像標準 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.9JBIG2：圖像文本壓縮標準 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
附錄Amg系統指南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
計算機科學報告（ComputerScience Technical Reports） 467
其他文檔集合 470
文檔集合的發展476
音頻集合（audiocollections） 476
音調索引（MelodyIndex） 477
B.2NZDL是如何工作的 479
原始文檔 479
搜尋和索引480
B.3影響 482
參考文獻 483
精彩節摘
大多數的外部壓縮方法可以歸納為兩類，即符號方法（symbolwise method）和字典方法（dictionarymethod）。符號方法就是通過估計符號（常常是字元）的機率值來壓縮文本，它在同一時間只對一個符號編碼，如摩斯碼，對最可能出現的符號使用較短的碼字。字典方法通過使用“字典”中詞條的索引替換單字或文本片段來實現壓縮。既然採用特殊的編碼表示所有的辭彙，因此Braille盲文編碼也是一種字典方法。
符號方法通常基於哈夫曼編碼或算術編碼，主要的不同之處在於如何估計符號的機率。符號機率值估計得越準，壓縮效果就越好。為了獲得更好的壓縮效果，機率估計常常要根據符號出現的上下文來進行。機率估計的工作叫做“建模”（modeling），而建立一個好的模型對於實現好的壓縮效果是至關重要的。把機率轉換為比特流（bitstream）以供傳輸的過程叫做“摩斯碼”，編碼這個概念很好理解，可用哈夫曼或算術編碼的方法有效地實現。模型的建立是一種藝術，不會只有唯一的“最佳”方法。
作者簡介
作者
作者是南半球院校當中最權威最重要的專家，本書當中闡釋了他們多項創新性研究。他們寫過8本書，300多篇研究論文 ，也在許多國際性程式協會當中做過研究，包括 IEEE數據壓縮協會，ACM數字圖書館，以及信息檢索協會。
譯者
楊青，畢業於清華大學計算機系，原人民搜尋技術總監，參與網頁搜尋、新聞搜尋等多個產品項目的研發工作，在搜尋引擎上面有多年的實踐經驗。
梁斌，清華大學計算機系博士研究生在讀，在搜狗和金山軟體等多個公司從事搜尋引擎和內容推薦的研發工作，曾編著《走進搜尋引擎》。
媒體評論
Witten，Moffat和Bell的第二版中不僅僅有更新、更好的文本搜尋算法，而且還有大量有關圖像分析和圖像文本處理的知識。如果你關心搜尋引擎，你就會需要這本書，這是目前唯一能夠細緻入微到搜尋引擎如何運作的各個細節的一本書籍。這本書不僅翔實而且可讀性強，作者將頂尖的程式和完美的寫作風格融為一爐。
——Michael Lesk，國家自然基金會
對每個希望掌握大規模數據處理的從業人員來說，這本書是一本聖經。在Infoseek公司，我們要求每個搜尋工程師閱讀此書。作者的這項工作令人讚嘆，他們已經把近5年內信息檢索研究界最令人矚目的成果寫進了本書。
——Steve kirsch，Infoseek公司創始人
能夠包括壓縮、檔案組織、全文索引技術和文檔管理系統，因此本書無疑是無以倫比的。學生，研究者和從業人員將會從本書中受益
——Bruce Croft,麻薩諸塞大學智慧型信息檢索中心主任
快速回響和高效存儲時超媒體研究者和開發者的基礎技術，我強烈向大家推薦這本可讀性強且發人深思的好書。
——Rob Aksycn, Knowledge Systems公司
前言
計算機革命使得全社會都再也不能離開信息。然而，大部分的信息還是以其原始的格式存儲著，即數據(data)。原始信息是海量的。這些數據主要產生於商業活動、法律訴訟和政府活動。隨之而來的還有不計其數的複製品，這主要是報導、雜誌和報紙產生的。最後這一切存儲在檔案館、圖書館和計算機中。面對的挑戰是如何高效和有效地處理大量的信息，以便能方便、廉價地定位和抽取有效的信息。
從空間的角度看，在紙張上存儲文檔的傳統方法是昂貴的，更重要的是，當需要定位和檢索所需要的信息時，需要付出高昂的代價。因此能夠經濟地存儲和訪問文檔就變得越來越重要。幾百英尺高的一大堆書中所包含的文本只需要一塊磁碟就可以存下，從物理空間占用的角度看，電子媒體的這種存儲能力是驚人的。和人工的文檔索引方法相比，這種方法即具有伸縮性（全部的單詞都可以作為關鍵字）和可靠性（因為索引構造的過程完全不需要人的參與，也就沒有人為干擾）。此外，當今社會的各類組織不得不處理各種來源的電子信息，例如，機器可讀文本、傳真、其他掃描文檔和數字圖像。和紙媒體相比，使用電子媒體在存儲和訪問上都特別有效。
這本書討論如何管理大量文檔、GB的數據。1GB大約是1000MB，這足夠存儲1000本書籍，相當於從地板摞到天花板這么高的書籍。在日常生活的辭彙不斷地增長的同時，大規模存儲設備容量也在不斷增長。就在20年前，百兆數據的需求看上去是那么的奢侈，甚至是幻想。今天個人電腦已經配置上了GB的存儲設備，甚至一些小的機構也需要存儲數GB的數據。自從本書第一版問世以來，全球資訊網爆炸般地創造了萬億位元組（terabytes）的公開數據，讓越來越多的人意識到處理如此大規模數據的難題是特別重要的。
管理如此大量數據主要需要面對兩個挑戰，這兩個挑戰都在本書中進行了討論。第一個挑戰是如何有效地存儲數據。這主要通過壓縮的方法來實現。第二個挑戰是提供一種通過關鍵字搜尋的方法來提供快速訪問信息的方法。因此，一個特別定製的索引尤為關鍵。傳統的壓縮和搜尋方法需要調整以適應這些挑戰。這也是本書中主要討論的兩個主題。本書討論的這些技術套用的結果是確保計算機系統可以存儲數百萬的文檔和能夠在秒級的時間內檢索到包含任給關鍵字（或關鍵字組合）的文檔，甚至可以在不到1s內完成查詢。
舉個例子來說明本書中所討論的這些方法的威力。掌握了這些方法後，你可以對數GB的文本創建一個資料庫，並且使用它來回響類似這樣的查詢請求，“在僅適用工作站的條件下，用數秒時間就能在全部文檔中檢索同時包含‘managing’和‘gigabytes’的段落”。事實上，如果能夠對文本創建恰當的索引，這並不是什麼神奇的事情。最令人著迷的是這些創建的資料庫（包括索引和完整文本），當然都是壓縮過的，只有不到原文本的一半大小。不僅如此，創建這樣一個資料庫只需要數小時即可。最令人驚訝的可能是如果數據集不壓縮的話，查詢時間還會更少。
大部分本書討論的技術都已經被提出、實驗和套用到實踐中。為快速搜尋和檢索而構造的文本索引被仔細地檢查過，這些信息構成了本書的核心。話題還包括文本壓縮和建模，壓縮圖像的方法，壓縮文本圖像（例如掃描或傳真文檔）和為了區分圖片圖表和文本而進行的頁面布局識別等。
全文索引不可避免會非常巨大，因此製作的成本也很高。然而，本書揭示了全部單詞，如果需要的話，還包括全部數字建立完整索引的奧秘，並闡述了如何用如此小的存儲代價支持如此快速的訪問能力的技巧。
本書的目標是介紹管理大量文檔和圖片數據集的最新方法。在閱讀本書以後，你將掌握這些技術並同時對它們的威力產生敬意。
