基本信息
- 原书名:Managing Gigabytes: Compressing and Indexing Documents and Images
- 原出版社: Morgan Kaufmann
- 作者: (新西兰)Ian H.Witten (澳)Alistair Moffat (新西兰)Timothy C.Bell
- 译者: 梁斌
- 出版社:电子工业出版社
- ISBN:9787121084911
- 上架时间:2009-6-23
- 出版日期:2009 年6月
- 开本:16开
- 页码:540
- 版次:1-1
- 所属分类:计算机 > 计算机网络 > 网络服务 > 综合
编辑推荐
Witten,Moffat和Bell的第二版中不仅仅有更新更好的文本搜索算法,而且还有大量有关图像分析和图像文本处理的知识。如果你关心搜索引擎,你就会需要这本书,这是目前唯一能够细致入微到搜索引擎如何运作的各个细节的一本书籍。这本书不仅翔实而且可读性强,作者将顶尖的程序和完美的写作风格融为一炉。
---Michael Lesk,国家自然基金会
内容简介
作译者
Alistair Moffat是墨尔本大学计算科学系的副教授。在各大会议和期刊中发表了大量论文,这些论文包括的领域有:关于文本和图像压缩的算法和数据结构,字典和优先级队列的自适应数据结构,以及自适应搜索和排序算法。..
Timothy C.Bell是Canterbury大学计算机科学系系主任,是出版于1990年的《Text Compression》一书的作者。在各大期刊和会议上发表了多篇论文,这些论文涉及文本和图像压缩,计算机和音乐、计算机教育等。...
目录
1.1 文档数据库(DOCUMENT DATABASES)
1.2 压缩(COMPRESSION)
1.3 索引(INDEXES)
1.4 文档索引
1.5 MG海量文档管理系统
1.6 进一步阅读
第2章 文本压缩
2.1 模型
2.2 自适应模型
2.3 哈夫曼编码
范式哈夫曼编码
计算哈夫曼编码长度
总结
2.4 算术编码
算术编码是如何工作的
实现算术编码
保存累积计数
2.5 符号模型
部分匹配预测
译者序
在这些资源 中,《Managing gigabytes》,简记做“MG”,是其中一本极其重要的书籍。在译者集中学习信息检索的2005年,这本书是斯坦福大学信息检索和挖掘课程 的首选教材之一,和MIR 一起成为全球主要大学信息检索的主要教材。
MG深入浅出地给出了海量信息数据处理的整套解决方案,包括压缩、索引和查询的方方面面。本书理论性较强,公式众多,很多数据的给出并没有做具体的解释,此外还包括一些文化背景差异带来的理解障碍。但是作者和译者联手为大家奉献了412个注解,协助大家更好地理解本书。
和MIR不同的是,MG更加具有实践性,这得益于3位作者精心编写的MG检索引擎,该检索引擎被实践证明具有很强的易用性和伸缩性,附录B介绍的新西兰电子图书馆就使用了MG代码作为其内核。MG源代码可以在原著的官网上找到。本书绝大部分算法和思想都在代码中被完整体现,是不可多得的学习和实践材料。
本书主要面向信息检索专业方向的研究生、从事搜索引擎相关工作和其他对搜索技术感兴趣的人们,除了从书中获取严谨的理论知识以外,还可在MG源代码上展开实际的研究。无论从哪一点来看,本书都是非常好的研究起点。
本书作者Ian H.Witten,Alistair Moffat和Timothy C.Bell均是信息检索领域赫赫有名的专家,特别是Timothy C.Bell教授在本书的翻译过程中给予了巨大的帮助,同时译者也为原著的勘误做出了贡献 。
本书的第一版曾由科学出版社于1996年翻译并出版,由于时代局限、技术落后等原因,其内容和原著有一定距离。译者在学习和翻译的过程中都获得了它的帮助,这里对参与本书第一版翻译工作的同志表示感谢。
最后要特别感谢包括原著3位作者在内的信息检索专家们无私地分享了他们的技术成果,并且感谢博文视点出版社大力引进,编辑孙学瑛女士及方方面面工作人员给予的帮助。由于译者能力有限,若有翻译不当之处,欢迎发送电子邮件至mgigabyte@gmail.com批评指正。
最后引用本书中的一段原话作为结尾:“在信息科学技术的历史上,从来没有像今天这样,创造如此大的价值的如此多的技术却掌握在如此少的人的手里。”希望能够和原著的作者一样做出自己一份微薄的贡献。
梁斌
2009年2月15日
前言
从空间的角度看,在纸张上存储文档的传统方法是昂贵的,更重要的是,当需要定位和检索所需要的信息时,需要付出高昂的代价。因此能够经济地存储和访问文档就变得越来越重要。几百英尺高的一大堆书中所包含的文本只需要一块磁盘就可以存下,从物理空间占用的角度看,电子媒体的这种存储能力是惊人的。和人工的文档索引方法相比,这种方法即具有伸缩性(全部的单词都可以作为关键词)和可靠性(因为索引构造的过程完全不需要人的参与,也就没有人为干扰)。此外,当今社会的各类组织不得不处理各种来源的电子信息,例如,机器可读文本、传真、其他扫描文档和数字图像。和纸媒体相比,使用电子媒体在存储和访问上都特别有效。
这本书讨论如何管理大量文档,G字节的数据。1G大约是1000M字节,这足够存储1000本书籍,相当于在从地板摞到天花板这么高的书籍。日常生活的词汇也在不断地增长的同时,大规模存储设备容量也在不断增长。就在20年前,百兆数据的需求看上去是那么的奢侈,甚至是幻想。今天个人电脑已经配置上了G字节的存储设备,甚至一些小的机构也需要存储数G的数据。自从本书第一版问世以来,万维网爆炸般地创造了万亿字节(terabytes)的公开数据,让越来越多的人意识到处理如此大规模数据的难题是特别重要的。
管理如此大量数据主要需要面对两个挑战,这两个挑战都在本书中进行了讨论。第一个挑战是如何有效地存储数据。这主要通过压缩的方法来实现。第二个挑战是提供一种通过关键词搜索的方法来提供快速访问信息的方法。因此,一个特别定制的索引尤为关键。传统的压缩和搜索方法需要调整以适应这些挑战。这也是本书中主要讨论的两个主题。本书讨论的这些技术应用的结果是确保计算机系统可以存储数百万的文档和能够在秒级的时间内检索到包含任给关键词(或关键词组合)的文档,甚至可以在不到1秒的时间内完成查询。
举个例子来说明本书中所讨论的这些方法的威力。掌握了这些方法后,你可以对数G字节的文本创建一个数据库,并且使用它来响应类似这样的查询请求,“在仅适用工作站的条件下,用数秒时间就能在全部文档中检索同时包含‘managing’和‘gigabytes’的段落”。事实上,如果能够对文本创建恰当的索引,这并不是什么神奇的事情。最令人着迷的是这些创建的数据库(包括索引和完整文本),当然都是压缩过的,只有不到原文本的一半大小。不仅如此,创建这样一个数据库只需要数小时即可。最令人惊讶的可能是如果数据集不压缩的话,查询时间还会更少。
大部分本书讨论的技术都已经被提出、实验和应用到实践中。为快速搜索和检索而构造的文本索引被仔细的检查过,这些信息构成了本书的核心。话题还包括文本压缩和建模,压缩图像的方法,压缩文本图像(例如扫描或传真文档)和为了区分图片图表和文本而进行的页面布局识别等。
全文索引不可避免会非常巨大,因此制作的成本也很高。然而,本书揭示了全部单词,如果需要的话,还包括全部数字建立完整索引的奥秘,并阐述了如何用如此小的存储代价支持如此快速的访问能力的技巧。
本书的目标是介绍管理大量文档和图片数据集的最新方法。在阅读本书以后,你将掌握这些技术并同时对它们的威力产生敬意。
随书软件
一个阐述本书思想的完整的系统,mg(代表”managing gigabytes”),已经被开发出来。mg完整代码可以在互联网上自由获得(官方首页www.cs.mu.oz.au/mg/)。代码用ANSI C语言编写并且能够运行在Unix操作系统下,这是一个我们开发的可操作的技术样例。它用一种完整的方法压缩、存储和访问了文本集合、扫描文档和图像。任何布尔型的关键词组合都可以用在对全部文档进行的检索中,同时支持非常规的排名查询(用户仅仅指定一个关键词列表,系统能够让被检索出的相关文档有序排列)。考虑到早先提到的查询例子,在全部文档中检索同时包含‘managing’和‘gigabytes’的段落。在包含750000个文档的数据库中,相当于2G字节的文本,对于mg来说只需要1秒就能够访问和解码这两个单词的索引项,这两个单词分别出现了159458和961次,同时包含这两个单词的文档有554个,大约7M字节。取出和解压这些文档只需要不到1分钟。
读者定位
对本书感兴趣的读者包括这样几类。对这些主题有兴趣的一般读者。需要掌握信息管理新技术的信息专家。愿意了解技术细节的其他读者。阅读此书的读者包括:信息系统的实践者,程序员,顾问,图书管理员,信息传播者,教授,学生,开发人员,需求工程师,专利检查员和对新技术感到好奇的人们。需要发布CD-ROM数据库(例如书籍,大百科全书,甚至计算机软件)的人员将直接从本书所阐述的技术中获益,为了避免要求读者具备较多的专业理论和数学知识,除了那些比较难懂的书中在右侧空白处用浅灰色条块标记的部分 ,读者可以跳过这些部分,并不会影响阅读的连续性。我们对主要的结论均在文中显著给出。
本书可以用于高年级大学生、研究生和专业人员的基础课来学习。每一章都介绍了全文检索系统的不同部分,这包括文本、索引和图片的压缩方法;大部分的章节可以独立作为短期课程的教材。例如,第二章是一个文本压缩方法的完整综述,可以用来作为关于压缩的一个短期课程教材。事实上可以用一本书的篇幅来写这一部分,事实上,他们也这么做了(和John G.Cleary和本书的两位作者一起合作了一本叫做Text Compression的书)。这个章节提供了一个独立成篇,对实践中常用的方法给出了一个实际的指南,给与那些愿意在这个领域从事工作的人们提供了足够的参考信息。类似的,第六章也是独立成篇的,介绍了图像压缩的当前技术和国际标准。第五章包括了使用布尔查询和排名查询的信息检索基本概念,给出了关于如何实现的一些具体技术细节。
这本书的组织让两组章节提供深入和更细的子领域的技术细节。第1,3,4和5章用作研究生关于信息检索的基础课。而第六,七和八章构成了有关图像分析和压缩的独立模块。更完整的高年级本科生和研究生的关于信息系统和数据压缩的课程所涉及的全部内容都可以在本书中找到,或者作为信息系统和实践数据结构的补充教材。
最后,如果你只对概念感兴趣,对技术细节不感兴趣的话,可以阅读本书第一和最后一章以了解一般的信息。第一章介绍了需要解决的问题和给读者一个现实世界的例子。交代了制作一个词汇索引在过去是多么耗时,以及后来他们是怎么被全文检索系统取代的过程。本书需要传达的主要思想:压缩和索引大规模文本和图像集合的方法。第十章展望了未来的发展和这些新技术的应用场合。其中一个开发方向是将广播和多媒体信息集成到索引的检索系统中来。这种需求是显然的;任何可以被关键词检索的信息类型都可以整合到压缩的索引系统中来,任何压缩对信息压缩的方法也都可以被引入。将来这类系统将会迅速应用与存储各种大量信息的场合中。
更新和修订的内容
本书的第一版于1994年出版,1999年3月,我们出版了它的第二版。在这5年间,信息世界中发生了巨大的变化,万维网的繁荣,数字图书馆的创意,信息国际化,Java语言和网络计算机,卧室中的虚拟现实(不好的一面是,色情文学,虚拟性和博彩)。今天,最大的信息系统是随处可见的TV、杂志和广告。今天信息工作者经历了这种冲击和每天都不可避免的大规模数据检索需求所导致的沮丧。这些都在这5年内发生了。其中本书中包含的诸多深奥话题中有关文本图像压缩的内容已经成为了国际标准,并且很快就能应用到你的传真机上。然而1993年预言的一些变化还没有发生:例如,第二版没有被叫做Managing Terabytes,在第一版中我曾这样预言过。有关技术预言的内容就是这么多。
一方面,全世界的信息已经融化进我们日常的生活中,这在某种程度上延续了我们在1993年的预言。另一方面,本书的话题并没有过时:事实上,这些内容和目前的现实更加契合。压缩和索引文档和图像的需求更加强烈。压缩、信息科学和全文检索的基本想法,包括图像表示的基本想法都是相同的。压缩的全文索引的想法特别不寻常。就目前我们了解的情况,非商业的搜索引擎已经基本使用了我们所提到的这些技术:他们付出了巨大的努力,使用了巨大的磁盘和安装了许多内存。他们不存储文本,只存储索引。在出现技术错误时,已经从“Bus error:core dumpled”这样奇怪的提示改为了“404 Not Found: The requested URL was not found on this server”,这看上更加友好。和第一本书出版的时候一样,现在正当时。
虽然第二版的基本核心内容和第一版相同,但是我们尽最大努力更新了部分内容以反应这五年来发生的变化。当然,我们改正了一些错误,这些错误来自于从在线勘误的积累。事实上,发现的错误出乎预料地少,我们希望第二本错误会更少。第二版的在线勘误可以在www.cs.mu.oz.au/mg/中找到。我们仔细的编辑了各个章节并且使这些内容保持与时俱进,追加了一些信息参考内容到“进一步阅读”中。最让人感兴趣的部分都追加了新内容,这些就是其中主要的追加。..
第二章追加了关于文本压缩的最近发展,包括块排序方法(Burrows-Wheeler转换),近似算术编码,和快速哈夫曼编码算法。有些方法的一些细节也进行了追加,效果比较也更新到了最近压缩程序的水平,相对结果采用了最新的Canterbury语料,而不是此前使用的Calgary语料。
媒体评论
---Michael Lesk,国家自然基金会
对每个希望掌握大规模数据处理的从业人员来说,这本书是一本圣经。在Infoseek公司,我们要求每个搜索工程师阅读此书。作者的这项工作令人赞叹,他们已经把近5年内信息检索研究界最令人瞩目的成果写进了本书。
---Steve kirsch,Infoseek公司创始人
能够包括压缩,文件组织,全文索引技术和文档管理系统,因此本书无疑是无以伦比的。学生,研究者和从业人员将会从本书中受益
---Bruce Croft,马萨诸塞大学智能信息检索中心主任
快速响应和高效存储时超媒体研究者和开发者的基础技术,我强烈向大家推荐这本可读性强且发人深思的好书。
---Rob Aksycn, Knowledge Systems公司