System and method for compressing data information
AssigneeInternational Business Machines Corporation
InventorsPeter A. Franaszek, Joy A. Thomas, Pantelis G. Tsoucas
Life of this patent
Estimating the term…
Abstract
A system and method for compressing or predicting data information received within an input stream, wherein contextual information is utilized in the selection of dictionaries for encoding or predicting of a next phrase within the information stream. The present invention utilizes contextual information in conjunction with dictionary-based Lempel-Ziv compression processes.
Claims17
In a data processing system, a method for compressing data, said method comprising the steps of:
- maintaining a plurality of dictionaries of encoded phrases for use in compression wherein each of said dictionaries correspond to a particular context;
- selecting a subset from said plurality of dictionaries such that for each context encountered there is a corresponding dictionary in said subset;
- and
- using said corresponding dictionary within said subset to encode, the next phrase.
In a data processing system, a method for compressing data, said method comprising the steps of:
- developing and storing dictionaries of encoded phrases as a function of histories associated with each of said encoded phrases;
- selecting a subset of said dictionaries that is determined to statistically provide the highest potential compression;
- using a particular history within said subset to encode said next phrase, wherein said particular history corresponds to a history of said next phrase;
- and wherein said selecting step further comprises the steps of:
- (a) computing an average depth of each of said dictionaries;
- (b) computing a longest length of a phrase pointer possible within each of said dictionaries;
- and
- (c) computing a ratio of (b) to (a) to derive a potential compression ratio for each of said dictionaries.
In a data processing system, a method for compressing data, said method comprising the steps of:
- developing and storing dictionaries of encoded phrases as a function of histories associated with each of said encoded phrases;
- selecting a subset of said dictionaries that is determined to statistically provide the highest potential compression;
- using a particular history within said subset to encode said next phrase, wherein said particular history corresponds to a history of said next phrase;
- selecting a phrase from a dictionary within said selected subset in order to compress said next phrase;
- computing a pointer corresponding to said selected phrase;
- adding tokens to roots of each tree including said particular history;
- and
- moving tokens in all trees as a function of a symbol(s) contained within said next phrase.
A system for compressing data, said system comprising:
- means for developing and storing a plurality of context dependent dictionaries of encoded phrases as a function of histories associated with each of said encoded phrases;
- and
- means for selecting a subset of said dictionaries corresponding to a tree that is determined to statistically provide the highest potential compression;
- and
- means for using a particular history within said subset to encode said next phrase, wherein said particular history corresponds to a history of said next phrase.
In a data processing system, a method for predicting a next sequence of unknown symbol(s) within a stream of symbols observed over a period of time, said method comprising the steps of:
- developing dictionaries of previously observed symbols, wherein more than one of said dictionaries is context dependent;
- determining which of a plurality of subsets of said dictionaries would statistically provide a most accurate compressor of said next sequence of symbol(s);
- selecting a dictionary within said determined subset for calculating a probability distribution of the next sequence of symbol(s);
- and
- using said probability distribution for predicting the next symbol.
A system for predicting a next sequence of unknown symbol(s) within a stream of symbols observed over a period of time, said system comprising:
- means for developing dictionaries of previously observed symbols, wherein more than one of said dictionaries is context dependent;
- means for determining which of a plurality of subsets of said dictionaries would statistically provide a most accurate compressor of said next sequence of symbol(s);
- means for selecting a dictionary within said determined subset for calculating a probability distribution of the next sequence of symbol(s);
- and
- means for using said probability distribution for predicting the next symbol.
A computer program product comprising:
- a program storage device readable by a computer system tangibly embodying a program of instructions executable by said computer system to perform a method for compressing data, said method comprising the steps of:
- developing and storing a plurality of context dependent dictionaries of encoded phrases as a function of histories associated with each of said encoded phrases;
- selecting a subset of said dictionaries corresponding to a tree that is determined to statistically provide the highest potential compression;
- and
- using a particular history within said subset to encode said next phrase wherein said particular history corresponds to a history of said next phrase.
Dependencies are inferred from the claim text.