Binary Version of Lempel-Ziv Algorithm
Suppose 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:
The result looks like this:
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 non-empty 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:
The LZ-coded 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.