System and method for compressing data information

Claim 2

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.

Claim 3

The method as recited in claim 1, wherein said selecting step further comprises the step of: comparing compression efficiencies of subsets of said dictionaries with respect to previously encoded phrases.

Claim 4

The method as recited in claim 1, further including the step of decompressing data previously compressed by said method for compressing data, wherein said previously compressed data is comprised of pointer data which refers to phrases included within said plurality of context dependent dictionaries formed during said method, and wherein each of said dictionaries is associated with a history of said previously compressed data, said method further comprising the steps of: decoding said compressed data by utilizing said pointer data to refer to corresponding phrases within said plurality of context dependent dictionaries; and combining said referred phrases to form said data.

Claim 5

The method, as recited in claim 1, further including the step of using a context of a phrase which is some number of immediately preceding characters.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 12

The system as recited in claim 7, wherein said plurality of context dependent dictionaries are subtrees of a single tree.

Claim 13

The system, as recited in claim 8, wherein said context dependent dictionaries are subtrees obtained by following a path from the root of said single tree consisting of branches corresponding to characters of a context.

Claim 14

The system as recited in claim 7, further including means for decompressing data previously compressed by said system for compressing data, wherein said previously compressed data is comprised of pointer data which refers to phrases included within said plurality of context dependent dictionaries formed by said system, and wherein each of said dictionaries is associated with a history of said previously compressed data, said system further comprising: means for decoding said compressed data by utilizing said pointer data to refer to corresponding phrases within said plurality of context dependent dictionaries; and means for combining said referred phrases to form said data.

Claim 15

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.

Claim 16

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.

Claim 19

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.

Claim 20

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.

Claim 21

The computer program product as recited in claim 13, wherein said selecting step further comprises the step of: comparing compression efficiencies of subsets of said dictionaries with respect to previously encoded phrases.

Claim 22

The computer program product as recited in claim 13, 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.

Claim 23

The computer program product as recited in claim 13, wherein said method further comprises the steps of: electing a phrase within said selected subset in order to compress said next phrase; computing a pointer corresponding to said elected 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.

Claim 24

The computer program product as recited in claim 13, wherein said method further includes the step of decompressing data previously compressed by said method, wherein said previously compressed data is comprised of pointer data which refers to phrases included within said plurality of context dependent dictionaries formed during said method, and wherein each of said dictionaries is associated with a history of said previously compressed data, said method further comprising the steps of: decoding said compressed data by utilizing said pointer data to refer to corresponding phrases within said plurality of context dependent dictionaries; and combining said referred phrases to form said data.