Difference coding adaptive context model
AssigneeRed Hal, Inc.
InventorJames P. Schneider
Life of this patent
Estimating the term…
Abstract
Techniques for improving encoding and decoding data are described herein. According to one embodiment, in response to a symbol retrieved from an input stream having a sequence of symbols, it is determined whether a current context can encode the retrieved symbol. A code representing an escape token is emitted to a code stream if the current context cannot encode the retrieved symbol. The process is escaped from the current context to a parent context of the current context if the current context is not a root context. The retrieved symbol is emitted to a literal stream if the current context is a root context, where the code stream and the literal stream are to be compressed and decoded by a decoder.
Claims22
A computer implemented method for encoding data, the method comprising:
- in response to a symbol retrieved from an input stream having a sequence of symbols, determining whether a current context can encode the retrieved symbol;
- emitting a code representing an escape token to a code stream if the current context cannot encode the retrieved symbol;
- escaping from the current context to a preceding context of the current context if the current context is not a root context;
- emitting the retrieved symbol to a literal stream if the current context is a root context, wherein the code stream and the literal stream are to be compressed and encoded by a compressor;
- emitting a code representing the retrieved symbol to the code stream if the current context can encode the retrieved symbol, wherein the code representing the retrieved symbol is generated based on an index associated with the retrieved symbol stored within the current context;
- and
- sorting at least a portion of the current context based on the emitted code and/or the emitted symbol.
(canceled)
A computer readable medium including instructions that, when executed by a processing system, cause the processing system to perform a method for encoding data, the method comprising:
- in response to a symbol retrieved from an input stream having a sequence of symbols, determining whether a current context can encode the retrieved symbol;
- emitting a code representing an escape token to a code stream if the current context cannot encode the retrieved symbol;
- escaping from the current context to a preceding context of the current context if the current context is not a root context;
- emitting the retrieved symbol to a literal stream if the current context is a root context, wherein the code stream and the literal stream are to be compressed and decoded by a decoder;
- emitting a code representing the retrieved symbol to the code stream if the current context can encode the retrieved symbol, wherein the code representing the retrieved symbol is generated based on an index associated with the retrieved symbol stored within the current context;
- and
- sorting at least a portion of the current context based on the emitted code and/or the emitted symbol.
(canceled)
A computer implemented method for decoding data, the method comprising:
- in response to a code stream having a plurality codes and a literal stream having a plurality of symbols encoded by an encoder, consuming a code from the code stream if the current context can code any symbol other than an escape token;
- generating an index value based on the consumed code, including performing a predetermined mathematical operation with the consumed code;
- retrieving a symbol from an entry corresponding to the index value stored in a table of the current context;
- emitting the symbol to an output stream;
- and
- sorting the table by moving the entry corresponding to the emitted symbol up front at index zero.
A computer readable medium including instructions that, when executed by a processing system, cause the processing system to perform a method for decoding data, the method comprising:
- in response to a code stream having a plurality codes and a literal stream having a plurality of symbols encoded by an encoder, consuming a code from the code stream if the current context can code any symbol other than an escape token;
- generating an index value based on the consumed code, including performing a predetermined mathematical operation with the consumed code;
- retrieving a symbol from an entry corresponding to the index value stored in a table of the current context;
- emitting the symbol to an output stream;
- and
- sorting the table by moving the entry corresponding to the emitted symbol up front at index zero.
Dependencies are inferred from the claim text.