Mastering Algorithms With C - Kyle Loudon [156]
This chapter focuses on lossless compression, for which there are two general approaches: minimum redundancy coding and dictionary-based methods. Minimum redundancy coding achieves compression by encoding symbols that occur with great frequency using fewer bits than for those that occur less often. Dictionary-based methods encode data in terms of tokens that take the place of redundant phrases. Example 14.1 is a header for the compression methods presented in this chapter.
This chapter covers:
Bit operations
An important part of data compression because most methods require operating on data one bit at a time to some degree. C provides a number of bitwise operators that can be used to implement an extended class of bit operations.
Huffman coding
One of the oldest and most elegant forms of compression based on minimum redundancy coding. Fundamental to Huffman coding is the construction of a Huffman tree, which is used both to encode and decode the data. Huffman coding is not the most effective form of compression, but it runs fast both when compressing and uncompressing data.
LZ77 (Lempel-Ziv-1977)
One of the fundamental methods of dictionary-based compression. LZ77 uses a sliding window and a look-ahead buffer to encode symbols in terms of phrases encountered earlier in the data. LZ77 generally results in better compression ratios than Huffman coding, but with longer compression times. However, uncompressing data is generally very fast.
Some applications of lossless data compression are:
Software distribution
The process of delivering software on various media. When distributing software on physical media, such as compact discs or magnetic tapes and diskettes, reducing the amount of storage required can produce considerable cost savings in mass distributions.
Archiving
Collecting groups of files into organized libraries. Typically, archives contain large amounts of data. Thus, after creating archives, frequently we compress them.
Mobile computing
An area of computing in which devices typically have limited amounts of memory and secondary storage. Mobile computing generally refers to computing with small, portable devices such as advanced programmable calculators, electronic organizers, and other personal computing devices.
Optimized networking (illustrated in this chapter)
Compression is used especially when sending large amounts of data across wide-area networks. Bandwidth at certain points along wide-area networks is often limited. Although compressing and uncompressing data does require time, in many network applications the cost is well justified.
Embedded applications
An area of computing similar to mobile computing in that devices typically have somewhat limited amounts of memory and secondary storage. Examples of embedded applications are lab instruments, avionics (aircraft electronics), VCRs, home stereos, and other pieces of equipment built around microcontrollers.
Database systems
Typically, large systems that can be optimized by reducing their size to some extent. Databases may be compressed at the record or file level.
Online manuals
Manuals that are accessed directly on a computer. Online manuals are typically of considerable size, but many sections are not accessed on a regular basis. Therefore, it is common to store them in a compressed form and uncompress sections only as they are needed.
Example 14.1. Header for Data Compression
/*****************************************************************************
* *
* ------------------------------ compress.h ------------------------------ *
* *
*****************************************************************************/
#ifndef COMPRESS_H
#define