Modified Huffman coding is used in
fax machines to encode black-on-white images (
bitmap
In computing, a bitmap (also called raster) graphic is an image formed from rows of different colored pixels. A GIF is an example of a graphics image file that uses a bitmap.
As a noun, the term "bitmap" is very often used to refer to a partic ...
s). It combines the variable-length codes of
Huffman coding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by ...
with the coding of repetitive data in
run-length encoding
Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (consecutive occurrences of the same data value) are stored as a single occurrence of that data value and a count of its consecutive occurrences, rather th ...
.
The basic Huffman coding provides a way to compress files with much repeating data, like a file containing text, where the alphabet letters are the repeating objects. However, a single scan line contains only two kinds of elements white pixels and black pixels which can be represented directly as 0 and 1. This "alphabet" of only two
symbols
A symbol is a mark, sign, or word that indicates, signifies, or is understood as representing an idea, object, or relationship. Symbols allow people to go beyond what is known or seen by creating linkages between otherwise different concep ...
is too small to apply the
Huffman coding
In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by ...
directly. But if we first use run-length encoding, we can have more objects to encode. Here is an example taken from the article on
run-length encoding
Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (consecutive occurrences of the same data value) are stored as a single occurrence of that data value and a count of its consecutive occurrences, rather th ...
:
A hypothetical scan line, with B representing a black pixel and W representing white, might read as follows:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
With a run-length encoding (RLE) data compression algorithm applied to the above hypothetical scan line, it can be rendered as follows:
12W1B12W3B24W1B14W
Here we see that we have several different numbers in addition to the two items "white" and "black." These numbers provide plenty of additional items to use, so the Huffman coding can be directly applied to the sequence above to reduce the size even more.
See also
*
Fax compression
External links
*
Lossless compression algorithms
Data compression
{{computer-stub