Decompression algorithm

Let's consider decompressing the example given in the previous section. In the previous section we considered compressing the character or byte stream 'ABAB'. Assume we chose to encode the second and only reappearances or recurrences of both 'A' and 'B', even though it does not save space. Given this assumption, from the previous section, 'ABAB' is compressed as:

A 00000000 00000001 01000000 B 00000000 00000001 10000000

This is our compressed input stream, and we will form a decompressed output stream. The 'A' is immediately read and placed into the decompressed output stream. Then $00000000_{2}$ follows. This is the escape sequence, so we know an encoding follows, which encodes the reappearances or recurrences of 'A'. If another escape sequence, $00000000_{2}$, followed the first escape sequence, it would really specify a natural $00000000_{2}$ in the compressed input stream, and we would not assume that an encoding followed. Next is $00000001_{2}$. This is the length of the encoding measured in bytes, namely 1 (one). Then the encoding itself follows, $01000000_{2}$, an encoding of length one (1), measured in bytes. This encoding indicates that not the next character, but the character after the next charter is a reappearance or recurrence of 'A'. So this is our decompressed output stream so far: 'A?A?', where question marks (?'s) represent currently missing or unknown information.

Next we read 'B' from the compressed input stream. This is immediately placed in the decompressed output stream, so our decompressed output stream is currently 'ABA?'. Then the escape sequence, $00000000_{2}$, follows, so we know an encoding follows, an encoding which encodes reappearances or recurrences of 'B'. Next is $00000001_{2}$. This is the length of the encoding measured in bytes, namely 1 (one). Then the encoding itself follows, $10000000_{2}$, an encoding of length one (1), measured in bytes. This encoding indicates the next question mark (?) in our decompressed output stream is a reappearance or recurrence of 'B'. So that completes our decompressed output stream: 'ABAB'. We have decompressed the compressed version of 'ABAB'.

A more complicated decompression example is given in Appendix B.

Figures 3 and 4 specify the decompression algorithm. Figure 4 is the algorithm for DECOMPRESS, which uses the helper function DECODE. Figure 3 is the algorithm for DECODE. Parameters passed to either function, either DECOMPRESS or DECODE, which are preceded by var are passed by reference, so their values can change in the algorithms.

Figure 3: DECODE

Figure 4: DECOMPRESS

Hosted by www.Geocities.ws