Data compression is the process of translating a given amount of data into a smaller representation, so that it may be stored on a medium using a minimum of storage space. Two broad categories of data compression are lossless compression and lossy compression. Numerous compression types or algorithms may be used to achieve either lossless or lossy compression. Lossless compression involves condensing data in a manner such that it can later be extracted to its full form Without any loss of information. Using a lossless compression method, the original data can be reconstructed exactly from the compressed data. Such methods are generally used to compress “discrete” data, such as text, computer-generated data, and various types of image and video information. Lossy compression generally involves a greater degree of compression, however, data compressed in this manner cannot be recovered in its exact original form.
A compression ratio is a general measure of the extent to which a set of data is compressed. For example, an uncompressed image made up of a 100×100 array of pixels may require one byte per pixel, or 10,000 bytes total, for storage. If a compressed version requires only 2,500 bytes, the compression ratio is said to be 4:1, as the original data set was four times larger than the compressed version. Achieving a high compression ratio is often desired when storage space is limited, since more data can be stored on a medium with a given amount of storage space.
Many different types of data compression methods exist. A common compression approach involves replacing a frequently repeated string of multiple characters with a shorter representation, possibly a single character. Upon expansion of lossless-compressed data, the short representation can be replaced with the original representation without any loss of data. A specific example of such a “dictionary-based” compression algorithm is the Huffman Code, in which frequently used elements are assigned a shorter representation than are less frequently used elements. This method is often used for compression of text documents. Run Length Encoding (RLE) consists of the process of searching for repeated runs of a single symbol in an input stream, and replacing them by a single instance of the symbol and a numerical run count (e.g., replacing a string of data reading “AAAAA” with the shorter representation “5A”). Numerous other compression types exist for compressing data.
With the increase in popularity of portable electronic devices, including digital cameras, MP3 players, personal digital assistants (PDAs), and other handheld computers (collectively called “hosts”), the need to store and compress data efficiently has risen. In addition to common onboard memories, such devices often record data to or read data from removable storage media, including miniature storage cards or drives. Generally, a pre-set compression level is chosen prior to taking pictures with a digital camera. When a picture is taken, an image is generally stored on a removable storage device, such as a flash memory card or other insertable media. In general, most digital cameras store images in a Joint Photographic Experts Group (JPEG or JPG) file format, a lossy storage method. If a high-quality image is desired, a higher fidelity level can be selected so that less compression takes place, and little information is discarded when writing the data to the memory. Alternatively, if a lower quality image will suffice, choosing a lower fidelity level, or resolution, will enact a higher compression level, allowing the data to be compressed to a smaller file upon saving. By discarding data concerning image patterns to which the eye is insensitive, there is little visually perceptible loss of information, and the image can be reconstructed substantially as it was recorded in the camera. Image compression is traditionally handled by the host device, the camera in this case, as the image is being written to memory.
Modern PDAs and handheld computers are often used to store or transport many types of data created by personal computer applications, including spreadsheets, word processing files, images, drafting files and music files. Since handheld computers and other portable host devices tend to have limited storage space when compared to a personal computer, it is often beneficial to compress data on the host device, to allow for surplus storage space. Given that many file types often contain information that should not be quantitatively altered or discarded, lossless compression is frequently desired in these cases. Generally, data files may be pre-compressed on a personal computer, then written to the removable storage media. However, it would be beneficial to be able to compress data on the removable storage media itself, whether during saving, on command of the user, or automatically, as the storage media senses it is low on storage space.
Typically, compression activities are managed by the host device. A conventional removable storage device used with multiple host devices would require each host operating system (OS) to understand the compression or encryption type performed by another OS or host software package, limiting the range of host types the compressed data can be read by. Further, compression abilities and settings may vary from host to host, making it even more difficult to one host device to expand data compressed by another host. In addition, when the host device is in charge of compression, managing compression activities may overburden a multitasking host, consuming computing power at critical times, often during a period of peak usage. To address the aforementioned issues, it is therefore desired to manage data compression activities within the removable storage device itself, instead of within the host device.