管理海量数据——压缩、索引和查询（第2版）（经典再现全新修订版）

作者简介

《管理海量数据——压缩、索引和查询（第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

内容概要

作者

作者是南半球院校当中最权威最重要的专家，本书当中阐释了他们多项创新性研究。他们写过8本书，300多篇研究论文 ，也在许多国际性程序协会当中做过研究，包括 IEEE数据压缩协会，ACM数字图书馆，以及信息检索协会。

译者

杨青，毕业于清华大学计算机系，原人民搜索技术总监，参与网页搜索、新闻搜索等多个产品项目的研发工作，在搜索引擎上面有多年的实践经验。

梁斌，清华大学计算机系博士研究生在读，在搜狗和金山软件等多个公司从事搜索引擎和内容推荐的研发工作，曾编著《走进搜索引擎》。

 管理海量数据——压缩、索引和查询（第2版）（经典再现全新修订版）下载 更多精彩书评