Binary Version of LempelZiv AlgorithmSuppose we have a binary stream we want to compress. We start with parsing exactly the same way we did with characters. Let's take as an example the following binary string: 001101100011010101001001001101000001010010110010110 The result looks like this: ,0,01,1,011,00,0110,10,101,001,0010, 01101,000,00101,001011,0010110 Since we will code the prefix number using the same 0s and 1s that also occur as characters in the string, we need our coded strings to have a fixed length. Since we have 16 strings (counting also the first "empty" string, which will be given the position number "zero"), we will need 4 bits for numbering them in binary. As we number the strings, starting from the first nonempty string (see Position Number in the table below), we also check what the Prefix is (that is the piece of the string before its last digit) and the Position Number of that prefix (which, by construction, is a string that was encountered before). The coded string is then constructed by taking the Position Number of the Prefix, and following that by the last bit of the string that we are considering. This table shows the proper method for encoding. Fill in the empty slots:
Practice
The LZcoded version of the chain in this example is
then formed by writing all the coded strings (from the last column in the
table) in one long chain. 001101100011010101001001001101000001010010110010110 becomes:
0000000011000010010100010010000011001111
