UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`SAP AMERICA INC. et. al,
`
`Petitioner
`
`v.
`
`REALTIME DATA LLC d/b/a IXO
`
`alleged Patent Owner
`
`DECLARATION OF SCOTT BENNETT, Ph.D.
`
`21 March 2016
`
`ORACLE I 119
`
`Page 1 0f45
`
`

`
`1.
`
`2.
`
`1, Scott Bennett, hereby declare as follows:
`
`I am a retired academic librarian working as a Managing Partner of
`
`the firm Prior Art Documentation LLC at 71 1 South Race Street, Urbana, IL,
`
`61801-4132.
`
`I was previously employed as follows:
`
`University Librarian, Yale University, New Haven, CT., 1994-2001
`
`Director, The Milton S. Eisenhower Library, The Johns Hopkins
`
`University, Baltimore, MD, 1989-1994
`
`Assistant University Librarian for Collection Management, Northwestern
`
`University, Evanston, IL, 1981-1989
`
`Instructor, Assistant, and Associate Professor of Library Administration,
`
`University of Illinois at Urbana-Champaign, Urbana, IL, 1974-1981
`
`Assistant Professor of English, University of Illinois at Urbana-
`
`Champaign, 1967-1974
`
`3.
`
`Over the course of my work as a librarian, professor of English,
`
`researcher, and author of nearly fifty scholarly papers and other publications, I
`
`have had extensive experience with cataloging records and online library
`
`management systems built around Machine—Readable Cataloging (MARC)
`
`standards.
`
`I also have substantial experience in authenticating printed documents
`
`Page 2 of 45
`
`

`
`and establishing the date when they were accessible to ordinarily skilled
`
`researchers.
`
`4.
`
`Exhibit A is my full resume. Further information about my firm is
`
`available at wwwpriorartdocumentation.com.
`
`5.
`
`I have been retained by Baker Botts LLP to authenticate and establish
`
`the dates of public accessibility of certain documents in inter partes review
`
`proceedings for U.S. Patent No. 6,597,812. For this service, I am being paid my
`
`usual hourly fee of $85/hour. My compensation in no way depends on the
`
`substance of my testimony or the outcome of this proceeding.
`
`PRELIMINARIES
`
`6.
`
`Library catalog records. Libraries world-Wide use the MARC format
`
`for catalog records; this machine readable format was developed at the Library of
`
`Congress in the 19605. The MARC 040a Field identifies the library or other entity
`
`that created the original catalog record for a given document and transcribed it into
`
`machine readable form. The MARC 008 Field identifies the date when this first
`
`catalog record was entered on the file. This date persists in all subsequent uses of
`
`the first catalog record, although newly created records for the same document will
`
`show a new date.
`
`7.
`
`WorldCat is the world’s largest public online catalog, maintained by
`
`the Online Computer Library Center, Inc., or OCLC (see
`
`Page 3 of 45
`
`

`
`https://en.wikipedia.org/wiki/OCLC). Its records appear in many different catalogs,
`
`including the Statewide Illinois Library Catalog. WorldCat records use the MARC
`
`format, and the date a given catalog record was created (corresponding to the
`
`MARC 008 Field) appears in some detailed WorldCat records as the Date of Entry.
`
`8.
`
`When a book has been cataloged, it will normally be made available
`
`to readers soon thereafter—normally within a few days or (at most) within a few
`
`weeks of cataloging.
`
`9.
`
`The public availability of MARC—formatted catalog records and
`
`detailed WorldCat records showing the Date of Entry varies greatly.
`
`REVIEW OF INDIVIDUAL DOCUMENTS
`
`10. Document 1. Nelson, Mark. The Data (.‘ompresst'on Book. San
`
`Marco, CA: M&T Books, 1992.
`
`Authentication
`
`11.
`
`Document 1 is a book published in 1992. Attachment la is a copy of
`
`the cover, title page, preface, table of contents, and Chapter 1 from the Concordia
`
`University [Illinois] Library. Attachment lb is a copy of that library’s catalog
`
`record, in MARC format, for Document 1.
`
`Public acce.5'.s'ib:'h'ty
`
`12. Attachment 1c is a copy of the Statewide Illinois Library Catalog
`
`record for Document 1, showing the book is held by 160 libraries world-wide.
`
`Page 4 of 45
`
`

`
`13. Attachment 1b indicates, in the MARC 0403 Field, that Document 1
`
`was first cataloged by the Library of Congress (OCLC code DLC). The MARC
`
`008 Field indicates this catalog record was created on 24 May 1991. The verso of
`
`Document 1’s title page (Attachment la) indicates this is a cataloging-in-
`
`publication record; such records are customarily created before a book’s
`
`publication.
`
`14. Attachment Id is a copy of the United States Copyright Office
`
`registration information for Document 1, showing the book was published on 10
`
`October 1991 and registered for copyright on 21 January 1993. Books published
`
`in the last quarter of the year often bear the following year as the publication date,
`
`as is the case with Document 1.
`
`15. Attachment 1e is a list of 12 publications citing Document 1 identified
`
`by Scopus, a major index, abstract, and full—text service. These documents were
`
`published between 1993 and 1995. Attachment la includes (on the last two pages)
`
`date stamped circulation slips showing that the Concordia University [Illinois]
`
`Library copy of Document 1 was actively in use in 1994.
`
`16. Based on the evidence presented here—a widely held publication,
`
`library cataloging, copyright registration, and citations and circulation data—
`
`it is my opinion that Document 1 was bibliographically identifiable by 24 June
`
`1991 and accessible to an ordinarily skilled researcher by the book’s
`
`Page 5 of 45
`
`

`
`publication date, 10 October 1991. Document 1 was demonstrably in active
`
`use by researchers as early as 1993.
`
`ATTACHMENTS
`
`17.
`
`The following attachments are true and accurate representations of
`
`library material and online documents and records, as they are identified above.
`
`All attachments were created on 17-19 March 2016, and all URLs referenced in
`
`this declaration were available 20 March 2016.
`
`Attachment la: Copy of Document 1 from the Concordia University [Illinois]
`
`Library
`
`Attachment lb: Concordia University [Illinois] Library catalog record for
`
`Document 1
`
`Attachment lc: Statewide Illinois Library catalog record for Document 1
`
`Attachment ld: United States Copyright Office record for Document 1
`
`Attachment le: List of publications citing Document 1 identified by Scopus.
`
`ATTESTATION
`
`18.
`
`This declaration and my opinions herein are made to the best of my
`
`knowledge and understanding, and based on the material available to me, at the
`
`time of signing this declaration. I declare under penalty of perjury under the laws
`
`of the United States of America that all statements made of my own knowledge are
`
`true and that all statements made on information and belief are believed to be true.
`
`6
`
`Page 6 of 45
`
`

`
`I understand that willful false statements and the like are punishable by fine or
`
`imprisonment, or both (18 U.S.C. § 1001).
`
`21 March 2016
`
`C§ufl (E-44mm
`
`Date
`
`Name
`
`Page 7 of 45
`
`

`
`EXHIBIT A: RESUME
`
`SCOTT BENNETT
`
`Yale University Librarian Emeritus
`
`71 1 South Race
`
`Urbana, Illinois 61801-4132
`
`rairienet.or I
`Zscottb
`21?‘-36?-9896
`
`EMPLOYIVIENT
`
`Retired, 2001. Retirement activities include:
`
`0 Managing Partner in Prior Art Documentation Services, LLC, 2015-. This firm provides
`documentation services to patent attorneys; more information is available at
`httpzffwww.priorartdocumentation.com
`
`0 Consultant on library space design, 2004- . This consulting practice is rooted in a research,
`publication, and public speaking program conducted since I retired from Yale University in
`20{}1.
`I have served more than 50 colleges and universities in the United States and abroad
`with projects ranging in likely cost from under $50,000 to over $100 million. More
`information is available at httpzffwww.libraryspaccplarmingcomf
`
`Senior Advisor for the library program of the Council of Independent Colleges, 2001-2009
`0
`0 Member of the Wartburg College Library Advisory Board, 2004-
`
`- Visiting Professor, Graduate School of Library and Information Science, University of
`Illinois at Urbana-Champaign, Fall 2003
`
`University Librarian, Yale University, 1994-2001
`
`Director, The Milton S. Eisenhower Library, The Johns Hopkins University, Baltimore, Maryland,
`1989-1994
`
`Assistant University Librarian for Collection Management, Northwestern University, Evanston,
`Illinois, 1981-1989
`
`Instructor, Assistant and Associate Professor of Library Administration, University of Illinois at
`Urbana—Champaign, 1924-1981
`
`Assistant Professor of English, University of Illinois at Urbana-Champaign, 1967-1974
`
`Woodrow Wilson Teaching Intern, St. Paul’s College, Lawrenccvillc, Virginia, 1964-1965
`
`EDUCATION
`
`University of Illinois, M.S., 1976 (Library Science)
`Indiana University, M.A., 1966; Ph.D., 196? (English)
`Oberlin College, A.B. magna cum laude, 1960 (English)
`
`HONORS AND AWARDS
`
`Page 8 of 45
`
`

`
`Morningside College (Sioux City, IA) Doctor of Humane Letters, 2010
`
`American Council of Learned Societies Fellowship, 1978-1979; Honorary Visiting Research
`Fellow, Victorian Studies Centre, University of Leicester, 1979; University of Illinois Summer
`Faculty Fellowship, 1969
`
`Indiana University Dissertation Year Fellowship and an Oberlin College Haskell Fellowship, 1966-
`1967; Woodrow Wilson National Fellow, 1960-1961
`
`PROFESSIONAL ACTIVITIES
`
`American Association for the Advancement oi’ Science: Project on Intellectual Property and
`Electronic Publishing in Science, 1999-2001
`
`American Association of University frofessors: University of Illinois at Urbana-Champaign
`Chapter Secretary and President, 1975-1978; Illinois Conference Vice President and President, 197 8-
`1984; national Council, 1982-1985, Committee F, 1982-1986, Assembly of State Conferences
`Executive Committee, 1983-1986, and Committee H, 1997-2001 ; Northwestern University Chapter
`Secretaryr’Treasurer, 1985 -1986
`
`Association of American Universities: Member of the Research Libraries Task Force on
`
`Intellectual Property Rights in an Electronic Environment, 1993-1994, 1995-1996
`
`Association of Research Libraries: Member of the Preservation Committee, 1990-1993; member of
`
`the Information Policy Committee, 1993-1995; member of the Working Group on Copyright, 1994-
`2001; member of the Research Library Leadership and Management Committee, 1999-2001; member
`of the Board of Directors, 1998-20(}0
`
`Carnegie Mellon University: Member of the University Libraries Advisory Board, 1994
`
`Center for Research Libraries: Program Committee, 1998-2000
`
`Johns Hopkins University Press: Ex-officio member of the Editorial Board, 1990-1994; Co-
`director of Project Muse, 1994
`
`Library Administration and Management Association, Public Relations Section, Friends of the
`Library Committee, 1977-1978
`
`Oberlin College: Member of the Library Visiting Committee, 1990, and of the Steering Committee
`for the library's capital campaign, 1992-1993; President of the Library Friends, 1992-1993, 2004-
`2005; member, Friends of the Library Council, 2003-
`
`Research Society for Victorian Periodicals: Executive Board, 1971-1983; Co-chairperson of the
`Executive Committee on Serials Bibliography, 1976-1982; President, 1977-1982
`
`A Selected Edition of W.D. Howells (one of several editions sponsored by the MLA Center for
`Editions of American Authors): Associate Textual Editor, 1965-] 970; Center for Editions of
`
`American Authors panel of textual experts, 1968-1970
`
`Victorian Studies: Editorial Assistant and Managing Editor, 1962-1964
`
`9
`
`Page 9 of 45
`
`

`
`Wartburg College: member, National Advisory Board for the V0 gel Library, 2004-
`
`Some other activities: Member of the Illinois State Library Statewide Library and Archival
`Preservation Advisory Panel; member of the Illinois State Archives Advisory Board; member of a
`committee advising the Illinois Board of Higher Education on the cooperative management of
`research collections; chair of a major collaborative research project conducted by the Research
`Libraries Group with support from Conoco, Inc.; active advisor on behalf of the Illinois
`Conference AAUP to faculty and administrators on academic freedom and tenure matters in northern
`Illinois.
`
`Delegate to Maryland Governor’s Conference on Libraries and Information Service; principal in
`initiating state-wide preservation planning in Maryland; principal in an effort to widen the use of
`mass deacidifieation for the preservation of library materials through cooperative action by the
`Association of Research Libraries and the Committee on Institutional Cooperation; co-instigator
`of a campus-wide information service for Johns Hopkins University; initiated efforts with the
`Enoch Pratt Free Library to provide information services to Baltimorc’s Empowerment Zones;
`speaker or panelist on academic publishing, copyright, scholarly communication, national and
`regional preservation planning, mass deacidifieation.
`
`Consultant for the University of British Columbia (1995), Princeton University (1996), Modern
`Language Association, (1995, 1996), Library of Congress (1997), Center for Jewish History
`(1998, 2000-), National Research Council (1998); Board of Directors for the Digital Library
`Federation, 1996-2001; accreditation visiting team at Brandeis University (1997); mentor for
`Northern Exposure to Leadership (1997); instructor and mentor for ARL’s Leadership and
`Career Development Program (1999-2000)
`
`At the Northwestern University Library, led in the creation of a preservation department and in the
`renovation of the renovation, for preservation purposes, of the Deering Library book stacks.
`
`At the Milton S. Eisenhower Library, led the refocusing and vitalization of client-centered services;
`strategic planning and organizational restructuring for the library; building renovation planning.
`Successfully completed a $5 million endowment campaign for the humanities collections and
`launched a $27 million capital campaign for the library.
`
`At the Yale University Library, participated widely in campus-space planning, university budget
`planning, information technology development, and the promotion of effective teaching and learning;
`for the library has exercised leadership in space planning and renovation, retrospective conversion of
`the card catalog, preservation, organizational development, recruitment of minority librarians,
`intellectual property and copyright issues, scholarly communication, document delivery services
`among libraries, and instruction in the use of information resources. Ovcrsaw approximately $70
`million of library space renovation and construction. Was co-principal investigator for a grant to plan
`a digital archive for Elsevier Science.
`
`Numerous to invitations speak at regional, national, and other professional meetings and at alumni
`meetings. Lectured and presented a series of seminars on library management at the Yunnan
`University Library, 2002. Participated in the 2005 International Roundtable for Library and
`Information Science sponsored by the Kanazawa Institute of Technology Library Center and the
`Council on Library and Infonnation Resources.
`
`10
`
`Page 10 of45
`
`

`
`PUBLICATIONS
`
`“Putting Leaming into Library Planning,” poriai; Libraries and the Academy, 15, 2 (April 2015),
`2 1 5-23 1 .
`
`“How librarians (and others!) love silos: Three stories from the field “ available at the Learning
`Spaces Collaborary Web site, http:iiwww.pka1lsc.org[
`
`“Learning Behaviors and Learning Spaces,” poriai: Libraries and the Academy,
`765-789.
`
`1 l, 3 (July 201 1),
`
`“Libraries and Learning: A History of Paradigm Change,” poriai: Libraries and the Academy, 9, 2
`(April 2009), 181-197. Judged as the best article published in the 2009 volume of poriai.
`
`“The Information or the Learning Commons: Which Will We Have?" Joarnai ofA cademic
`Librarianship, 34 (May 2008), 183-185. One ofthe ten most-cited articles published in JAL, 2007-
`2011.
`
`“Designing for Uncertainty: Three Approaches," Journal ofAcademic Librarianship, 33 (2007), 165-
`179.
`
`“Campus Cultures Fostering Information Literacy,” portal: Libraries and the Academy, 7 (2007),
`147-167. Included in Library Instruction Round Table Top Twenty library instruction articles
`published in 2007
`
`“Designing for Uncertainty: Three Approaches,” Journal’ ofA cademic Librarianship, 33 (2007),
`1 65-1 79.
`
`“First Questions for Designing Higher Education Learning Spaces," Journai ofAcademic
`Librarianship, 33 (2007), 14-26.
`
`“The Choice for Learning," Journal ofAcademic Librarianship, 32 (2006), 3-13.
`
`With Richard A. O’Connor, “The Power of Place in Learning," Planningfor Higher Education, 33
`(June-August 2005), 28-30
`
`“Righting the Balance,” in Library as Place: Reihinking Roles, Rethinking Space (Washington, DC:
`Council on Library and Information Resources, 2005), pp. 10-24
`
`Libraries‘ Designedfor Learning (Washington, DC: Council on Library and Information Resources,
`2003)
`
`“The Golden Age of Libraries,” in Proceedings cfthe inrernationai Conference on Academic
`Librarianship in the New MiIiennium.' Roies, Trends, and Global Coiiaboraiion, ed. Haipcng Li
`(Kunming: Yunnan University Press, 2002), pp, 13-21, This is a slightly different version of the
`following item.
`
`“The Golden Age of Libraries,” Joarnai ofA cadernic Librarianship, 24 (2001), 256-258
`
`. at the annual dinner of the Friends of the Oberlin College Library
`.
`“Second Chances. An address .
`November 13 1999,” Friends of the Oberlin C ollcgc Library, February 2000
`
`11
`
`Page 11of45
`
`

`
`“Authors” Rights,” The Journa.’ ofEieetronic Pubiishing (December 1999),
`http:iiwww.press.umich.eduij epi05-02ibennett.htmI
`
`“Information-Based Productivity,” in Technoiogy and Scholarly Communication, ed. Richard Elonan
`and Richard E. Quandt (Berkeley, 1999), pp. 73-94
`
`“Just-In-Time Scholarly Monographs: or, Is There a Cavalry Bugle Call for Beleaguered Authors and
`Publishers?” TheJournoI of Eiectronic Pubiishing (September 1998),
`http:iiwww.press. umicheduij ept04-0 libcnnctt. html
`
`“Re-engineering Scholarly Communication: Thoughts Addressed to Authors," Schoiariy Publishing,
`27 (1996), 185-196
`
`“The Copyright Challenge: Strengthening the Public Interest in the Digital Age," Library Journai, 15
`November 1994, pp. 34-37
`
`“The Management of Intellectual Property,” Computers in Libraries, 14 (May 1994), 18-20
`
`“Repositioning University Presses in Scholarly Communication,” Journai of Schoiariy Publishing, 25
`(1994), 243-248. Reprinted in The Essential JSP. Critical Insights into the World of Schoiariy
`Pubiishing. Volume I: University Presses (Toronto: University of Toronto Press, 2011), pp. 147-153
`
`“Preservation and the Economic Investment Model,” in Preservation Research and Deveioprnent.
`Round Tobie Proceedings, September 28-29, I 992, ed. Carrie Beyer (Washington, D.C.: Library of
`Congress, 1993), pp. 17-18
`
`“Copyright and Innovation in Electronic Publishing: A Commentary,” Journai ofAcademic
`Librarianship, 19 (1993), 87-91; reprinted in condensed form in Library Issues: Briefings for Facuity
`and Administrators, 14 (September 1993)
`
`with Nina Mathcson, “Scholarly Articles: Valuable Commodities for Universities,” (‘hronicie of
`Higher Education, 27 May 1992, pp. Bl—B3
`
`“Strategies for Increasing [Preservation| Productivity, "Minutes of the I I I 9th/' Meeting / of the
`Association (.fReseorch Libraries] (Washington, DC., 1992), pp. 39-40
`
`“Management Issues: The Director’s Perspective,” and “Cooperative Approaches to Mass
`Deaeidifieation: Mid-Atlantic Region,” in A Roundtabie on Mass Deacidification, ed. Peter G. Sparks
`(Washington, D.C.: Association of Research Libraries, 1992), pp. 15-18, 54-55
`
`“The Boat that Must Stay Afloat: Academic Libraries in Hard Times,” Schoiariy PubIi.s'hing, 23
`(1992),131-137
`
`“Buying Time: An Alternative for the Preservation of Library Material,” AC LS Newsietier, Second
`Series 3 (Summer, 1991), 10-11
`
`“The Golden Stain of Time: Preserving Victorian Periodicals" in Investigating Victorian Journaz'ism,
`ed. Laurel Brake, Alex Jones, and Lionel Madden (London: Macmillan, 1990), pp. 166-183
`
`12
`
`Page 12 of45
`
`

`
`“Commentary on the Stephens and Haley Papers” in Coordinating Cooperative ("oliection
`Development.‘ A National Perspective, an issue of Resource Sharing and Information Networks, 2
`(1985), 199-201
`
`“The Editorial Character and Readership of The Penny Magazine: An Analysis,” Victorian
`Periodicat'.s' Review, ]7 (1984), 127-141
`
`“Current Initiatives and Issues in Collection Management, ” Journal ofA cademic l.ibrarian.s'hip, l(}
`(1984), 257-261; reprinted in l.il)rary Lit." The Best of85
`
`“Revolutions in Thought: Serial Publication and the Mass Market for Reading” in The Victorian
`Periodical Press: Samplings and Soundings, ed. Joanne Shattock and Michael Wolff (Leicester:
`Leicester University Press, 1982), pp. 225-257
`
`“Victorian Newspaper Advertising: Counting What Counts,” Publishing History, 8 (1980), 5-18
`
`“Library Friends: A Theoretical History" in Organizing the Library is Support.‘ Donors, Volunteers,
`Friends, ed. D.W. Krummel, Allerton Park Institute Number 25 (Urbana: University of Illinois
`Graduate School of Library Science, 1980), pp. 23-32
`
`“The Learned Professor: being a brief account of a scholar [Harris Francis Fletcher] who asked for
`the Moon, and got it,” Non Solus, 7 (1980), 5-12
`
`“Prolegomenon to Serials Bibliography: A Report to the [Research] Society [for Victorian
`Periodieals],” Victorian Periodicals Review, I2 (1979), 3-15
`
`“The Bibliographic Control of Victorian Periodicals" in Victorian Periodicals: A Guide to Research,
`ed. J. Don Vann and Rosemary T. VanArsdel (New York: Modern Language Association, 1978), pp.
`2 1-5 1
`
`“John Murray’s Family Library and the Cheapening of Books in Early Nineteenth Century Britain,”
`Studies in Bibliography, 29 (19't'6), 139-166. Reprinted in Stephen C olclough and Alexis Weedon,
`eds., the History ofthe Book in the West: I800-I914, Vol. 4 (Famham, Surrey: Ashgate, 2010), pp.
`30?-3 34.
`
`with Robert Carringer, “Dreiser to Sandburg: Three Unpublished Letters,” Library Chronicle, 40
`(1976), 252-256
`
`“David Douglas and the British Publication of W. D. Howells‘ Works," Studies in Bibliography, 25
`(1972), 107-124
`
`as primary editor, W. D. Howells, Indian Summer (Bloomington: Indiana University Press, 1971)
`
`“The Profession of Authorship: Some Problems for Descriptive Bibliography” in Research Methods
`in Librarian.ship.' Historical and Bilaiiographic Methods in Liltrary Research, ed. Rolland E. Stevens
`(Urbana: University of Illinois Graduate School of Library Science, 1971), pp. 74-85
`
`edited with Ronald Gottesman, Art and Error: Modern Textual Editing (Bloomington: Indiana
`University Press, 1970)--also published in London by Methuen, 1970
`
`13
`
`Page 13 of45
`
`

`
`“Catholic Emancipation, the Quarterly Review, and Britain’s Constitutional Revolution,” Victorian
`Studies, 12 (1969), 283-304
`
`as textual editor, W. D. Howells, The Attrurian Romances (Bloomington: Indiana University Press,
`1968); introduction and annotation by Clara and Rudolf Kirk
`
`as associate textual editor, W. D. Howells, Their Wedding Journey (Bloomington: Indiana University
`Press, 1968); introduction by John Reeves
`
`“A Concealed Printing in W. D. Howells,” Papers of the Bibliographic Society ofA merica, 61
`(l96't'), 56-60
`
`editor, Non Sofas, A Publication of the University of Illinois Library Friends, 1974-1981
`
`editor, Robert B. Downs Publication Fund, University of Illinois Library, 1975-1981
`
`reviews, short articles, etc. in Victorian Studies, Journat ofEnglish and German Philotogy, Victorian
`Periodicals Newsletter, Criilectitin Management, Nineteenth—Century Literature, College & Research
`Libraries, Schoiartjr Publishing Today, ARL Newstetter, Serials Review, Library Issues, Sfocietyforf
`Sfchotartyi Pfubtishing] Newsletter, and Victorian Britain: An Encyctopedia
`
`14
`
`Page 14 of45
`
`

`
`} !
`
`TheData
`Compresmen
`
`Featuring fast, efficient data
`compression techniques in C
`
`Mark Nelson
`
`2 DISHS
`INCLUDED!
`
`M(Sfl"i
`
`Eli
`
`Page 15 of 45
`
`

`
`The Data
`Compresslon
`Book
`
`Featuring fast, efficient data
`compression techniques in C
`
`M u r k N e I s o n
`
`E'=:?£:-‘E.§ORL“&L LIBBELBY
`iii
`’<:3f2=.3’3.‘?C'3f:f;;C1 University
`
`50305-1499
`
`;E*‘c:3:=&:;‘s';:,
`
`M621" 3
`__
`cl:2
`=1
`n
`
`Ta
`
`]
`
`l
`
`
`
`Page 16 of 45
`
`

`
`MSIE
`
`M&T Books
`
`A Division of M&T Publishing, Inc.
`411 Bore] Avenue
`
`San Mateo, CA 94402
`
`2 n
`
`u-.I
`
`E
`
`© 1992 by M&T Publishing, Inc.
`
`Printed in the United States of America
`
`All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means,
`electronic or mechanical, including photocopying, recording, or by any information, storage and
`retrieval sytem, without prior written pemission from the Publisher. Contact the Publisher for
`information on foreign rights.
`
`Limits of Liability and Disclaimer of Warranty
`The Author and Publisher of this book have used their best efforts in preparing the book and the
`programs contained in it. These efforts include the development, research, and testing of the theories
`and programs to determine their effectiveness.
`
`The Author and Publisher make no warranty of any kind, expressed or implied, with regard to these
`programs or the documentation contained in this book. The Author and Publisher shall not be liable in
`any event for incidental or consequential damages in connection with, or arising out of, the furnishing,
`performance, or use of these programs.
`
`Library of Congress Cataloging-in-Publication Data
`
`Nelson, Mark, 1958 -
`The Data Compression Book/by Mark Nelson
`p. cm.
`Includes index.
`
`ISBN 1-55851-214-4: $29.95
`1. Data Compression (Computer Science)
`QA?6.9.D33N46
`199]
`00S.74’6--dc20
`
`ISBN 1-55351-216-0 (book/disk set): $39.95
`I. Title
`
`91-23080
`CIP
`
`Project Editor: Tova Fliegel
`Copy Editor: Shayne Bell
`Technical Reviewer: Robert Jung
`
`95
`
`94 9392
`
`4321
`
`Cover Design: Lauren Smith Design
`Layout: Marni Tapscott
`
`
`
`Page 17 of 45
`
`

`
`Contents
`
`WHY THIS BOOK IS FOR YOU ....................................................................1
`
`INTRODUCTION TO DATA COMPRESSION ........................................3
`
`The Audience
`
`Keeping
`
`The Structure
`
`'u:>E.n°4~.»'4=.
`
`10
`
`THE DATA-COMPRESSION LEXICON, WITH A H|STORY....13
`
`The Two
`
`.
`
`Data Compression = Modeling + Coding ............................................................ ..
`
`The DawnAge
`
`Coding
`
`An
`
`L..L...'_.,_..'_.
`
`oo-.Jum.|:L..a
`
`Statistical Modeling
`
`DictionzuySchemes
`
`Ziv and Lempel
`
`LossyCompression
`
`Programs to Know .............................................................................................. ..25
`
`THE DAWN AGE: MINIMUM FIEDUNDANCY CODING ............. ..29
`
`The Sham1on—FanoAlgorithm
`
`The Huffman
`
`
`
`Page 18 of 45
`
`

`
`A Reminder about Prototypes
`
`Into the Huffman Code
`
`Counting the
`
`Saving theCounts
`
`Building theTree
`
`Using the Tree
`
`The CompressionCode
`Putting It All
`
`A SIGNIFICANT IMPROVEMENT: ADAPTIVE HUFFMAN
`
`CODING .......................................................................................................................8'l
`
`Adaptive Coding82
`
`Updating the Huffman
`
`What Swapping Does
`
`The Algorithm.
`
`An
`
`The Escape Code .
`
`The Overflow Problem
`
`A Rescaling Bonus.
`
`The Code
`
`83
`
`37
`
`Initialization of theArray
`
`The Compress Main Program
`
`The Expand Main Program .............................................................................. ..99
`
`Encoding the Symbol.
`
`Decoding the
`
`The Code
`
`100
`
`108
`
`109
`
`Page 19 of 45
`
`
`
`

`
`HUFFMAN ONE BETTER:
`
`ARITHMETIC CODING ...................................................................................123
`Difficulties
`123
`Arithmetic Coding: A Step Forward .................................................................. .. 124
`Practical Matters
`128
`A Complication .............................................................................................. ..130
`Decoding ....................................................................................................... ..132
`Where’s the Beef’? .......................................................................................... .. 133
`The Code ........................................
`................................................................ .. 134
`The Compression
`134
`The Expansion Program ................................................................................. .. 136
`Initializing the Model ..................................................................................... .. 137
`Reading the
`141
`Initializing the Encoder .................................................................................. .. 141
`The Encoding Process .................................................................................... ..142
`Flushing the Encoder
`145
`The Decoding Process ................................................................................... .. 145
`Summary ........................................................................................................... .. 148
`Code .................................................................................................................. .. I48
`
`STATISTICAL MODELING ......................................................................... "16?
`I-Iigher—Order Modeling ..................................................................................... .. 167
`Finite Context Modeling ................................................................................... .. 168
`Adaptive Modeling ........................................................................................... .. 169
`A Simple Example ......................................................................................... ..17O
`Improvements ................................................................................................ .. 176
`Highest-Order Modeling ................................................................................... .. 1'76
`Updating the Model ....................................................................................... .. 178
`Escape Probabilities
`I79
`Scoreboarding ................................................................................................ .. 180
`Data Structures
`181
`The Finishing Touches: Tables 1 and2185
`
`Page 20 of 45
`
`

`
`Model Flushing .............................................................................................. .. 186
`Implementation ................................................................................................ 186
`Conclusions ......................................................................................................... 187
`Enhancement
`
`DICTIONARY-BASED COMPRESSION ...............................................219
`AnExample
`Static vs. Adaptive ...............................................................................................22O
`AdaptiveMethods
`A Representative Example ...............................................................................223
`Israeli Roots
`History .............................................................................................................226
`ARC: The Father of MS-DOS Dictionary Compression .....................................227
`Dictionary
`DangerAhead——Patents
`Conclusion .......................................................................................................... 23 1
`
`SLIDING WINDOW COMPRESSION .....................................................233
`The Algorithm .....................................................................................................233
`Problems with LZ77
`An EncodingProblem
`LZSSCompression
`Data Structures
`A Balancing Act ..............................................................................................244
`Greedy vs. Best Possible ..................................................................................246
`The Code ............................................................................................................247
`Constants and Macros ................................
`.................................................. ..247
`Global Variables ............................................................................................... 25 1
`The Compression Code .......................................................................................252
`Initialization. ....................................................................................................253
`The Main Loop ................................................................................................254
`
`Page 21 of 45
`
`

`
`The Exit Code ................................................................................................ ..256
`
`AddStrir1gO .................................................................................................... ..257
`
`DeleteString() ................................................................................................. ..26O
`
`Binary Tree SupportRoutines
`
`The Expansion Routine
`
`Improvements
`
`The Code ............................................................................