LZW Compression

Obtaining and Building the Source Code

The source code for the compressor, and the data analysis code, are available on GitHub here. Building the compressor requires g++; it has been tested with GCC 6.3, but should compile correctly on GCC 5. The analysis code requires Wolfram Mathematica, and has only been tested on Mathematica 11, though it should work with any reasonably recent version.

Once the source code has been acquired, move into the src directory and run make. This will create the bin directory alongside the src directory, and the lzw executable inside of it.

Invocation and Options

The lzw program should be invoked as follows:

• -c
  Compress mode; mutually exclusive with -x, with the last one to appear taking precedence. If neither is specified -c is taken to be the default.
• -i LOG_INTERVAL
  If compression statistics are being collected with the -s flag, sets the interval, in number of codes output, at which these statistics are stored. Defaults to 1.
• -m COMPRESSOR_MODE
  Sets the compression mode; see the modes list for allowed settings and what they do. This option must be set the same way when decompressing a file as it was when the file was compressed. Defaults to fs.
• -o OUTPUT_FILE
  Specify file name of output. By default, when compressing this is the input file name with the compressor mode being used appended to it as an extension. When extracting, if such an extension is present it removes it and uses this as the filename; if not, it defaults to the input filename with .extr_ and then the compressor mode as an extension.
• -s STATS_FILE
  Specify a file to write compression statistics. Has no effect if -x is set. If this option is not used, compression statistics are ignored.
• -w WIDTH
  Set the maximum code width for the compressor, in bits. WIDTH must be at least 9 and not more than 63. If unspecified, defaults to 12 bits. Must be set the same way when decompressing as when compressing.
• -x
  Extract mode; mutually exclusive with -c, with the last one to appear taking precedence.

Statistics File Format

The files generated with the -s flag above during compression are normal ASCII comma-separated values files. Each line corresponds to the state of the compressor after emitting a code. Note that in general all sizes are measured in bits. The columns represent, in order:

• Step: the number of codes that have been emitted so far. Note that this is not the position in the input file, and for modes with variable-width codes it doesn't directly correspond to position in the output file either.
• Last input size: the number of bits represented by the code that was just emitted. For instance, if the code represented a sequence of 4 characters, the last input size would be 32.
• Last code size: the number of bits in the last code that was emitted.
• Total input size: the total number of input bits that have been compressed so far. If the statistics log interval is set to 1 (see the -i option above), this should equal the sum of all of the last input size entries so far.
• Total output size: the total number of bits that have been output into the compressed file so far. Again, if the statistics log interval is 1, this should be the sum of all last code size entries so far.
• Dictionary size: the total number of entries in the dictionary so far, including all of the initial dictionary entires.
• Last dictionary entry size: the number of bits in the entry added to the dictionary when emitting the current code, or zero if no entry was added (for instance if the dictionary was full.