US 6,724,330 B1Granted

Prefix table implemented data compression method and apparatus utilizing string code reassignment

AssigneeUnisys Corporation

InventorAlbert B. Cooper

Life of this patent

Estimating the term…

Loading patent…

Abstract

The disclosed compressor utilizes a plurality of prefix tables corresponding to respective prefix codes. A string is stored by storing the code associated with the string in a prefix table corresponding to the code of the string prefix at a prefix table location corresponding to the extension character of the string. The input data character stream is searched by comparing the input stream to the stored strings to determine the longest match therewith. The code associated with the longest match is outputted so as to provide the output stream of compressed codes. The stored strings are updated by inserting an extended string into the prefix tables, the extended string comprising the longest match extended by the next data character in the input stream following the longest match, the extended string being stored in the prefix table corresponding to the code of the longest match, a code being assigned to the extended string. A code is deleted from a prefix table for reassignment to an extended string to be inserted when further codes are unavailable for assignment. A code is selected for reassignment when the prefix table corresponding to the code is empty or has not been established.

Claims40

Dependent claims

A data compression method for compressing an input stream of data characters into an output stream of compressed codes, said data characters being from an alphabet of data characters, comprising

providing a plurality of prefix tables corresponding to a respective plurality of codes,
storing, in said prefix tables, strings of data characters encountered in said input stream, said stored strings having respective codes assigned thereto, a string comprising a prefix string of at least one of said characters followed by an extension character, a prefix string having a code associated therewith,
a particular string being stored in said prefix tables by storing the code associated with said particular string in the prefix table corresponding to the code of the prefix string of said particular string at a prefix table location corresponding to the extension character of said particular string,
searching said input stream by comparing said input stream to said stored strings to determine the longest match therewith,
outputting the code associated with said longest match so as to provide said output stream of compressed codes,
inserting an extended string into said prefix tables, said extended string comprising said longest match extended by the next data character in said input stream following said longest match, said extended string being stored in the prefix table corresponding to said code of said longest match,
assigning a code to said extended string, and
deleting a code from a prefix table for reassignment to an extended string to be inserted when further codes are unavailable for assignment.

5 more elements

Data compression apparatus for compressing an input stream of data characters into an output stream of compressed codes, said data characters being from an alphabet of data characters, comprising

a plurality of prefix tables corresponding to a respective plurality of codes,
said prefix tables storing strings of data characters encountered in said input stream, said stored strings having respective codes assigned thereto, a string comprising a prefix string of at least one of said characters followed by an extension character, a prefix string having a code associated therewith,
a particular string being stored in said prefix tables by storing the code associated with said particular string in the prefix table corresponding to the code of the prefix string of said particular string at a prefix table location corresponding to the extension character of said particular string,
means for searching said input stream by comparing said input stream to said stored strings to determine the longest match therewith,
means for outputting the code associated with said longest match so as to provide said output stream of compressed codes,
means for inserting an extended string into said prefix tables, said extended string comprising said longest match extended by the next data character in said input stream following said longest match, said extended string being stored in the prefix table corresponding to said code of said longest match,
means for assigning a code to said extended string, and
means for deleting a code from a prefix table for reassignment to an extended string to be inserted when further codes are unavailable for assignment.

5 more elements

Dependencies are inferred from the claim text.