深入搜尋引擎

《深入搜尋引擎》是2009年電子工業出版社出版的圖書，作者是[美]Ian H. Witten（艾倫 H.威頓）,Alistair Moffat（亞里斯蒂爾.莫夫特）, Timothy C. Bell (Author)（提摩太 C.貝爾）。

基本介紹

• 中文名：深入搜尋引擎
• 出版社： 電子工業出版社　
• 出版時間： 2009-5-1
• 頁數：508頁
• 開本：16開
• ISBN：9787121084911 
• 價格：￥75.00元
• 分類：圖書 >> 計算機 >> 搜尋引擎
• 翻譯：梁斌

編輯推薦

本書作為史丹福大學信息檢索課程的教材之一，具有一定的閱讀難度，主要面向信息檢索專業高年級本科 生和研究生、搜尋引擎業界的專業技術人員和從事海量數據處理相關專業的技術人員。

內容簡介

本書是史丹福大學信息檢索和挖掘課程的首選教材之一，並已成為全球主要大學信息檢索的主要教材。本書理論和實踐並重，深入淺出地給出了海量信息數據處理的整套解決方案，包括壓縮、索引和查詢的方方面面。其最大的特色在於不僅僅滿足信息檢索理論學習的需要，更重要的是給出了實踐中可能面對的各種問題及其解決方法。

作者簡介

Ian H.Witten 是紐西蘭Waikato大學計算系科學系教授，是ACM、紐西蘭皇家學會會員。是英國、美國、加拿大和紐西蘭的專業計算、信息檢索和工程協會會員。他是 《The Reactive Keyboard》和《Text Compression》的作者之一，這兩本書分別出版於1992年和1990年。各大會議和期刊論文都能看到他的論文。

原著推薦序

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位作者在內的信息檢索專家們無私地分享了他們的技術成果，並且感謝博文視點出版社大力引進，編輯孫學瑛女士及方方面面工作人員給予的幫助。

最後引用本書中的一段原話作為結尾：“在信息科學技術的歷史上，從來沒有像今天這樣，創造如此大的價值的如此多的技術卻掌握在如此少的人的手裡。”希望能夠和原著的作者一樣做出自己一份微薄的貢獻。

梁斌

2009年2月15日

前言

計算機革命使得全社會都再也不能離開信息。然而，大部分的信息還是以其原始的格式存儲著：即數據(data)。原始信息是海量的。這些數據主要產生於商業活動、法律訴訟和政府活動。隨之而來的還有不計其數的複製品，這主要是報導、雜誌和報紙產生的。最後這些一切存儲在檔案館、圖書館和計算機中。面對的挑戰是如何高效和有效地處理大量的信息，以便能方便、廉價地定位和抽取有效的信息。

從空間的角度看，在紙張上存儲文檔的傳統方法是昂貴的，更重要的是，當需要定位和檢索所需要的信息時，需要付出高昂的代價。因此能夠經濟地存儲和訪問文檔就變得越來越重要。幾百英尺高的一大堆書中所包含的文本只需要一塊磁碟就可以存下，從物理空間占用的角度看，電子媒體的這種存儲能力是驚人的。和人工的文檔索引方法相比，這種方法即具有伸縮性（全部的單詞都可以作為關鍵字）和可靠性（因為索引構造的過程完全不需要人的參與，也就沒有人為干擾）。此外，當今社會的各類組織不得不處理各種來源的電子信息，例如，機器可讀文本、傳真、其他掃描文檔和數字圖像。和紙媒體相比，使用電子媒體在存儲和訪問上都特別有效。

這本書討論如何管理大量文檔，G位元組的數據。1G大約是1000M位元組，這足夠存儲1000本書籍，相當於在從地板摞到天花板這么高的書籍。日常生活的辭彙也在不斷地增長的同時，大規模存儲設備容量也在不斷增長。就在20年前，百兆數據的需求看上去是那么的奢侈，甚至是幻想。今天個人電腦已經配置上了G位元組的存儲設備，甚至一些小的機構也需要存儲數G的數據。自從本書第一版問世以來，全球資訊網爆炸般地創造了萬億位元組（terabytes）的公開數據，讓越來越多的人意識到處理如此大規模數據的難題是特別重要的。

管理如此大量數據主要需要面對兩個挑戰，這兩個挑戰都在本書中進行了討論。第一個挑戰是如何有效地存儲數據。這主要通過壓縮的方法來實現。第二個挑戰是提供一種通過關鍵字搜尋的方法來提供快速訪問信息的方法。因此，一個特別定製的索引尤為關鍵。傳統的壓縮和搜尋方法需要調整以適應這些挑戰。這也是本書中主要討論的兩個主題。本書討論的這些技術套用的結果是確保計算機系統可以存儲數百萬的文檔和能夠在秒級的時間內檢索到包含任給關鍵字（或關鍵字組合）的文檔，甚至可以在不到1秒的時間內完成查詢。

舉個例子來說明本書中所討論的這些方法的威力。掌握了這些方法後，你可以對數G位元組的文本創建一個資料庫，並且使用它來回響類似這樣的查詢請求，“在僅適用工作站的條件下，用數秒時間就能在全部文檔中檢索同時包含‘managing’和‘gigabytes’的段落”。事實上，如果能夠對文本創建恰當的索引，這並不是什麼神奇的事情。最令人著迷的是這些創建的資料庫（包括索引和完整文本），當然都是壓縮過的，只有不到原文本的一半大小。不僅如此，創建這樣一個資料庫只需要數小時即可。最令人驚訝的可能是如果數據集不壓縮的話，查詢時間還會更少。

大部分本書討論的技術都已經被提出、實驗和套用到實踐中。為快速搜尋和檢索而構造的文本索引被仔細的檢查過，這些信息構成了本書的核心。話題還包括文本壓縮和建模，壓縮圖像的方法，壓縮文本圖像（例如掃描或傳真文檔）和為了區分圖片圖表和文本而進行的頁面布局識別等。

全文索引不可避免會非常巨大，因此製作的成本也很高。然而，本書揭示了全部單詞，如果需要的話，還包括全部數字建立完整索引的奧秘，並闡述了如何用如此小的存儲代價支持如此快速的訪問能力的技巧。

本書的目標是介紹管理大量文檔和圖片數據集的最新方法。在閱讀本書以後，你將掌握這些技術並同時對它們的威力產生敬意。

隨書軟體

一個闡述本書思想的完整的系統，mg（代表”managing gigabytes”），已經被開發出來。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”，這看上更加友好。和第一本書出版的時候一樣，現在正當時。

雖然第二版的基本核心內容和第一版相同，但是我們盡最大努力更新了部分內容以反應這五年來發生的變化。當然，我們改正了一些錯誤，這些錯誤來自於從線上勘誤的積累。事實上，發現的錯誤出乎預料地少，我們希望第二本錯誤會更少。

第二章追加了關於文本壓縮的最近發展，包括塊排序方法（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，他們的成長過程本身就沉浸在資訊時代中，讓我們不斷地接觸現實，並持續地提醒我們不知是管理千兆數據才那么重要。

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