| 词条 | 深入搜索引擎 |
| 释义 | 本书是斯坦福大学信息检索和挖掘课程的首选教材之一，并已成为全球主要大学信息检索的主要教材。本书理论和实践并重，深入浅出地给出了海量信息数据处理的整套解决方案，包括压缩、索引和查询的方方面面。其最大的特色在于不仅仅满足信息检索理论学习的需要，更重要的是给出了实践中可能面对的各种问题及其解决方法。 图书信息作 者：[美]Ian H. Witten（艾伦 H.威顿）,Alistair Moffat（亚里斯蒂尔.莫夫特）, Timothy C. Bell (Author)（提摩太 C.贝尔）著 梁斌 译 出 版 社： 电子工业出版社 出版时间： 2009-5-1 页 数：508页 开 本： 16开 I S B N ： 9787121084911 分类： 图书 >> 计算机 >> 搜索引擎 定价：￥75.00元 内容简介本书作为斯坦福大学信息检索课程的教材之一，具有一定的阅读难度，主要面向信息检索专业高年级本科 生和研究生、搜索引擎业界的专业技术人员和从事海量数据处理相关专业的技术人员。 作者简介Ian H.Witten 是新西兰Waikato大学计算系科学系教授，是ACM、新西兰皇家学会会员。是英国、美国、加拿大和新西兰的专业计算、信息检索和工程协会会员。他是 《The Reactive Keyboard》和《Text Compression》的作者之一，这两本书分别出版于1992年和1990年。各大会议和期刊论文都能看到他的论文。 Alistair Moffat是墨尔本大学计算科学系的副教授。在各大会议和期刊中发表了大量论文，这些论文包括的领域有：关于文本和图像压缩的算法和数据结构，字典和优先级队列的自适应数据结构，以及自适应搜索和排序算法。 Timothy C.Bell是Canterbury大学计算机科学系系主任。是出版于1990年的《Text Compression》一书的作者。在各大期刊和会议上发表了多篇论文，这些论文涉及文本和图像压缩，计算机和音乐，计算机教育等。 原著推荐序The new edition of Witten, Moffat, and Bell not only has newer and better text search algorithms but much material on image analysis and joint image/text processing. If you care about search engines, you need this book; it is the only one with full details of how they work. The book is both detailed and enjoyable; the authors have combined elegant writing with top-grade programming. ----Michael Lest, National Science Foundation This book is the Bible for anyone who needs to manage large data collections. It’s required reading for our search gurus at infoseek. The authors have done an outstanding job of incorporating and describing the most significant new research in information retrieval over the past five years into this second edition ----Steve Kirsch, Cofounder, Infoseek Corporation The coverage of compression, file organizations, and indexing techniques for full text and document management system is unsurpassed, Students, researchers, and practitioners will all benefit from reading this book. ---Bruce Croft, Director, Center for Intelligent Information Retrieval at the University of Massachusetts. Rapid response and efficient storage are fundamental technologies for hypermedia researchers and developers, and I strongly recommend this second edition of this highly readable and thought-provoking book. ---Rob Aksycn, Knowledge System. 作者序 About the Chinese edition: a word from the authors Ni hao! It is a great pleasure to have the opportunity to write a few words for this new Chinese edition of Managing Gigabytes. We produced the first edition of this book in 1993—when the World-Wide Web was hardly known. With the advent of the web the techniques we described became far more important than before. Indeed, we have been told that our book was required reading at Google in the early days. Back in 1993 a gigabyte was still considered to be an enormous amount of storage space, but it turns out that the techniques described apply equally well to terabytes—even petabytes—of data. Of course, the book has been considerably updated since that first edition. We have all visited China and seen many wonders: ranging from Jade Dragon Snow Mountain in the west to Shanghai in the east; from Beijing and Yinchuan in the north to Nanjing and Guangzhou in the south. The first trip by one of us was over thirty years ago, and we have seen the country blossom in technical maturity and sophistication from a base that can only be described as mamahuhu. We are absolutely delighted that our book will contribute to further extended growth in the key technologies of full-text searching and data compression. Many years ago one of our students showed us a Chinese version of an early edition of Managing Gigabytes. The translation, which we had not been aware of, was embarrassingly poor, and a devastatingly prominent error was that only one author’s name appeared on the cover of the book—indeed the other two were not mentioned anywhere inside either (although their families were faithfully thanked in the translated preface). So you can imagine how extraordinarily pleased we are to see this new translation of the second edition of our book. During visits to China in 2008 and 2009 Tim Bell taught the material in this book at Huazhong University of Science and Technology, and could see the value of having a translation available for students. We were delighted when we heard from 梁斌, who was starting on a translation around that time, and even more pleased when we realised what a careful and thorough job he was doing. Perhaps the greatest compliment anyone can pay an author is to painstakingly translate their work. We are deeply and sincerely grateful to 梁斌 for the tremendous amount of time and energy he has put into this project. Xiexie! We know that he has mastered the material because he has pointed out a number of obscure errors in the English edition, and has asked us many penetrating questions. We hope you will benefit from his effort, and enjoy reading this book. Tim Bell Alistair Moffat Ian H. Witten March 2009 译者序1998年从美国斯坦福大学产生了一段传奇的财富神话，这就是今天市值约千亿美元的Google。众所周知，Google 正是由Lawrence Page在斯坦福大学发起的研究项目转变而来的。正是由于斯坦福大学对全球信息检索的杰出贡献，译者从事相关研究的时候也曾阅读了大量出自斯坦福大学的课件、论文和推荐教材。 在这些资源 中，《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教授在本书的翻译过程中给予了巨大的帮助，同时译者也为原著的勘误做出了贡献 。 最后要特别感谢包括原著3位作者在内的信息检索专家们无私地分享了他们的技术成果，并且感谢博文视点出版社大力引进，编辑孙学瑛女士及方方面面工作人员给予的帮助。由于译者能力有限，若有翻译不当之处，欢迎发送电子邮件至mgigabyte@gmail.com批评指正。 最后引用本书中的一段原话作为结尾：“在信息科学技术的历史上，从来没有像今天这样，创造如此大的价值的如此多的技术却掌握在如此少的人的手里。”希望能够和原著的作者一样做出自己一份微薄的贡献。 梁斌 2009年2月15日 前言计算机革命使得全社会都再也不能离开信息。然而，大部分的信息还是以其原始的格式存储着：即数据(data)。原始信息是海量的。这些数据主要产生于商业活动、法律诉讼和政府活动。随之而来的还有不计其数的复制品，这主要是报道、杂志和报纸产生的。最后这些一切存储在档案馆、图书馆和计算机中。面对的挑战是如何高效和有效地处理大量的信息，以便能方便、廉价地定位和抽取有效的信息。 从空间的角度看，在纸张上存储文档的传统方法是昂贵的，更重要的是，当需要定位和检索所需要的信息时，需要付出高昂的代价。因此能够经济地存储和访问文档就变得越来越重要。几百英尺高的一大堆书中所包含的文本只需要一块磁盘就可以存下，从物理空间占用的角度看，电子媒体的这种存储能力是惊人的。和人工的文档索引方法相比，这种方法即具有伸缩性（全部的单词都可以作为关键词）和可靠性（因为索引构造的过程完全不需要人的参与，也就没有人为干扰）。此外，当今社会的各类组织不得不处理各种来源的电子信息，例如，机器可读文本、传真、其他扫描文档和数字图像。和纸媒体相比，使用电子媒体在存储和访问上都特别有效。 这本书讨论如何管理大量文档，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语料。 第三章讨论了索引技术，追加了关于基于上下文索引压缩的一节内容，包括对最新发展起来的插值编码进行了讨论。关于签名文件和其与倒排文件的效果比较的内容都进行进一步的修订。 第四章中追加了4个小节。第一个新增小节讨论了分块倒排索引的使用，这能够支持快速布尔查询。第二个新增小节讨论了基于频率排序的到排索引，这能够改善排名查询的效果。第三个新增小节阐述了一些关于运作万维网搜索引擎的一些话题。第四个新增小节分析了分布式查询。这些小节介绍了排名查询，TREC项目被进一步修订以包含这5年来的一些进展。 第六章包括了一些关于无损图像压缩的新内容，包括在互联网上广泛使用的图像事实标准（GIF和PNG），一个叫做CALIC的高性能无损图像压缩算法。和JPEG无损和JPEG-LS草案都已经申请成为新的无损压缩的国际标准。 第七章追加了关于JBIG2的一个新小节，这是一个即将成为文档图像压缩的国际标准。虽然直到2000年末该方案还没有最终确定，但是在本书出版之时，这个方案有可能会确定下来，其中会包含本书中介绍的许多技术。 第九章修订和更新了许多实验结果以反应压缩技术的当前水平和计算机硬件在这5年间所取得的成就。特别地，一个特别细致的小节（包含若干新图例）被追加用来阐述限长的哈夫曼编码。 第十章包含了关于因特网和万维网的一些新内容，关于数字图书馆的一些新内容，关于Web搜索引擎的新内容和基于代理的信息检索。 书中的附录B是一个应用本书思想的一个大型应用，新西兰数字图书馆。这是一个互联网上可以访问的公开信息资源，使用MG作为其内核。它试图展示MG软件在信息检索方法的易用性和灵活性。附录解释了提供而来一些功能和机制。 最后，从我们在教学中使用该书所获得的经验上来讲，我们提供了一个“指导附件”包含了关于本书的问题复习、实验和使用中遇到的问题。这是一本单独的小册子，教师们可以向Tim C.Bell索要 。地址是：Department of Computer Science, University of Canterbury, Christchurch, New Zealand。 老了会聪明点吗？我们不能预测在本书的第三版Managing Gigabytes会做那些改变，这个工作也许将在2003年开展。 致谢 写致谢总是一件令人愉快的事情，许许多多的人都帮助过我们，更高兴有机会能向他们表示感谢。许多在数据压缩和信息检索领域享有盛名的同事在本书的编写过程中给予了大量的鼓励和帮助，尤其是Abe Bookstein，Nigel Horspool，Tomi Klein，Glen Langdon，Timo Raita和Jim Storer。从他们身上我们学到了许多东西，并把其中一部分体现在本书中。特别需要指出的是John Cleary，RadFord Neal，Ron Sacks-Davis和Justin Zobel，我们长期在一起努力工作，这些成绩也是他们的。Bob Kurse在本书一个重要问题上给出了很有价值的建议，Rod Harries和Todd Bender 为词汇索引提供了有用的信息和建议。在这5年间，还有其他几位也为我们提供了直接或间接的帮助：Gill Bryant，Sally Jo Cunningham，Tony Dale，Daryl D’Souza，Mike Fleischmann，peter Gutmann,Jan Pedersen，Bill Pennebarker，Art Pollard，Marcelo Weinberger和Ross Wilkinson。David Abrahamson在本书编写工作的早期作了大量工作，他帮我们确定了书中应该包含哪些内容和不该包含哪些内容。他还鼓励我们进行文本图像压缩工作，并且为第七章提供了一些素材。我们还要感谢那些评论家，他们最先说服出版社支持我们。当手稿即将完成时，他们又一次给与我们帮助。Douglas Campbell 对第二版提供了特别细致和有价值的评价。Ron Murray，Rob Akscyn，Robert Gray，David Hawking，PaulKantor， Yann LeCun，Michael Lesk，Darryl Lovato，Karen SparckJones，Jan Pedersen和Peter Willett。 Morgan Kaufmann出版社的Jenifer Mann和Karyn Johnson 对第二版的排版工作付出了巨大的努力，Elisabeth Beller是本书的产品编辑，在整个过程中为我们提供了理想的服务。来自 IBM的Joan Mitchell在本书的编写、修改到出版过程中均给与了许多有价值的帮助。 我们的许多学生也给予了极大的帮助。加拿大Calgary大学的Mary-Ellen Harrison和Mark James以及新西兰Canterbury大学的Hugh Emberson在我们研究文本图像压缩的过程中给予了极大的帮助。新西兰Waikato大学的Stuart Inglis和Abdul Saheed完成了文档布局识别和采用基于模型压缩技术实现的模式匹配。Caig Nevill Manning 参与我们早期关于索引压缩技术的研究并给予了很多实际的帮助。澳大利亚墨尔本大学的Peter Thompson为第五章提供了素材。我们还要对那些参与本书许多实验的同学们表示感谢，他们是：Tim A .H.Bell(来自墨尔本大学，请不要与本书的作者Tim C.Bell混淆)，Gwenda Bensemann，Mike Ciaarella，Craig Farrow，Andrew Kelly，Alex McCooke，Chris Stephens，John Tham，Bert Thompson，Lang Stuiver，Andrew Turpin和Glenn Wightwick，他们一起努力的工作聚沙成塔为本书提供了许多宝贵的意见。 在完成第二版的同时，我们要特别感谢Auckland大学的Peter Fenwick，他协助提供了关于Burrows-Wheeler转换的素材。Nasir Memon友好提供了第六章的一些信息，JPEG-LS中大量的信息来源于他写的一篇论文。PaulHoward对尚处襁褓中的文本图像压缩新标准的描述进行了审阅。Harold Thimbleby对附录为提供了有价值的评价，Yvonne Simmons对索引部分提供了帮助。Andrew Turpin 对huffword程序提供了改进的实现方法，以及关于第九章中限长编码的结果提供了帮助。Owen de Kretser和Lang Stuiver 对第三章和第四章中许多结果进行了重新计算。Tim A.H. Bell对本书的全篇进行了事先地校对工作，Tetra Lindarto，Elizabeth Ng和Bronwyn Webster对校对工作也提供了帮助。Nelson Beebe就是有价值信息的一个来源，从本书第一版出版之日起就不断给我们鼓励。 第一个mg系统是在澳大利亚研究学会和联合信息技术研究院的支持下开发成功的，得到了Lachlan Andrew，Gray Eddy和Neil Sharman的帮助。从那以后，又有许多人参与进来：Owen de Kretser，Tim Shimming和William Weber，以及起来对该项目有直接贡献的人们。还有许许多多在各个方面做出贡献的人们，由于篇幅所限不能一一列举他们。最小完美哈希函数子程序由昆士兰大学的Bohdan Majewski所写，非常感谢他提供在本书中使用这些程序，还有许许多多的人提供了超出我们预期的关于技术细节方面的巨大帮助。 第六章的全部图都由Neil Sharman制作，包括第二章和附录A的若干图。第七章和第八章的很多图例由Kerry Guise和Stuart Inglis制作。 图1-1的复制获得了T.&T.Clark Ltd的许可。图1-2的复制获得了康奈尔大学出版社的许可。图1-3的复制获得了Garland出版社的许可。图1-5由Gail Williams所绘制。图1-6的复制活动了Faber and Faber有限公司和Crown出版社的许可。图3-4文本的复制获得了Ziff通讯公司的许可。图6-1，6-18和6-20的图像来源于南加利福利亚图像处理研究所（USC-IPI）图像数据库。图6-11中的杂志页也用在了图8-1，8-2和8-5是来自于加拿大人工智能杂志。图7-1的复制获得了都柏林三一大学董事会的许可。图8-16的复制获得了ACM的许可（版权1987，Computing Machinery联合机构）。图8-25和图8-26来源于《IEEE computer》，复制获得了电子电器工程师协会的许可。 部分研究工作得到了澳大利亚研究协会和加拿大自然科学与工程研究协会的资助。此外，Calagray，Canterbury，Melbourne和Waikato大学的计算机科学系也非常支持我们的工作。 最后，我们由衷地感谢我们的家人。他们深知有一位家庭成员在家中写作的涵义，支持我们编写本书。感谢她们的支持：Judith，Pam和ThauMee。你们在各个方面提供了巨大的帮助，这本书也同样是你们的。同样也感谢我们的孩子们：Andrew，Anna，Anne，Kate（在本书第一版出版后不久就来到这个世界），Michael和Nikk，他们的成长过程本身就沉浸在信息时代中，让我们不断地接触现实，并持续地提醒我们不知是管理千兆数据才那么重要。 关于作者 Ian H.Witten 是新西兰Waikato大学计算系科学系教授，是ACM、新西兰皇家学会会员。是英国、美国、加拿大和新西兰的专业计算、信息检索和工程协会会员。他是 《The Reactive Keyboard》和《Text Compression》的作者之一，这两本书分别出版于1992年和1990年。各大会议和期刊论文都能看到他的论文。 Alistair Moffat是墨尔本大学计算科学系的副教授。在各大会议和期刊中发表了大量论文，这些论文包括的领域有：关于文本和图像压缩的算法和数据结构，字典和优先级队列的自适应数据结构，以及自适应搜索和排序算法。 Timothy C.Bell是Canterbury大学计算机科学系系主任。是出版于1990年的《Text Compression》一书的作者。在各大期刊和会议上发表了多篇论文，这些论文涉及文本和图像压缩，计算机和音乐，计算机教育等。 目 录第1章 概览 1 1.1 文档数据库（DOCUMENT DATABASES） 7 1.2 压缩（COMPRESSION） 10 1.3 索引（INDEXES） 12 1.4 文档索引 16 1.5 MG海量文档管理系统 20 1.6 进一步阅读 21 第2章 文本压缩 23 2.1 模型 26 2.2 自适应模型 29 2.3 哈夫曼编码 32 范式哈夫曼编码 38 计算哈夫曼编码长度 44 总结 51 2.4 算术编码 51 算术编码是如何工作的 53 实现算术编码 56 保存累积计数 59 2.5 符号模型 61 部分匹配预测 61 块排序压缩 64 动态马尔科夫压缩 69 基于单字的压缩 71 2.6 字典模型 73 自适应字典编码器的LZ77系列 74 LZ77的Gzip变体 78 自适应字典编码器的LZ78系列 79 LZ78的LZW变体 81 2.7 同步 84 创造同步点 84 自同步编码 87 2.8 性能比较 89 压缩性能 91 压缩速度 94 其他性能方面的考虑 97 2.9 进一步阅读 98 第3章 索引 102 3.1 样本文档集合 106 3.2 倒排文件索引 110 3.3 压缩倒排文件 115 无参模型（Nonparameterized models） 117 全局贝努里模型 120 全局观测频率模型（Global observed frequency model） 123 局部贝努里模型（Local Bernoulli model） 124 有偏贝努里模型（Skewed Bernoulli model） 125 局部双曲模型（Local hyperbolic model） 127 局部观测频率模型（Local observed frequency model） 128 上下文相关压缩（Context-sensitive compression） 130 3.4 索引压缩方法的效果 133 3.5 签名文件和位图 134 签名文件 135 位片签名文件（Bitsliced signature files） 139 签名文件分析 144 位图 147 签名文件和位图的压缩 148 3.6 索引方法的比较 151 3.7 大小写折叠、词根化和停用词 153 大小写折叠 154 词根化 154 影响索引长度的因素 155 停用词（stop word） 156 3.8 进一步阅读 159 第4章 查询 162 4.1 访问字典的方法 166 访问数据结构 167 前端编码（Front coding） 170 最小完美哈希函数 173 完美哈希函数的设计 176 基于磁盘的字典存储 181 4.2 部分指定的查询术语 182 字符串暴力匹配（Brute-force string matching） 182 用n-gram索引 183 循环字典（Rotated lexicon） 184 4.3 布尔查询（BOOLEAN QUERY） 186 合取查询（conjunctive query） 187 术语处理顺序 188 随机访问和快速查找 189 分块倒排索引 192 非合取查询（Nonconjunctive query） 194 4.4 信息检索和排名 195 坐标匹配（Coordinate matching） 195 内积相似度 196 向量空间模型 202 4.5 检索效果评价 205 召回率和精确率 205 召回率-精确率曲线 207 TREC项目 208 万维网搜索（World Wide Web Searching） 212 其他有效性评价方法 215 4.6 余弦法实现 216 文档内频率 217 余弦值的计算方法 220 文档权重所需的内存 222 累加器内存 227 快速查询处理 228 按频率排序的索引 229 排序 233 4.7 交互式检索 236 相关性反馈 237 概率模型 239 4.8 分布式检索 241 4.9 进一步阅读 245 第5章 索引构造 248 计算模型 251 索引构造方法概览 252 5.1 基于内存的倒排 253 5.2 基于排序的倒排 256 5.3 索引压缩 261 压缩临时文件 261 多路归并 264 原地多路归并 265 5.4 压缩的内存内倒排 271 大内存倒排 271 基于字典的切分（Lexicon-based partitioning） 276 基于文本的切分 278 5.5 倒排方法的比较 281 5.6 构造签名文件和位图 282 5.7 动态文档集合 284 扩展文本（Expanding the text） 284 索引扩展（Expanding the index） 285 5.8 进一步阅读 290 第6章 图像压缩 292 6.1 图像类型 293 6.2 CCITT二值图像的传真标准 297 6.3 二值图像的上下文压缩 301 上下文模型 304 二值上下文模型 307 “超视力”压缩（Clairvoyant compression） 309 6.4 JBIG：二值图像标准 310 分辨率降低（Resolution reduction） 311 模板和自适应模板 316 编码及概率估计 317 6.5 连续色调图像的无损压缩 318 GIF和PNG无损图像格式 319 FELICS：快速、有效且无损图像压缩系统 321 CALIC：基于上下文自适应无损图像解码器 325 JPEG-LS：无损图像压缩新标准 326 6.6 JPEG：连续色调图像标准 328 6.7 图像的递增传输 334 金字塔编码 335 金字塔编码的压缩 335 中位数聚合 337 误差模型 338 6.8 图像压缩技术总结 339 6.9 进一步阅读 341 第7章 文本图像 343 7.1 文本图像压缩概念 345 7.2 有损和无损压缩 349 7.3 标记抽取 351 跟踪标记的边界 351 清除图像中的标记 354 按自然阅读顺序排序标记 356 7.4 模板匹配 357 全局模板匹配 358 局部模板匹配 360 基于压缩的模板匹配 361 库模板筛法 364 评价模板匹配方法 365 7.5 从标记到符号 369 库构造 369 符号及其偏移量 371 7.6 编码文本图像分量 372 库 372 符号数 373 符号偏移 373 原始图像 374 7.7 效果：有损和无损的模式 376 7.8 系统考虑 381 7.9 JBIG2：图像文本压缩标准 383 7.10 进一步阅读 385 第8章 混合图文 386 8.1 方向 388 用Hough变换检测直线 389 左侧留白查找 391 投影轮廓 392 从斜率直方图到文本谱 397 8.2 切分 401 自下向上的切分方法 401 自上向下的组合的切分方法 403 基于标记的切分 404 使用短文本字符串切分 406 利用文本句法切分 409 8.3 分类 410 8.4 进一步阅读 413 第9章 系统实现 415 9.1 文本压缩 416 选择压缩模型 417 选择编码器 420 哈夫曼编码的限制 422 长度限制的编码 428 9.2 文本压缩效果 433 压缩有效性 433 解压速度 437 解压内存 437 动态文档集合 440 9.3 图像和文本图像 442 压缩二值图像 444 压缩灰度图像 445 压缩文本图像 445 9.4 构造索引 447 9.5 索引压缩 449 9.6 查询处理 451 布尔查询 451 排名查询 454 9.7 进一步阅读 456 第10章 信息爆炸 458 10.1 信息技术发展2 000年 458 10.2 INTERNET：一种全球信息资源 460 10.3 纸张问题 463 10.4 面对信息爆炸 465 网页搜索引擎 465 基于代理的信息检索 467 数据挖掘 469 10.5 数字图书馆 469 10.6 更好地管理海量数据 471 10.7 小就是美 473 10.8 对生活的个人信息支持 475 10.9 进一步阅读 476 附录A MG系统指南 478 A.1 安装MG系统 478 A.2 一个简单的存储和检索例子 480 A.3 数据库创建 485 A.4 对一个索引文档集合进行查询 489 A.5 非文本文件 491 A.6 图像压缩程序 493 附录B 新西兰图书馆 494 B.1 什么是NZDL 494 其他文档集合 497 文档集合的发展 501 音频集合（audio collections） 502 音调索引（Melody Index） 503 B.2 NZDL是如何工作的？ 505 原始文档 505 搜索和索引 506 B.3 影响 508 B.4 进一步阅读 508 |
| 随便看 |
百科全书收录4421916条中文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。