LIBRARY OF CONGRESS
`
`Office of Business Enterprises
`Duplication Services Section
`
`THIS IS TO CERTIFYthat the collections of the Library of Congress contain a bound
`volumeentitled A GUIDE TO DATA COMPRESSION METHODS,David Salomon,call
`number QA 76.9.D33 $28 2002, Copy 2. Theattached - Title Page, Copyright Page, Table of
`Contents Pages and Introduction Pages- are a true and complete representation from that work.
`
`IN WITNESS WHEREOF,the seal of the Library of Congressis affixed hereto on
`May 18, 2018.
`
`
`
`Deirdre Scott
`Business Enterprises Officer
`Office of Business Enterprises
`Library of Congress
`
`101 Independence Avenue, SE Washington, DC 20540-4917 Tel 202.707.5650 www.loc.gov; duplicationservices@loc.gov
`
`Comcast - Exhibit 1010, page 1
`
`Comcast - Exhibit 1010, page 1
`
`

`

`
`
`
`
`
`FT MEADE
`MRC
`
`-
`
`i
`A Guide to
`
`*
`
`DATA
`|
`° OMPRESSION
`eo? METHODS
`— David Salomon
`
`
`
`
`INCLUDED Ly
`
`CD-ROM
`
`
`
`Comcast - Exhibit 1010, page 2
`
`Comcast - Exhibit 1010, page 2
`
`

`

`A Guide to
`
`David Salomon
`
`With 92 Illustrations
`
`IncludesaCD-ROM | al j
`
`DATA
`COMPRESSION
`METHODS
`
`
`
`
`
`
`
`5)
`
`Springer
`
`
`
`Comcast - Exhibit 1010, page 3
`
`Comcast - Exhibit 1010, page 3
`
`

`

`
`
`
`
`David Salomon
`Department of Computer Science ;
`California State University, Northridge
`Northridge, CA 91330-8281
`USA
`david.salomon@csun.edu
`
`CoverIllustration: “Abstract: Yellow, Blue”, 1993, Patricia §. Brown/Superstock.
`
`Library of Congress Cataloging-in-Publication Data
`Salomon, D. (David), 1938-
`A guide to data compression methods/David Salomon.
`p.
`cm.
`Includes bibliographical references and index.
`ISBN 0-387-95260-8 (pbk.: alk. paper)
`1. Data compression (Computerscience).
`QA76.9D33 $28
`2001
`005.746—de21
`
`I. Title.
`
`2001-032844
`
`Printed on acid-free paper.
`
`© 2002 Springer-Verlag New York, Inc.
`All rights reserved. This work may not be translated or copied in wholeor in part without the written permission of
`the publisher (Springer-Verlag NewYork, Inc., 175 Fifth Avenue, New York, NY 10010, USA), exceptfor brief excerpts
`in connection with reviews or scholarly analysis, Use in connection with any form of information storage and
`retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now knownorhereafter
`developed is forbidden.
`The use of general descriptive names, trade names, trademarks,etc., in this publication, even if the former are not
`especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and
`Merchandise Marks Act, mayaccordingly be usedfreely by anyone.
`Production managed by Frank M¢Guckin; manu facturing supervised by Erica Bresler.
`Camera teady copypreparedfromthe author’s TeXfiles,
`Printed and bound by Hamilton Printing Co., Rensselaer, NY.
`Printed in the United States of Anverica.
`
`987654321
`
`ISBN 0-387-95260-8
`
`SPIN 10796580
`
`Springer Verlag NewYork Berlin Heidelberg
`A member af HertelsmannSpringerScience+Business Media GmbH
`
`
`
`Comcast - Exhibit 1010, page 4
`
`Comcast - Exhibit 1010, page 4
`
`

`

`Contents
`
`Preface —___
`
`Introduction
`
`Statistical Methods __
`
`
`
`=
`
`
`
`=
`=
`
`
`ix
`
`1
`
`29
`
`57
`
`
`
`1
`2
`3
`4
`5
`6
`7
`8
`
`Entropy
`Variable-Size Codes
`Decoding
`Huffman Coding
`Adaptive Huffman Coding
`Facsimile Compression
`Arithmetic Coding
`Adaptive Arithmetic Coding
`
`Dictionary Methods
`1
`L277 (Sliding Window)
`2
`LZSS
`3
`LZ78
`4
`LZW
`5
`Summary
`
`Image Compression —
`1
`Introduction
`2
`Iinage Types
`3
`Approaches to Lnage Compression
`4
`Intuitive Methods
`5
`Image Transforms
`6
`Progressive Inage Compression
`7
`JPEG
`8
`JPEG-LS
`
`9
`10
`12
`12
`22
`32
`40
`52
`
`59
`62
`66
`69
`80
`
`82
`87
`88
`103
`104
`135
`140
`159
`
`— 81
`
`Comcast - Exhibit 1010, page 5
`
`Comcast - Exhibit 1010, page 5
`
`

`

`Contents
`
`Wavelet Methods
`=
`
`l
`Averaging and Diflerencing
`167
`2
`The Haar Transform
`181
`3
`Subband ‘Transforms
`185
`4
`Filter Banks
`190
`5
`Deriving the Filter Coefficients
`197
`6
`The DWT
`199
`7
`Examples
`203
`8
`The Daubechies Wavelets
`207
`9
`SPIHT
`214
`Video Compression
`4
`
`227
`|
`Basic Principles
`2
`Suboptimal Search Methods
`233
`
`Audio Compression
`242
`1
`Sound
`245
`2
`Digital Audio
`247
`3
`The Human Auditory System
`200
`4
`Conventional Methods
`fy
`MPEG-1 Audio Layers
`253
`
`=
`Bibliography
`
`Glossary
`
`ae =
`
`2
`
`=e
`
`167
`
`227
`
`241
`
`269
`
`275
`
`Joining the Data Compression Community —.-—————S—SCS~éi HA
`
`-
`Appendix of Algorithms _
`
`-
`
`Index
`
`285
`
`287
`
`Thus a rigidly chronological series of Jetters would
`present a patchwork of subjects, each of which would
`be difficult to follow. The Table of Contents will show
`in what way | have attempted to avoid this result.
`
`-—Charles Darwin, Life and Letters of Charles Darwin
`
`
`
`Comcast - Exhibit 1010, page 6
`
`Comcast - Exhibit 1010, page 6
`
`

`

`Introduction
`
`letters, such as “E,” “T,” and “A” are common, whereas other letters, such as “Z” and
`
`Those who use compression software are familiar with terms such as “zip,” “implode,”
`“stuffit,” “diet,” and “squeeze.” These are names of programs or methods for compress-
`ing data, names chosen ta imply compression. However, such names do not reflect the
`true nature of data compression. Compressing data is not done by stuffing or squeezing
`it, but by removing any redundancy that’s present in the data. The concept of redun-
`dancyis centra] to data compression. Data with redundancy can be compressed. Data
`without any redundancy cannot be compressed, period.
`We all knowwhat information is. We intuitively understand it but we consider it a
`qualitative concept. Information seems to be one of those entities that. cannot be quan-
`tified and dealt with rigorously. Thereis, however, a mathematical field called informa-
`tion theory, where information is handled quantitatively. Among its other achievements,
`information theory shows how to precisely define redundancy. Here, we try to under-
`stand this concept intuitively by pointing out the redundancyin two common types of
`computer data and trying to understand why redundant data is used in thefirst place.
`The first type of data is text. Text is an important example of computer data.
`Many computer applications, such as word processing and software compilation, are
`nonnumeric; they deal with data whose elementary components are characters of text.
`The computer can store and process only binary information (zeros and ones), so each
`character of text must be assigned a binary code. Present-day computers usc the ASCII
`code (pronounced “ass-key,” short for “American Standard Code for Information In-
`terchange”), although more and more computers use the new Unicode. ASCII is a
`fixed-size code where each character is assigned an 8-bit code (the code itself occupies
`seven of the eight bits, and the eighth bit is parity, designed to increase the reliability
`of the code). A fixed-size codeis a natural choice because it makes it easy for soft-
`ware applications to handle characters of text. On the other hand, a fixed-size code is
`inherently redundant.
`In a file of randomtext, we expect cach character to occur approximately the same
`number of times. However, files used in practice are rarely random. They contain
`meaningful text, and we know from experience that in typical English text certain
`
`Comcast - Exhibit 1010, page 7
`
`Comcast - Exhibit 1010, page 7
`
`

`

`
`
`Introduction
`
`
`
`This explains why the ASCII code is redundant and also points the way
`“()," are rare.
`redundancy. ASCII is redundant because1b assigns to each character,
`to eliminating, the
`the same number (eight) of bits. Removing the redundancy can be
`common or rare,
`done by assigning variable-size codes to the characters, with short codes assigned to
`the commoncharacters and long codes assigned tio the rare ones. ‘This is precisely how
`Huffman coding (Section 1.4) works.
`Imaginetwotoxt files A and B with the same text, where A uses ASCII codes and
`B has variable-size codes. We expect B to be smaller than A and we say that A has
`been compressed to B. It is obvious that the amount of compression depends on the
`redundancy of the particular text and on the particular variable-size codes usedin file
`B. Text where certain characters are very common while others are very rare has much
`redundancy and will compress well if the variable-size codes are properly assigned. Tn
`sucha file, the codes of the commoncharacters should be very short, while those of the
`rare characters can be long. The long codes would not degrade the compression because
`they would rarely appear in B. Most of B would consist of the short codes. Random
`text, on the other hand, does not benefit from replacing ASCH with variable-size codes,
`because the compression achieved by the short codes is cancelled out by the long codes.
`This is a special case of a gencral rule that says that random data cannot. be compressed
`because it has no redundancy.
`The second type of common computer datais digital images. A digital image
`is a rectangular array of colored dots, called pixels. Each pixel is represented in the
`computer by its color code.
`(In the remainderof this section, the term “pixel” is used
`for the pixel’s color code.)
`In order to simplify the software applications that handle
`images, the pixels are all the samesize. ‘The size of a pixel depends on the numberof
`colors in the image, and this numberis normally a powerof 2. If there are 2” colors in
`an image, then each pixel is a k-bit number.
`There are two types of redundancyin adigital image. The first type is similar to
`redundancy in text. In any particular image, certain colors may dominate, while others
`may be infrequent. This redundancy can be removed byassigning variable-size codes to
`the pixels, as is done with text. The other type of redundancy is much more important
`and is the result of pixel correlation. As our eyes move along the image from pixel to
`pixel, we find that in most cases, adjacent pixels have similar colors. Imagine an image
`containing blue sky, white clouds, brown mountains, and ercen trees. As long as we
`look at a mountain, adjacent pixels tend to be similar; all or almost all of them are
`shades of brown. Similarly, adjacent pixels in the sky are shades of blue. It is only on
`the horizon, where mountain meets sky, that adjacent pixels may have very different
`colors. The individual pixels are therefore not completelyin lependent, and we say that
`neighboring pixels in an image tend to be correlated.
`‘This type of redundaney ean be
`exploited in many ways, as described in Chapter 3.
`Regardless of the method used to compress an image, the effectiveness of the com-
`pression depends on the amount of redundancy in the image. One extreme case is a
`uniform image. Such an image has maximum redundaney because adjacent pixels are
`identical. Obviously, such an image is not
`interesting and is rarely,
`if ever, used.
`in
`practice. However, it will compress very well under any image compression methoc L.
`The other extreme example is an image with uncorrelated pixels. All adjacent pixels
`
`
`
`Comcast - Exhibit 1010, page 8
`
`Comcast - Exhibit 1010, page 8
`
`

`

`Introduction
`
`B
`
`in such an image are very different, so the image redundancy is zero. Such an image
`will not compress, regardless of the compression method used. However, such an image
`tends to look like a randern jumble of dots and is therefore uninteresting. We rarely
`need to keep and manipulate such an image, so we rarely necd to compress it. Also, a
`truly random image features small or zero correlation between pixels.
`
`
`What with all the ARC war flames going around, and arguments about which program
`
`is best, I decided to do something aboutit and write my OWN.
`You've heard of crunching, jamming, syucezing, squashing, packing, crushing, implod-
`ing, Cte...
`Nowthere’s TRASHING.
`|TRASHcompressesafile to the smallest: size possible: 0 bytes! NOTILING compresses |
`|a file better than TRASH! Date/time stamp are not affected, and since thefile is zero
`bytes long, it doesn’t even take up any space on yourharddisk!
`In fact, it takes
`| And TRASHis FAST! Files can be TRASHED in microseconds!
`llonger to go through the various parameter screens than it does to trash thefile!
`This prerelease version of TRASHis yours to keep and evaluate. I would recommend
`backing up anyfiles you intend to TRASH first, though....
`The next version of TRASH will have graphics and take wildcards:
`TRASH C:\PAYROLL\*.*
`.and will even work on entire drives:
`TRASH D:
`...or be first on your block to trash your system ON PURPOSE!
`TRASH ALL
`We're even hoping to come up with a way to RECOVERTRASHedfiles!
`From FIDO News, 23 April 1990
`
`2”different files of sizes less than or equal n/2. However, the total numberof thesefiles
`
`Thefollowing simple argument illustrates the essence of the statement “Data com-
`pression is achieved by reducing or removing redundancyin the data.” The argument
`shows that most data files cannot be compressed, no matter what compression method
`is used. This seems strange at first because we compress our data files all the time.
`The point is that most files cannot be compressed because they are randomorclose
`to random and therefore have no redundancy. The (relatively) few files that can be
`compressed are the ones that we want to compress; they are the files we nse all the
`time. They have redundancy, are nonrandomand therefore useful and interesting.
`Given two different files A and B that are compressed tofiles C and D, respectively,
`it is clear that Cl and D must be different. If they were identical, there would be no
`way to decompress them and get back file A or file B.
`Suppose that a file of size n bits is given and we want to compressit efficiently.
`Anycompression method that can compress this file to, say, 10 bits would be welcome.
`Even compressing it to 11 bits or 12 bits would be great. We therefore (somewhat
`arbitrarily) assume that compressing suchafile 0 half its size or better is considered
`good compression. There are 2” n-bit files and they would have to be compressed into
`
`Comcast - Exhibit 1010, page 9
`
`Comcast - Exhibit 1010, page 9
`
`

`

` Introduction
`
`
`
`is
`
`N=142444----4 gn/2 = gi+n/2 —_1lx glin/2.
`
`so only Nof the 2” original files have a chance of being compressed efficiently. The
`problem is that N is much smaller than 2". Here are two examples of the ratio between
`these two numbers,
`For n = 100 (files with just 100 bits), the total numberoffiles is 219° and the
`number of files that can be compressedefficiently is 254. The ratio of these numbersis
`the ridiculously small fraction 2-49 = 1.78. 107).
`For n = 1000 (files with just 1000 bits, about 125 bytes), the total numberoffiles
`is 210°and the numberoffiles that can be compressed efficiently is 25°. The ratio of
`these numbers is the incredibly small fraction 274% = 9.82 107%.
`Most files of interest are at least some thousands of bytes long. For such files,
`the percentage of files that can be efficiently compressed is so small that it cannot be
`computed with floating-point numbers even on a supercomputer(the result is zero).
`It is therefore clear that. no compression method can hope to compressall files or
`even a significant percentage of them. In order to compress a data file, the compression
`algorithm has to examine the data, find redundancies in it, and try to remove them.
`Since the redundancies in data depend on the type of data (text, images, sound, etc.),
`any compression method has to be developedfor a specific type of data and works best
`on this type. There is no such thing as a universal, efficient data compressionalgorithm.
`Therest of this introduction covers important technical terms used in thefield of
`data compression.
`
`The compressor or encoder is the program that compresses the raw data in the
`»
`input file and creates an output file with compressed (low-redundancy) data. The de-
`compressor or decoder converts in the opposite direction. Notice that the term encoding
`is very general and has wide meaning, but since we discuss only data compression, we
`usc the name encoder to mean data compressor. The teri codec is sometimes used to
`describe both the encoder and decoder. Similarly, the term compandiny is short for
`“compressing/expanding.”
`
`<A nonadaptive compression methodis rigid and does not modify its operations,
`«
`its parameters, or its tables in response to the particular data being compressed. Such
`a method is best used to compress data that is all of a single type. Examples are
`the Group 3 and Group 4 methods for facsimile compression (Section 1.6). They are
`specifically designed for facsimile compression and would do a poor job compressing
`any other data. In contrast, an adaptive method examines the raw data and modifies
`its operations and/or its parameters accordingly. An example is the adaptive Huffman
`method of Section 1.5. Some compression methods use a two-pass algorithm, where the
`first pass reads the input file to collect statistics on the data to be compressed, and
`the second pass does the actual compressing using parameters or codes set by thefirst
`pass. Such a method may be called semiadaptive. A data compression method can
`also be locally adaptive, meaning it adapts itself to local conditions in the inputfile and
`varies this adaptation as it moves from area to area in the input. An example is the
`move-to-frout method [Salomon 2000].
`
`
`
`
`Comcast- Exhibit 1010, page 10
`
`Comcast - Exhibit 1010, page 10
`
`

`

`Introduction
`
`3
`
`a=Lossy/losstess compression: Certain compression methods are lossy. They achieve
`better compression by losing some information. When the compressed file is decom-
`pressed,
`the result is not identical to the original data. Such a method makes seuse
`when compressing images, movies, or sounds. Tf the loss of data is small, we may not
`be able totell the difference. In contrast, text files, especially files containing computer
`programs, may become worthless if even one bit gets modified. Such files should be
`compressed only by alossless compression method.
`[Two points should be mentioned
`regarding text files:
`(1) Ifa text file contains the source code of a program, many blank
`spaces can normally be eliminated, since they are disregarded by the compiler anyway.
`(2) When the output of a word processor is saved in a text file, the file may contain in-
`formation about the different fonts used in the text. Such information may be discarded
`if the user wants to save just the text..]
`a
`«Symmetric compressionis the case where the compressor and decompressor use the
`same basic algorithm but work in “opposite” directions. Such a metlod makes sense
`for general work, where the same numberof files are compressed as are decompressed.
`In an asymmetric compression method, either the compressor or the decompressor may
`have to work significantly harder. Such methods have their uses and are not necessarily
`bad. A compression method where the compressor executes a slow, complex algorithm
`and the decompressor is simple is a natural choice when files are compressed into an
`archive, where they will be decompressed and used very often, such as mp3 audio files
`on a CD. The opposite case is useful in environments wherefiles are updated all the
`time arid backups are made. There is only a small chance that a backup file will be
`uscd, so the decompressorisn’t used very often.
`
`The bit budget for the tables is 10%in this case.
`
`A valuc of 0.6 means that, the data occupies 60% of its original size after compression.
`Vahucs greater than 1 indicate an output file bigger than the input file (negative com-
`pression). The compression ratio can also be called bpb (bit per bit), since it equals
`the munberof bits in the compressed file needed, on average, to cornpress one bit. in the
`input file. In image compression, the similar term bpp stands for “bits per pixel.” In
`modern,efficient text compression methods, it makes sense to talk about bpe(bits per
`character), the numberof bits it takes, on average, to compress one character in the
`input file.
`Two more terms should be mentioned in connection with the compression ratio.
`The term bitrate (or “bit rate”) is a general term for bpb and bpc. Thus, the main
`goal of data compression is to represent any given data at low bil rates. The term bit
`budget refers to the functions of the individual bits in the compressedfile.
`Imagine a
`compressedfile where 90% of the bits are variable-size codes of certain symbols and the
`remaining 10%are used to encodecertain tables that are needed by the decompressor.
`
`Compression performance: Several quantities are commonly used to express the
`s
`performance of a compression method.
`1. The compression ratio is defined as
`
`
`size of the output file
`Compression ratio = —
`—
`—,
`size of the inputfile
`
`Comcast- Exhibit 1010, page 11
`
`Comcast - Exhibit 1010, page 11
`
`

`

`
`
`6
`
`Introduction
`
`
`
`2. The inverse of the compressionratio is the compression factor:
`
`size of the input file
`Pa
`Compression factor = —-————_————_.
`size of the outputfile
`
`In this case values greater than 1 indicate compression, and values less than 1 inuply
`expansion. This measure seems natural to many people, since the bigger the factor,
`the better the compression. This measureis distantly related to the sparsenessratio, a
`performance measure discussed in Section 4.1.2.
`3. The expression 100 x (1 — compressionratio) is also a reasonable measure of compres-
`sion performance. A value of 60 means that the output file occupies 40%ofits original
`size (or that the compression has resulted in savings of 60%).
`4. In image compression, the quantity bpp (bits per pixel) is commonly used. It equals
`the numberofbits neeced, on average, to compress onepixel of the image. This quantity
`should always be compared with the bpp before compression.
`
`The probability model. This concept is important in statistical data compression
`»
`methods. Sometimes, a compression algorithmconsists of two parts, a probability model
`and the compressoritself. Before the next data item (bit, byte, pixel, or anything clse)
`can be compressed, the model is invoked andis asked to estirnate the probability of the
`data item. The item and the probability are then sent to the cormpressor, which uses
`the estimated probability to compress the item. The better the probability, the better
`the item is compressed.
`Here is an example of a simple model for a black and white image. Each pixel in
`such an image is a single bit. Assume that after reading 1000 pixels and compressing
`them, pixel 1001 is read. What is the probability that this pixel is black? The model
`can simply count the numbers of black and white pixels read so far. If 350 of the 1000
`pixels were black, then the model can assign pixel 1001 a probability of 350/1000 = 0.35
`of being black. The probability and the pixel (which may, of course be either black or
`white) are then sent to the compressor. The point is that the decompressor can easily
`calculate the same probabilities before it. decodes the 1001st pixel.
`
`The term alphabet refers to the set of symbols in the data being compressed. An
`«
`alphabet inay consist of the two bits 0 and 1, of the 128 ASCII characters, of the 256
`possible 8-bit bytes, or of any other symbols.
`
`The performance of any compression methodis limited. No method can compress
`«
`all datafiles efficiently. Imagine applying asophisticated compression algorithm X to a
`data file A and obtaining a compressedfile of just 1 bit! Any method that can compress
`an entirefile to a single bit is excellent. Even if the compressedfile is 2 bits long, we still
`considerit to be highly compressed, and the sameis true for compressedfiles of 3, 4, 5
`and even more bits. It seems reasonable to define efficient compression as compressing
`a file to at most half its original size. Thus, we may be satisfied (even happy) if we
`discover a method X that compresses any data file A to a file B ofsize less than or
`equal half the size of A.
`The point is that different files A should be compressed to different files B, since
`otherwise decompressionis impossible. If method X compresses twofiles C’ and D to the
`
`
`
`
`
`Comcast- Exhibit 1010, page 12
`
`Comcast - Exhibit 1010, page 12
`
`

`

`Introduction
`
`same file E, then the X decompressor cannot decompress &. Once this is clear, it is easy
`to showthat methad X cannot compressall files efficiently. Iffile A is nbits long, then
`there are 2"differentfiles A. At the same time, the total numberofall files B whose size
`is less than or equal half the size of A is 2!+"/2 — 2. For n = 100, the numberof A files
`is N4 — 21° = 1.27-10°° but the numberof B files is only Ng = 2'+5° —2 = 2.25.10).
`The ratio Np /Nais the incredibly small fraction 1.77-107'°. Forlargervalues of n this
`ratio is much smaller.
`The conclusion is that method X can compress efficiently just a small fraction of
`all the files A. The great majority of files A cannot be compressedefficiently since they
`are randomor close to random.
`This sad conclusion, however, should not cause any reader to close the book with
`a sigh and turn to more promising pursuits. The interesting fact is that out of the 2”
`files A, the ones we actually want to compress are normally the ones that compress
`well. The ones that compress badly are normally random orclose to randomandare
`therefore uninteresting, unimportant, and not candidates for compression, transmission,
`or storage.
`
`The days just prior to marriage are like a
`snappy introduction to a tedious book,
`
`7
`
`Wilson Mizner
`
`Comcast- Exhibit 1010, page 13
`
`Comcast - Exhibit 1010, page 13
`
`