Data Compression Algorithms in Java

Be advised that these, and virtually all data compression techniques, have been granted patents.
This software uses only algorithms and coding techniques that are available to the public in the open literature. You are however, advised to make your own determination of legality, for your intended use.
See the comp.compression FAQ for more information, both on theory and application of data compression, and on patent coverage that you should be aware of. The patent information given below is taken from this FAQ.

Run Length Encoding (RLE)

RLE compression recognizes sequences of a repeating value, and replaces each sequence by a code, representing the value and the repeat count. The degree of compression depends on how much repetition is found in the data. RLE compression is effective with data having many and / or lengthy contiguous repeat values, such as graphics with areas of solid color, and sparsely filled binary data with runs of zero bytes.

The repeat count should allow for the expected amount of repetition, without wasting too much space allowing for unusually large counts, which can be handled when they do occur, by writing one or more additional codes. This version uses 4 bit counts for total 12 bit code width.

Note! Other versions of RLE may use other sizes of repeat count, and other coding conventions. They are not inter-operable with this algorithm.

Tsukiyama has two US patents on run length encoding: 4,586,027 and 4,872,009 granted in 1986 and 1989 respectively.

• 4,586,027 Method and system for data compression and restoration inventor Tsukimaya et al. assignee Hitachi filed 08/07/84, granted 04/29/86 patents run length encoding in its most primitive form: a length byte followed by the repeated byte.
• 4,872,009 Method and apparatus for data compression and restoration inventor Tsukimaya et al. assignee Hitachi filed 12/07/87, granted 10/03/89 This patent on run length encoding covers the invention of limiting the run length to 16 bytes, and thus the encoding of the length on 4 bits.

There is no need to construct an RLE object, the RLE.Compress () and RLE.Expand () methods are static.

Limpel, Ziv, Welch (LZW)

LZW compression recognizes sequences that have already appeared in the data, and replaces each later appearance by a unique code. The degree of compression depends on how much repetition is found in the data. LZW compression is effective with data having many and / or lengthy repeat sequences, such as text, and graphics with areas of solid color or patterns.

The sequence history should allow for the expected amount of repetition, without wasting too much space in each code on a history index. This version is fixed at 12 bit codes, which can refer to nearly a 2^^12 item sequence history, less some internal overhead. This size is considered good for short message blocks, and is simple to implement.

Note! Other versions of LZW may use other sizes of sequence history, and other coding conventions. They are not inter-operable with this algorithm.

The original papers:

• Terry Welch, A Technique for High-Performance Data Compression, IEEE Computer, June 1984
• J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, May 1977

• One form of the original LZ78 algorithm was patented (4,464,650) by its authors Lempel, Ziv, Cohn and Eastman. This patent is owned by Unisys.
• The LZW algorithm used in 'compress' is patented, both by IBM (4,814,746) and Unisys (4,558,302).

There is no need to construct an LZW object, the LZW.Compress () and LZW.Expand () methods are static.

Sources

• CodeInputUnpacker.java
• CodeOutputPacker.java
• LZW.java
• RLE.java

This software is provided free of charge with no support. Email me at morris_hirsch@brown.edu if you do have a problem, and I will try to help, but I cannot promise to.

Your comments, suggestions, bug reports, bug fixes, and enhancements, are welcome!

Was this Helpful?

Other java

Please also visit my home page.

Legalities

Redistribution and use in source and binary forms, with or without modification, for any purpose, are permitted, except as may be restricted by original copyright holders, provided that the following conditions are met:

• Redistributions of source code must retain the above copyright notice, all earlier copyright notices of others, this list of conditions and the following disclaimer.
• Redistributions in binary form must reproduce the above copyright notice, all earlier copyright notices of others, this list of conditions and the following disclaimer, in the documentation, and/or other materials provided with the distribution.

DISCLAIMER