管理海量数据-压缩、索引和查询 第2版PDF电子书下载

第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