US 6,188,333 B1Granted

LZW data compression apparatus and method using look-ahead mathematical run processing

AssigneeUnisys Corporation

InventorAlbert B. Cooper

Life of this patent

Estimating the term…

Loading patent…

Abstract

The disclosed data compressor compresses an input stream of data characters using LZW data compression. When the occurrence of a run of input data characters is detected, the run is processed by successively looking ahead into the input to determine the contiguous numerically increasing segments that exist in the run and by utilizing codes from the compressor code counter to correspond to the contiguous numerically increasing run segments. Alternatively, the detected run is processed by determining the length of the run and mathematically determining, from the length of the run, the respective codes from the code counter corresponding to the contiguous numerically increasing segments that exist in the run. Specifically, an iterative mathematical algorithm or a quadratic equation algorithm are utilized to process the run.

Claims58

Dependent claims

A data compression method for compressing an input stream of data characters into an output stream of compressed codes, said method including an LZW data compression process, said LZW data compression process including storing strings of data characters, assigning respectie codes to said stored strings from a code counter and incrementing said code counter for each said stored string, said method comprising:

detecting when a run of data characters is occurring in said input stream by detecting when a predetermined number of adjacent data characters of said input stream are the same with respect to each other,
said detected run including contiguous numerically increasing segments, a segment having one data character less than the next following adjacent segment of said detected run,
determining consecutive codes from said code counter to correspond, respectively, to said contiguous segments of said detected run,
using said LZW data compression process to compress said input stream when a run is not detected occurring therein by comparing said input stream to said stored strings to determine longest matches therewith and providing said codes assigned thereto, thereby providing LZW compressed codes, and
outputting the data character of said detected run and said consecutive codes corresponding to said contiguous segments and outputting said LZW compressed codes so as to provide said output stream.

2 more elements

Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes, said apparatus including an LZW data compressor, said LZW data compressor including a dictionary for storing strings of data characters, a code counter for assigning respective codes to said stored strings and means for incrementing said code counter for each said stored string, said apparatus comprising:

means for detecting when a run of data characters is occurring in said input stream by detecting when a predetermined number of adjacent data characters of said input stream are the same with respect to each other,
said detected run including contiguous numerically increasing segments, a segment having one data character less than the next following adjacent segment of said detected run,
means for determining consecutive codes from said code counter to correspond, respectively, to said contiguous segments of said detected run,
said LZW data compressor operative to compress said input stream when a run is not detected occurring therein by comparing said input stream to said stored strings to determine longest matches therewith and providing said codes assigned thereto, thereby providing LZW compressed codes, and
means for outputting the data character of said detected run and said consecutive codes corresponding to said contiguous segments and for outputting said LZW compressed codes so as to provide said output stream.

2 more elements

Dependencies are inferred from the claim text.