Data compression

Claim 1

A method for compressing a token comprising the steps of propagating a coded representation of the token when the token does not appear in a primary list, propagating a coded representation of the position of the token in the primary list when the token appears in the primary list but the position of the token in the primary list does not appear in a secondary list, and propagating a coded representation of the position in the secondary list corresponding to the token when the token appears in the primary list and the position of the token in the primary list appears in the secondary list.

Claim 2

A method for compressing a token comprising the steps of propagating a coded representation of the token when the token does not appear in a primary list, propagating a coded representation of the position of the token in the primary list when the token appears in the primary list but the position of the token in the primary list does not appear in a secondary list, and propagating a coded representation of the position in the secondary list corresponding to the token when the token appears in the primary list and the position of the token in the primary list appears in the secondary list.

Claim 3

A method for compressing a token comprising the steps of propagating a coded representation of the token when the token does not appear in a primary list, propagating a coded representation of the position of the token in the primary list when the token appears in the primary list but the position of the token in the primary list does not appear in a secondary list, propagating a coded representation of the position in the secondary list corresponding to the token when the token appears in the primary list, the position of the token in the primary list appears in the secondary list, and the position in the secondary list does not appear in a tertiary list, and propagating a coded representation of the position in the tertiary list corresponding to the token when the token appears in the primary list, the position of the token in the primary list appears in the secondary list, and the position of the secondary list appears in the tertiary list.

Claim 4

A method for compressing a token comprising the steps of propagating a coded representation of the token when the token does not appear in a primary list, propagating a coded representation of the position of the token in the primary list when the token appears in the primary list but the position of the token in the primary list does not appear in a secondary list, propagating a coded representation of the position in the secondary list corresponding to the token when the token appears in the primary list, the position of the token in the primary list appears in the secondary list, and the position in the secondary list does not appear in a tertiary list, and propagating a coded representation of the position in the tertiary list corresponding to the token when the token appears in the primary list, the position of the token in the primary list appears in the secondary list, and the position of the secondary list appears in the tertiary list.

Claim 5

A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of tokens, (b) sequentially determining if each token from said stream of tokens is stored in a primary memory and, if so, invoking step (f); otherwise, continuing with step (c), (c) transmitting identification data indicative of a new token and transmitting a representation for said new token as a corresponding outgoing data segment in the compacted data stream, (d) inserting said new token at the top of the primary memory, (e) returning to step (b), (f) determining the primary memory address of the said each token in the primary memory, (g) determining if the primary memory address is in a secondary memory and, if so, invoking step (1); otherwise, continuing with step (h), (the) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the primary memory address, (i) inserting the primary memory address at the top of the secondary memory, (j) moving said each token to the top of the primary memory, (k) returning to step (b), (l) determining the secondary memory location of the primary memory address, (m) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the secondary memory location, (n) moving said each token to the top of the primary memory, and (o) moving the secondary memory location to the top of the secondary memory, and (p) returning to step (b).

Claim 6

A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of tokens, (b) sequentially determining if each token from said stream of tokens is stored in a primary memory and, if so, invoking step (f); otherwise, continuing with step (c), (c) transmitting identification data indicative of a new token and transmitting a representation for said new token as a corresponding outgoing data segment in the compacted data stream, (d) inserting said new token at the top of the primary memory, (e) returning to step (b), (f) determining the primary memory address of the said each token in the primary memory, (g) determining if the primary memory address is in a secondary memory and, if so, invoking step (1); otherwise, continuing with step (h), (the) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the primary memory address, (i) inserting the primary memory address at the top of the secondary memory, (j) moving said each token to the top of the primary memory, (k) returning to step (b), (l) determining the secondary memory location of the primary memory address, (m) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the secondary memory location, (n) moving said each token to the top of the primary memory, and (o) moving the secondary memory location to the top of the secondary memory, and (p) returning to step (b).

Claim 14

A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of tokens, (b) sequentially determining if each token from said stream of tokens is stored in a primary memory and, if so, invoking step (f); otherwise, continuing with step (c), (c) transmitting identification data indicative of a new token and transmitting a representation for said new token as a corresponding outgoing data segment in the compacted data stream, (d) inserting said new token at the top of the primary memory, (e) returning to step (b), (f) determining the primary memory address of the said each token in the primary memory, (g) determining if the primary memory address is in a secondary memory and, if so, invoking step (1); otherwise, continuing with step (h), (h) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the primary memory address, (i) inserting the primary memory address at the top of the secondary memory, (j) moving said each token to the top of the primary memory, (k) returning to step (b), (l) determining the secondary memory location of the primary memory address, (m) moving said each token to the top of the primary memory, (n) determining if the secondary memory location is in a tertiary memory and, if so, invoking step (s); otherwise, continuing with step (o), (o) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the secondary memory location, (p) inserting the secondary memory location at the top of the tertiary memory, (q) moving the secondary memory location to the top of the secondary memory, and (r) returning to step (b), (s) determining the tertiary memory position of the secondary memory location, (t) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the tertiary memory position, (u) moving the tertiary memory position to the top of the tertiary memory, (v) moving the secondary memory location to the top of the secondary memory, and (w) returning to step (b).

Claim 15

A method for compressing an incoming data stream to produce an outgoing compacted data stream, the method comprising the steps of (a) parsing the incoming data stream to generate a corresponding stream of tokens, (b) sequentially determining if each token from said stream of tokens is stored in a primary memory and, if so, invoking step (f); otherwise, continuing with step (c), (c) transmitting identification data indicative of a new token and transmitting a representation for said new token as a corresponding outgoing data segment in the compacted data stream, (d) inserting said new token at the top of the primary memory, (e) returning to step (b), (f) determining the primary memory address of the said each token in the primary memory, (g) determining if the primary memory address is in a secondary memory and, if so, invoking step (1); otherwise, continuing with step (h), (h) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the primary memory address, (i) inserting the primary memory address at the top of the secondary memory, (j) moving said each token to the top of the primary memory, (k) returning to step (b), (l) determining the secondary memory location of the primary memory address, (m) moving said each token to the top of the primary memory, (n) determining if the secondary memory location is in a tertiary memory and, if so, invoking step (s); otherwise, continuing with step (o), (o) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the secondary memory location, (p) inserting the secondary memory location at the top of the tertiary memory, (q) moving the secondary memory location to the top of the secondary memory, and (r) returning to step (b), (s) determining the tertiary memory position of the secondary memory location, (t) transmitting as an outgoing segment in the compacted data stream a data block corresponding to the tertiary memory position, (u) moving the tertiary memory position to the top of the tertiary memory, (v) moving the secondary memory location to the top of the secondary memory, and (w) returning to step (b).

Claim 27

A method utilizing a primary memory and a secondary memory for decompressing a compacted data stream into an output data stream, the compacted data stream formed by compressing an incoming data stream partitioned into a sequence of tokens using a move-to-front data structure providing a recency rank of the most recent appearance of a repeated token in the primary memory or the address in the primary memory of the repeated token as an entry in the secondary memory, the compacted data stream having a delimiter to distinguish each new token from each repeated token, a token indicator to provide the length of each token and, in the case of a repeated token, the memory from which the recency rank serves as the encoded representation of the repeated token, the primary memory storing at each address the most recent appearance of any repeated token and the secondary memory storing at a memory location the address in the primary memory of the most recent appearance of the repeated token, the method comprising the steps of (a) sequentially parsing the compacted data stream to determine whether the next incoming one of the tokens is a new token or a repeated token, and if said next token is a new token, proceeding to step (e); otherwise, continuing with step (b), (b) if the token indicator indicates that the recency rank in the compacted data stream is in the primary memory, continuing with step (c); otherwise, proceeding to step (d), (c) determining the storage address of the repeated token in the primary memory based on the recency rank information contained in the compacted data stream, delivering the repeated token to the output data stream, and proceeding to step (f), (d) determining the storage location of the repeated token in the secondary memory based on the recency rank information contained in the compacted data stream, determining the storage address of the repeated token in the primary memory based on the secondary memory location of the repeated token, delivering the repeated token to the output data stream, and proceeding to step (f), (e) determining the length of the new token from the token length indicator, and supplying data from the compacted data stream to the output data stream based on the length of the new token, (f) updating the memories using the move-to-front data structure, and returning to step (a).

Claim 28

A method utilizing a primary memory and a secondary memory for decompressing a compacted data stream into an output data stream, the compacted data stream formed by compressing an incoming data stream partitioned into a sequence of tokens using a move-to-front data structure providing a recency rank of the most recent appearance of a repeated token in the primary memory or the address in the primary memory of the repeated token as an entry in the secondary memory, the compacted data stream having a delimiter to distinguish each new token from each repeated token, a token indicator to provide the length of each token and, in the case of a repeated token, the memory from which the recency rank serves as the encoded representation of the repeated token, the primary memory storing at each address the most recent appearance of any repeated token and the secondary memory storing at a memory location the address in the primary memory of the most recent appearance of the repeated token, the method comprising the steps of (a) sequentially parsing the compacted data stream to determine whether the next incoming one of the tokens is a new token or a repeated token, and if said next token is a new token, proceeding to step (e); otherwise, continuing with step (b), (b) if the token indicator indicates that the recency rank in the compacted data stream is in the primary memory, continuing with step (c); otherwise, proceeding to step (d), (c) determining the storage address of the repeated token in the primary memory based on the recency rank information contained in the compacted data stream, delivering the repeated token to the output data stream, and proceeding to step (f), (d) determining the storage location of the repeated token in the secondary memory based on the recency rank information contained in the compacted data stream, determining the storage address of the repeated token in the primary memory based on the secondary memory location of the repeated token, delivering the repeated token to the output data stream, and proceeding to step (f), (e) determining the length of the new token from the token length indicator, and supplying data from the compacted data stream to the output data stream based on the length of the new token, (f) updating the memories using the move-to-front data structure, and returning to step (a).