Properly handling the end of the bitstream first requires modeling what is really happening. To this end, I'll focus on arithmetic coding. (For more information, see "Arithmetic Coding and Statistical Modeling," by Mark R. Nelson, DDJ, February 1991.)

The first level of abstraction is to see if the compressor is looking at a series of symbols followed by an EOF signal from the operating system. For example, a typical compressor reads in the symbols S0:S1:....:Sn:EOF one at a time and passes them to a probability-modeling module. In turn, the probability of the character asks the arithmetic encoder to update the output with new high and low ranges. The encoder's output for each symbol is either the null symbol N, or a series of symbols being defined as 0, 1, or C (for carry).

The null symbol represents the case where the arithmetic encoder causes less than 1 bit of information to be output. This is what leads to most of the problems with arithmetic compression since it means that more than one symbol can map to a single bit. But the trick is just to use the token N. When you decompress, you won't have a problem because you will be working on the set of N, C, 0, and 1.

Now assume you want to change the symbols 01001CC:CC:N:N:011CC:EOF into 1s and 0s. The Ns aren't a problem since they are dropped. The carry bits are output using the conventional rules for arithmetic coding. If a series of Cs is followed by a 1, slide the 1 in front of the Cs and change the Cs to 0s. If a 0 or EOF follows, slide a 0 in front of the Cs and change the Cs to 1s. (This is because you are really mapping to a structure that has an infinite number of zeros at the end.) For this example, you now have 0100101:11:::11101:10000... EOF is replaced by an infinite number of zeroes. (The ":" characters are the original symbol separators.)

Now comes the tricky part. Notice that the last symbol is :01CC:. If the last symbol contains a 1 or at least two Cs, then the compression at this point is fully reversible. The problem occurs when the last symbol is of the form :C:, :000:, or :N: — you've dropped the EOF marker so if this symbol is of this form, the decompressor would not know that the hidden :N: or :000: (where "000" can be any number of zeroes) was last.

Working around this problem requires another fix. Although there are several ways to tackle this problem, I use the following for my arithmetic compressor: The trick is that when you line up the symbols in order so that the least-likely symbols are closer to the high end of the probability model and the most-likely symbols are closer to the low end, then all the symbols have at least one 1 bit in their expansion, except maybe the most likely symbol.

There are two special cases where the output of the arithmetic coder may not have any 1 bits. In the first case, the most-probable symbol has a 0.5 or less chance of occurring. The second case, where the most-probable symbol may have no bits in its arithmetic encoding, is when the first symbol occurs with probability of greater than 0.5 so that the :N: field has a high possibility of being the last token in the first mapping. But notice the next most-probable symbol is always 1 or longer and will contain a 1 in the final mapping to the infinite file.

So here's the next trick. If the file being compressed ends with the most-probable symbol (and thereby might lack a 1 bit), you add the next most-probable symbol to the file. If the symbol ends with a tail of the most-probable symbol followed by a series of second most probable, you add one more second most-probable symbol to the end of string of the second most-probable symbols. This mapping is reversible so far and the last symbol mapped has at least one 1-bit set. Again, in the example 0100101:11:::11101:10000... EOF is replaced by an infinite number.

Since, in this case, the file didn't end in :C:, :N:, or :000:, you don't need an extra string at the end. Notice that the ":" characters designated as symbol separators are not really needed because on decompression, you are only looking at 0s and 1s. The example now becomes 0100101:11:::11101:10000... This is still not a byte-aligned stream, but it is a unique string for any arithmetic compression that knows the next trick.

If you divide the output stream into bytes with the separator character, it then looks like: 01001011:11110110:00000000:00000000:... Because of the concept of the infinite file, you drop all the trailing :00000000: fields; they are implicitly there. This gives a new stream value of :01001011:11110110:. Finally, this is the compressed output.

Now that the output is properly aligned, my decoder properly restores the input file as long as it assumes the file ends with an infinite string of zeros.

For just a bit more savings, there is one trick left to apply. Notice that with this algorithm you have compressed the file to binary, where any combination is possible, except having a 1 in the last bit position. Think of the file as containing three types of symbols — the all 0 symbol ("0"), the leading-1 symbol (":10000000:"), and all the rest (type R). If a files ends with the tail of an all-0 symbol (":00000000:") followed by one or more leading-1 symbol (":10000000:"), then you can chop off the last symbol.

Conclusion

So is getting a standard arithmetic coder to conform to the definition of bijective worth the effort? I think so, for two compelling reasons:

• First, you know from the Counting Theorem that it isn't possible to compress all files. In fact, most files expand under compression due to gaps created when certain files are not used as possible compressions. Bijective compression makes full use of the file space.
• Second, programs such as PGP compress and then encrypt. This not only saves space but helps to increase the Unicity distance. Using most conventional compression algorithms, a brute-force attacker can quickly discard most keys by only testing a few bytes of the input file. The nonbijective file quickly shows itself to be invalid. With a bijective algorithm, attackers can always decompress the input stream, valid or not.

To illustrate how you can implement the concepts presented here, I'm providing electronically (see "Resource Center," page 5) a pair of command-line programs — a compressor (aribd.cpp) and decompressor (unaribd.cpp). Instructions on their use is included in the source-code comments.

DDJ

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.