管理海量数据:压缩、索引和查询.pdf

管理海量数据:压缩、索引和查询.pdf
 

书籍描述

编辑推荐
《管理海量数据:压缩、索引和查询(第2版)(全新修订版)》编辑推荐:大数据时代,这是一本给海量数据处理的从业人员的圣经——它教会您如何高效和有效地处理大量的信息,以便能方便、廉价地定位和抽取对企业对自己有效的信息。

媒体推荐
Witten,Moffat和Bell的第二版中不仅仅有更新、更好的文本搜索算法,而且还有大量有关图像分析和图像文本处理的知识。如果你关心搜索引擎,你就会需要这本书,这是目前唯一能够细致入微到搜索引擎如何运作的各个细节的一本书籍。这本书不仅翔实而且可读性强,作者将顶尖的程序和完美的写作风格融为一炉。
——Michael Lesk,国家自然基金会
对每个希望掌握大规模数据处理的从业人员来说,这本书是一本圣经。在Infoseek公司,我们要求每个搜索工程师阅读此书。作者的这项工作令人赞叹,他们已经把近5年内信息检索研究界最令人瞩目的成果写进了本书。
——Steve kirsch,Infoseek公司创始人
能够包括压缩、文件组织、全文索引技术和文档管理系统,因此本书无疑是无以伦比的。学生,研究者和从业人员将会从本书中受益
——Bruce Croft,马萨诸塞大学智能信息检索中心主任
快速响应和高效存储时超媒体研究者和开发者的基础技术,我强烈向大家推荐这本可读性强且发人深思的好书。
——Rob Aksycn, Knowledge Systems公司

作者简介
作者
作者是南半球院校当中最权威最重要的专家,本书当中阐释了他们多项创新性研究。他们写过8本书,300多篇研究论文 ,也在许多国际性程序协会当中做过研究,包括 IEEE数据压缩协会,ACM数字图书馆,以及信息检索协会。
译者
杨青,毕业于清华大学计算机系,原人民搜索技术总监,参与网页搜索、新闻搜索等多个产品项目的研发工作,在搜索引擎上面有多年的实践经验。
梁斌,清华大学计算机系博士研究生在读,在搜狗和金山软件等多个公司从事搜索引擎和内容推荐的研发工作,曾编著《走进搜索引擎》。

目录
第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

序言
计算机革命使得全社会都再也不能离开信息。然而,大部分的信息还是以其原始的格式存储着,即数据(data)。原始信息是海量的。这些数据主要产生于商业活动、法律诉讼和政府活动。随之而来的还有不计其数的复制品,这主要是报道、杂志和报纸产生的。最后这一切存储在档案馆、图书馆和计算机中。面对的挑战是如何高效和有效地处理大量的信息,以便能方便、廉价地定位和抽取有效的信息。
从空间的角度看,在纸张上存储文档的传统方法是昂贵的,更重要的是,当需要定位和检索所需要的信息时,需要付出高昂的代价。因此能够经济地存储和访问文档就变得越来越重要。几百英尺高的一大堆书中所包含的文本只需要一块磁盘就可以存下,从物理空间占用的角度看,电子媒体的这种存储能力是惊人的。和人工的文档索引方法相比,这种方法即具有伸缩性(全部的单词都可以作为关键词)和可靠性(因为索引构造的过程完全不需要人的参与,也就没有人为干扰)。此外,当今社会的各类组织不得不处理各种来源的电子信息,例如,机器可读文本、传真、其他扫描文档和数字图像。和纸媒体相比,使用电子媒体在存储和访问上都特别有效。
这本书讨论如何管理大量文档、GB的数据。1GB大约是1000MB,这足够存储1000本书籍,相当于从地板摞到天花板这么高的书籍。在日常生活的词汇不断地增长的同时,大规模存储设备容量也在不断增长。就在20年前,百兆数据的需求看上去是那么的奢侈,甚至是幻想。今天个人电脑已经配置上了GB的存储设备,甚至一些小的机构也需要存储数GB的数据。自从本书第一版问世以来,万维网爆炸般地创造了万亿字节(terabytes)的公开数据,让越来越多的人意识到处理如此大规模数据的难题是特别重要的。
管理如此大量数据主要需要面对两个挑战,这两个挑战都在本书中进行了讨论。第一个挑战是如何有效地存储数据。这主要通过压缩的方法来实现。第二个挑战是提供一种通过关键词搜索的方法来提供快速访问信息的方法。因此,一个特别定制的索引尤为关键。传统的压缩和搜索方法需要调整以适应这些挑战。这也是本书中主要讨论的两个主题。本书讨论的这些技术应用的结果是确保计算机系统可以存储数百万的文档和能够在秒级的时间内检索到包含任给关键词(或关键词组合)的文档,甚至可以在不到1s内完成查询。
举个例子来说明本书中所讨论的这些方法的威力。掌握了这些方法后,你可以对数GB的文本创建一个数据库,并且使用它来响应类似这样的查询请求,“在仅适用工作站的条件下,用数秒时间就能在全部文档中检索同时包含‘managing’和‘gigabytes’的段落”。事实上,如果能够对文本创建恰当的索引,这并不是什么神奇的事情。最令人着迷的是这些创建的数据库(包括索引和完整文本),当然都是压缩过的,只有不到原文本的一半大小。不仅如此,创建这样一个数据库只需要数小时即可。最令人惊讶的可能是如果数据集不压缩的话,查询时间还会更少。
大部分本书讨论的技术都已经被提出、实验和应用到实践中。为快速搜索和检索而构造的文本索引被仔细地检查过,这些信息构成了本书的核心。话题还包括文本压缩和建模,压缩图像的方法,压缩文本图像(例如扫描或传真文档)和为了区分图片图表和文本而进行的页面布局识别等。
全文索引不可避免会非常巨大,因此制作的成本也很高。然而,本书揭示了全部单词,如果需要的话,还包括全部数字建立完整索引的奥秘,并阐述了如何用如此小的存储代价支持如此快速的访问能力的技巧。
本书的目标是介绍管理大量文档和图片数据集的最新方法。在阅读本书以后,你将掌握这些技术并同时对它们的威力产生敬意。

文摘
大多数的外部压缩方法可以归纳为两类,即符号方法(symbolwise method)和字典方法(dictionary method)。符号方法就是通过估计符号(常常是字符)的概率值来压缩文本,它在同一时间只对一个符号编码,如摩斯码,对最可能出现的符号使用较短的码字。字典方法通过使用“字典”中词条的索引替换单字或文本片段来实现压缩。既然采用特殊的编码表示所有的词汇,因此Braille盲文编码也是一种字典方法。
符号方法通常基于哈夫曼编码或算术编码,主要的不同之处在于如何估计符号的概率。符号概率值估计得越准,压缩效果就越好。为了获得更好的压缩效果,概率估计常常要根据符号出现的上下文来进行。概率估计的工作叫做“建模”(modeling),而建立一个好的模型对于实现好的压缩效果是至关重要的。把概率转换为比特流(bit stream)以供传输的过程叫做“摩斯码”,编码这个概念很好理解,可用哈夫曼或算术编码的方法有效地实现。模型的建立是一种艺术,不会只有唯一的“最佳”方法。

内容简介
《管理海量数据:压缩、索引和查询(第2版)(全新修订版)》是斯坦福大学信息检索和挖掘课程的首选教材之一,并已成为全球主要大学信息检索的主要教材。《管理海量数据——压缩、索引和查询(第2版)》理论和实践并重,深入浅出地给出了海量信息数据处理的整套解决方案,包括压缩、索引和查询的方方面面。其最大的特色在于不仅仅满足信息检索理论学习的需要,更重要的是给出了实践中可能面对的各种问题及其解决方法。
《管理海量数据——压缩、索引和查询(第2版)》作为斯坦福大学信息检索课程的教材之一,具有一定的阅读难度,主要面向信息检索专业高年级本科生和研究生、搜索引擎业界的专业技术人员和从事海量数据处理相关专业的技术人员。

购买书籍

当当网购书 京东购书 卓越购书

PDF电子书下载地址

相关书籍

搜索更多