book-index.html

The primary purpose of this book is to explain various data-compression techniques using the C progr

<DL>
<DD>code, 60-73
<DD>command lines for, 74
<DD>statistics for, 512-514
</DL>
<DD>HUFF-E, command lines for, 74
<DD>Huffman, D. A., 15, 16, 531
<DD>Huffman coding, 15, 54, 530-531. <I>See also</I> Adaptive Huffman coding
<DL>
<DD>advantages of arithmetic coding over, 122-123
<DD>arithmetic coding vs., 16-17
<DD>BITIO.C as illustration of, 35-43
<DD>difficulties with, 113-114
<DD>model of, 12-13
<DD>probability table in, 75-76
<DD>Shannon-Fano coding vs., 34-35
</DL>
<DD>Huffman table, 18
<DD>Huffman tree, 18
<DL>
<DD>algorithm for building, 31-35
<DD>building, 55-58
<DL>
<DD>counts, saving, 56-57
<DD>symbols, counting, 56
</DL>
<DD>using, 59-60
</DL>
<DD>Hutchinson, J., 458
</DL>
<P><FONT SIZE="+1"><B>I</B></FONT></P>
<DL>
<DD>IBM, 213-214, 297
<DD>IDCT (Inverse DCT), 329-330, 356-357
<DD>IFS. <I>See</I> Iterated Function Systems
<DD>information theory, 13-15, 27, 531
<DD>initialization
<DL>
<DD>adaptive Huffman coding, 89-90
<DD>arithmetic coding, 126-130
<DD>DCT.C, 348-349
<DD>Discrete Cosine Transform, 348-349
<DD>fractal image compression, 473-474
<DD>LZSS, 232-233
</DL>
<DD>initialize_model() routine (adaptive Huffman coding), 76
<DL>
<DD>InitializeTree(tree) (adaptive Huffman coding), 90
</DL>
<DD>InitTree() (LZSS), 233
<DD>input_counts() (HUFF.C), 57
<DD>integer registers, with arithmetic coding, 118-120
<DD>Intel, 298
<DD>International Standards Organization (ISO), 22, 326, 338, 531
<DD>International Telegraph and Telephone Consultative Committee (CCITT), 528
<DD>Internet, 25, 298
<DD>Inverse DCT (IDCT), 329-330, 356-357
<DD>ISO. <I>See</I> International Standards Organization
<DD>Iterated Function Systems (IFS), 459-467. <I>See also</I> Partitioned Iterated Function Systems
<DL>
<DD>image compression with, 461-467
<DD>mathematics of, 460-461
</DL>
<DD>Iterated Systems, Inc., 458, 509-510
</DL>
<P><FONT SIZE="+1"><B>J</B></FONT></P>
<DL>
<DD>Jacobs, Bill, 458, 510
<DD>Jacquin, Arnaud, 458
<DD>Joint Photographic Experts Group (JPEG), 22, 23, 326, 531. <I>See also</I> JPEG standard
<DD>JPEG. <I>See</I> Joint Photographic Experts Group
<DD>JPEG standard, 326-345
<DL>
<DD>coding, 340-345
<DD>compression algorithm, 327
<DD>Discrete Cosine Transform with, 327-340
<DD>drawbacks of, 457
</DL>
<DD>Jung, Robert, 209
</DL>
<P><FONT SIZE="+1"><B>K</B></FONT></P>
<DL>
<DD>Katz, Phil, 24
<DD>K&R C, 3-7
</DL>
<P><FONT SIZE="+1"><B>L</B></FONT></P>
<DL>
<DD>Lau, Raymond, 25
<DD>League for Programming Freedom, 213
<DD>Lehman, Bruce, 214
<DD>Lempel, Abraham, 21, 207, 532, 536
<DD>LHArc (compression program), 24, 209, 210, 531
<DD>library function calls, 3-4
<DD>LIFS (Local Iterated Function Systems), 459
<DD>Linear Predictive Coding (LPC), 319, 532
<DD>LISAW.GS, 464-471
<DD>List files command (CARMAN), 383
<DD>Local Iterated Function Systems (LIFS), 459
<DD>lossless compression, 11-12, 532
<DL>
<DD>of sound, 299-302
</DL>
<DD>lossy compression (generally), 11, 22-23, 532
<DL>
<DD>of sound, 302-303
</DL>
<DD>lossy graphics compression, 321-379
<DL>
<DD>and adaptive coding, 325-326
<DD>and differential modulation, 324-325
<DD>JPEG standard for, 326-345
<DL>
<DD>coding, 340-345
<DD>compression algorithm, 327
<DD>Discrete Cosine Transform with, 327-340
<DD>and quantization, 337-340
</DL>
<DD>results, analysis of, 375-379
<DD>sample program, 345-370
<DL>
<DD>code, 357-370
<DD>compression module, 346-348
<DD>expansion algorithm, 353-354
<DD>forward DCT routine, 349-350
<DD>initialization, 348-349
<DD>input DCT codes, 355-356
<DD>input format, 346
<DD>Inverse DCT, 356-357
<DD>OutputCode() routine, 351-352
<DD>ReadDCTData() routine, 354-355
<DD>WriteDCTData() routine, 350-351
</DL>
<DD>statistical and dictionary compression vs., 322-323
<DD>support programs, 370
<DL>
<DD>GS.C, 370-372
<DD>GSDIFF.C, 372-375
</DL>
</DL>
<DD>low-pass filters, 293-294
<DD>LPC (Linear Predictive Coding), 319, 532
<DD>LZ77, 21, 207-208, 209, 215-221, 532
<DL>
<DD>compression algorithm, 216-218
<DD>decompression algorithm, 218-219
<DD>as &#147;greedy&#148; algorithm, 226
<DD>inefficiency of, 221
<DD>limitations of, 255
<DD>LZ78 vs., 256-257
<DD>LZSS vs., 262
<DD>problems with, 220-221
<DD>and QIC-122, 205
<DD>text window in, 215-216
</DL>
<DD>LZ78, 21-22, 207-208, 209, 255-262, 287-288, 532. <I>See also</I> LZW
<DL>
<DD>functioning of, 257-260
<DD>implementation of, 260-262
<DD>LZ77 vs., 256-257
<DD>tree in, 260-261
</DL>
<DD>LZSS, 221-253, 532
<DL>
<DD>and ARJ 2.10, 300-301
<DD>balanced trees, maintaining, 225-226
<DD>binary tree in, 230-231
<DD>and CARMAN, 383, 405
<DD>code for, 244-253
<DD>compression program, 227, 231-242
<DL>
<DD>AddString() routine, 235-238
<DD>DeleteString() routine (LZSS), 238-240
<DD>exit code, 235
<DD>initialization, 232-233
<DD>main loop, 233-235
<DD>support routines, binary tree, 240-242
</DL>
<DD>constants in, 228
<DD>data structures in, 222-225
<DD>expansion program, 242-244
<DL>
<DD>potential improvements to, 243-244
</DL>
<DD>global variables in, 229-231
<DD>as &#147;greedy&#148; algorithm, 226-226
<DD>LZ77 vs., 262
<DD>macros in, 228-229
<DD>text window in, 221-222
</DL>
<DD>LZSS.C, 244-253
<DL>
<DD>statistics for, 512-514
</DL>
<DD>LZW, 208, 210, 212, 213, 262-288, 532
<DL>
<DD>code, 273-278
<DD>compression program, 262-263, 270-271
<DD>decompression program, 264-270, 271-273
<DL>
<DD>and LZW implementation, 267
<DD>tree maintenance and navigation, 268-270
<DD>undefined code, problem with, 266-267
</DL>
<DD>LZW15V.C as improvement of, 279
<DD>patent concerns, 287-288
</DL>
<DD>LZW12.C
<DL>
<DD>code, 273-278
<DD>decompression routine in, 271-273
<DD>hashing function of, 268-269
<DD>&#147;special&#148; nodes in, 270
<DD>statistics for, 512-514
</DL>
<DD>LZW15V.C
<DL>
<DD>code, 280-287
<DD>as improvement over LZW, 279
<DD>statistics for, 512-514
</DL>
</DL>
<P><FONT SIZE="+1"><B>M</B></FONT></P>
<DL>
<DD>Macintosh, compression programs for, 24-25
<DD>macros, in LZSS, 228-229
<DD>MAIN-C.C, 45-50
<DD>MAIN-E.C, 50-53
<DD>MAIN.H, 45-46
<DD>Mandelbrot, Benoit, 457, 458
<DD>Mandelbrot set, 457-458
<DD>MassageMSDOSFileName() routine (CARMAN), 394-396
<DD>measurement of compression, 7
<DD>Microcom Corp., 210
<DD>Microsoft, 211, 213
<DD>MNP-5, 210
<DD>modeling, 17-18. <I>See also</I> adaptive modeling; highest-order modeling; Statistical modeling
<DL>
<DD>coding vs., 12-13
<DD>finite-context, 154
<DD>higher-order, 153-154
</DL>
<DD>models, 532
<DL>
<DD>static, 535
</DL>
<DD>modulation, differentiation, 324-325
<DD>Moving Pictures Experts Group (MPEG), 22, 23, 532-533
<DD>MPEG-II, 22
<DD>MPEG (Moving Pictures Experts Group), 22, 23, 532-533
<DD>MS-DOS, CARMAN with, 392-396
</DL>
<P><FONT SIZE="+1"><B>N</B></FONT></P>
<DL>
<DD>NeXT Computer, 298
<DD>nodes[] array, 88-89
<DD>Nyquist, Harry, 295
<DD>Nyquist Rate, 295, 533
</DL>
<P><FONT SIZE="+1"><B>O</B></FONT></P>
<DL>
<DD>on-line services, 298
<DD>OpenArchiveFiles() command, 397-398
<DD>Oracle, 213
<DD>order-0 modeling, 154
<DD>order(-1) table (ARITH-N.C), 169
<DD>order(-2) table (ARITH-N.C), 169
<DD>order (of model), 533
<DD>OutputBits routine (adaptive Huffman coding), 93
<DD>OutputCode() routine (DCT.C), 351-353
<DD>output_counts() routine
<DL>
<DD>arithmetic coding, 129
<DD>HUFF.C, 57
</DL>
<DD>overflow, in adaptive Huffman coding, 84-87
</DL>
<P><FONT SIZE="+1"><B>P</B></FONT></P>
<DL>
<DD>p x 64, 533-534
<DD>P6 processor (Intel), 298
<DD>parameters, in function declarations, 43-44
<DD>ParseArguments() routine (CARMAN), 390-391
<DD>Partitioned Iterated Function Systems (PIFS), 458, 467, 509
<DL>
<DD>compression with, 463-467
</DL>
<DD>patent concerns
<DL>
<DD>dictionary-based compression programs, 212-214
<DD>fractal image compression, 509-510
<DD>LZW algorithm, 287-288
</DL>
<DD>PC Backup, 210
<DD>PC-based sound, 297-299
<DD>PCX format, 322
<DD>phrases, 533
<DD>PIFS. <I>See</I> Partitioned Iterated Function Systems
<DD>PKWare, 24
<DD>PKZ204.EXE, 24
<DD>PKZIP, 24, 209, 210, 381, 533
<DD>PNG format, 209, 213
<DD>Print files command (CARMAN), 383
<DD>probability table (Huffman coding), 75-76
<DD>prototypes, 43-44
<DD>pseudocode, 2
</DL>
<P><FONT SIZE="+1"><B>Q</B></FONT></P>
<DL>
<DD>QIC-122, 205-207, 211, 212
<DD>quality factor, 345
<DD>quantization, 337-340
<DL>
<DD>errors in, 295
<DD>matrix for, 338-340
</DL>
</DL>
<P><FONT SIZE="+1"><B>R</B></FONT></P>
<DL>
<DD>Radford, Neal, 161
<DD>ReadDCTData() routine, 354-355
<DD>redundancy, 13
<DD>redundant information, 13
<DD>refine_image() function (FRAC.C), 477
<DD>Replace files command (CARMAN), 383
<DD>rescaling, in adaptive Huffman coding, 87-88
<DD>resolution independence, 469-471
<DD>RLE (Run-Length Encoding), 341, 534
<DD>root mean square (RMS), 346, 466-467, 507
<DD>Run-Length Encoding (RLE), 341, 534
</DL>
<P><FONT SIZE="+1"><B>S</B></FONT></P>
<DL>
<DD>SAMPLE-3.RAW., 301
<DD>sampling, 291-292
<DL>
<DD>of variables, 294-297
</DL>
<DD>scale_counts() routine (arithmetic coding), 128-129
<DD>scoreboarding, with highest-order modeling, 165-166
<DD>second pass, 155
<DD>Shannon, Claude, 13, 14, 27, 202, 534
<DD>Shannon-Fano coding, 15, 27-29, 534
<DL>
<DD>Huffman coding vs., 34-35
</DL>
<DD>Shannon-Fano tree, 28-29, 32
<DL>
<DD>algorithm for building, 29-31
</DL>
<DD>shareware, 298-299, 534-535
<DD>SILENCE.C, 305-309
<DD>silence compression, 303-310
<DL>
<DD>code, 305-309
<DD>effectiveness of, 310
</DL>
<DD>16-bit machines, 4
<DD>sliding window compression. <I>See</I> LZ77; LZSS
<DD>Sloan, Alan, 458-459
<DD>Sound Blaster, 298
<DD>speech compression, 289-319
<DL>
<DD>ADPCM algorithm, 319
<DD>companding, 310-318
<DL>
<DD>code, 314-318
<DD>codecs with, 312-314
<DD>linear conversion with, 311-312
<DD>and minimum resolution, 310-311
</DL>
<DD>and digital audio, 289-299
<DL>
<DD>low-pass filters, 293-294
<DD>PC-based sound, 297-299
<DD>range of hearing, 290
<DD>replay, 293
<DD>sampling, 291-292
<DD>variables, sampling, 294-297
<DD>waveforms, 290-291
</DL>
<DD>G.721 algorithm, 318-319
<DD>Linear Predictive Coding, 319
<DD>lossless compression, 299-302
<DD>lossy compression, 302-303
<DD>silence compression, 303-310
<DL>
<DD>code, 305-309
<DD>effectiveness of, 310
</DL>
</DL>
<DD>SQ program, 23, 535
<DD>Stac Electronics, 204-205, 210, 211, 213
<DD>Stacker, 211
<DD>static dictionary-based compression, 20, 202-203
<DD>static models, 535
<DD>statistical modeling, 14, 18-20, 153-200
<DL>
<DD>and adaptive compression, 155-162
<DL>
<DD>escape code as fallback, using, 159-161
<DD>example (ARITH-1.C.), 156-158
<DD>improvements to, 161-162
</DL>
<DD>and finite-context modeling, 154
<DD>with graphics files, 322
<DD>and higher-order modeling, 153-154
<DD>highest-order modeling (ARITH-N.C), 162-170
<DL>
<DD>code, 172-200
<DD>data structures, redesign of, 166-169
<DD>escape probabilities, 164-165
<DD>flush code for, 170
<DD>implementation, memory and, 170
<DD>order(-1) table for, 169
<DD>order(-2) table for, 169-170
<DD>scoreboarding with, 165-166
<DD>updating ARITH-1.C for, 163-164
</DL>
<DD>potential improvements to, 171
</DL>
<DD>statistics, compression, 7, 511-515
<DD>__STDC__ macro, 74
<DD>StuffIt (compression program), 25
<DD>swap_nodes() routine (adaptive Huffman coding), 82
<DD>swapping, in adaptive Huffman coding, 81, 96-97
<DD>switching equipment, 290
<DD>symbols, 535
</DL>
<P><FONT SIZE="+1"><B>T</B></FONT></P>
<DL>
<DD>TAR, 24, 535-536
<DD>Test files command (CARMAN), 383
<DD>test program (CHURN.C), 517-526
<DD>text windows
<DL>
<DD>LZ77, 215-216
<DD>LZSS, 221-222
</DL>
<DD>32-bit machines, 4
<DD>time domain representation, 328
<DD>tokens, 536
<DD>traverse_image() function (FRAC.C), 477
<DD>tree(s). <I>See also</I> Huffman tree
<DL>
<DD>in LZ78, 260-261
<DD>in LZSS, 225-226, 230-231
<DD>in LZW, 268-270
<DD>updating, in adaptive Huffman coding, 77-80, 95-100
</DL>
</DL>
<P><FONT SIZE="+1"><B>U</B></FONT></P>
<DL>
<DD>underflow, 120-121, 132-133
<DD>Unisys, 209, 212, 287
<DD>UNIX, 4
<DL>
<DD>CARMAN with, 392-393
<DD>compression programs in, 23
<DD>dictionary-based compression with, 208, 209
</DL>
<DD>update exclusion, 163-164
<DD>UpdateModel() routine (adaptive Huffman coding), 76, 77, 91-92
<DD>U.S. Patent Office, 213-214
<DD>utility programs, 298-299
</DL>
<P><FONT SIZE="+1"><B>V</B></FONT></P>
<DL>
<DD>V.4bis, 212
<DD>V.42bis, 211
<DD>variables, sampling, 294-297
<DD>vector quantization, 457, 463-467
<DD>VGA display, 321, 346
<DD>VOC-HDR.EXE, 298
</DL>
<P><FONT SIZE="+1"><B>W</B></FONT></P>
<DL>
<DD>waveforms, 290-291
<DD>Welch, Terry, 208, 209, 212, 287, 536
<DD>WinZIP, 24
<DD>Witten, Ian H., 161
<DD>World-Wide Web, 298
<DD>WriteDCTData() routine, 350-351
<DD>WriteFileHeader() routine (CARMAN), 388
</DL>
<P><FONT SIZE="+1"><B>X</B></FONT></P>
<DL>
<DD>Xtract files command (CARMAN), 383
</DL>
<P><FONT SIZE="+1"><B>Y</B></FONT></P>
<DL>
<DD>Yoshizaki, Haruyasu, 24, 209
</DL>
<P><FONT SIZE="+1"><B>Z</B></FONT></P>
<DL>
<DD>zig-zag sequence, 341-343
<DD>ZIP files, 24, 25
<DD>ZipIt V1.2, 25
<DD>Ziv, Jacob, 21, 207, 532, 536
</DL>
<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="ewtoc.html">Table of Contents</A></TD>
</TR>
</TABLE>
</CENTER>


</TD>
</TR>
</TABLE>

</BODY>
</HTML>