Adaptive entropy coding compression output formats

FIELD

0001The invention relates to data compression. More specifically, the invention relates to improving the compression ratio achieved by members of the known class of adaptive entropy coding compression algorithms.

BACKGROUND

0002Data compression can be used to write all of human knowledge on a pin (in theory, at least). Here's how: take a pin (<figref idrefs="DRAWINGS">FIG. 3</figref>, <b>300</b>) and divide it into twenty-six segments (one segment for each letter, from A to Z). Make a mark <b>310</b> along the pin, in the segment corresponding to the first letter of all of human knowledge. In this example, the first letter is ‘T’. It doesn't matter where in the ‘T’ segment the mark is made; anywhere between the end of ‘S’ and the beginning of ‘U’ is fine. The pin now contains the first letter of all of human knowledge.

0003Next, divide the ‘T’ segment into twenty-six segments (expanded view <b>320</b>, showing the subdivided ‘T’ segment, the preceding ‘S’ segment <b>330</b> and following ‘U’ segment <b>340</b>). Adjust the mark <b>350</b> so that it falls somewhere in the segment corresponding to the second letter of all human knowledge. In this example, the second letter is ‘H’.

0004Repeat this process to encode the rest of the letters of all human knowledge. Doubly-expanded view <b>360</b> shows the ‘H’ segment, between ‘G’ <b>370</b> and ‘I’ <b>380</b>, where the mark <b>390</b> has been adjusted to indicate that the third letter of all human knowledge is ‘E’. Note that this procedure only works to write on the side of the pin. Writing on the head of a pin requires a different technique.

0005To recover the message written on the pin, one simply measures—very, very carefully—how far along the pin the mark is located, and works through the same segment-dividing method to extract the message. Since so much information (all human knowledge!) is encoded in a single mark on the pin, the information has been compressed.

0006In the real world, of course, the physical properties of matter prevent this method from being used to write more than a few letters on any reasonably-sized pin. However, there is no mathematical reason why ideal intervals cannot be subdivided indefinitely, and the foregoing method is a simplified form of entropy encoding compression, a viable and effective way of compressing data.

0007Traditional entropy encoding compression algorithms (such as Huffman coding, adaptive Huffman coding or arithmetic coding) depend on having a statistical model of the input stream they are compressing. The more accurately the model represents the actual statistical properties of symbols in the input stream, the better the algorithm is able to compress the stream. Loosely speaking, the model is used to make a prediction about what input symbol will come next in the input stream. For example, if the input stream is English-language text, the model would assign a higher probability to the letter ‘e’ than to the letter ‘Q’ (usually). This corresponds physically to making the ‘e’ segment of the pin longer than the ‘Q’ segment.

0008The probability model can be static (i.e., unchanging for the duration of a compression process) or adaptive (i.e., evolving as the compressor processes the input data stream). The probability model can also take into account one or more of the most recently encountered input symbols to take advantage of local correlations. For example, in English text, encountering a letter ‘Q’ or ‘q’ in the input stream makes it more likely that the next character will be ‘u’.

0009An adaptive model typically works by matching the current input symbol against its prediction context, and if it finds the current input symbol in its context, generating a code representing the particular probability range that the input symbol represents. For example, if the current input symbol is ‘e’ and the model predicts that the probability of ‘e’ is in the range 0.13 to 0.47, then the compressor would generate an output code representing that probability range. This corresponds, in the physical example, to adjusting the mark to fall within the noted range of the current sub-segment of the pin. Once the symbol is encoded, the compressor updates the probability model. This “code and update” cycle is repeated until there are no more input symbols to compress.

0010When the compressor encounters a new symbol for which its model has no prediction, it must do something else. What it does is encode a special “escape” symbol to signal to the decompressor that the next symbol is a literal value. This escape-and-literal output has two problems: first, since the literal value will be sent as a whole number of bits (e.g., eight bits), compression algorithms that can send symbols in fractional bits will lose a small amount of compression efficiency when a fractional bit is rounded up to a whole-bit boundary. Second, the fact that these escaped literal symbols failed to match the current probability model provides some residual information that could be used to compress the literals themselves. This compression opportunity is wasted if the literals are distributed throughout the compressed data stream wherever the unmatched symbols happen to appear. Compression algorithm modifications to plug these efficiency “leaks” may be able to improve overall compression performance.

BRIEF DESCRIPTION OF DRAWINGS

0011Embodiments of the invention are illustrated by way of example and not by way of limitation in the figures of the accompanying drawings, in which like references indicate similar elements. It should be noted that references to “an” or “one” embodiment in this disclosure are not necessarily to the same embodiment, and such references mean “at least one.”

0012<figref idrefs="DRAWINGS">FIG. 1</figref> shows an overview of an adaptive coding compression process according to an embodiment of the invention.

0013<figref idrefs="DRAWINGS">FIG. 2</figref> shows the three-symbol contexts that are created as an embodiment of the invention compresses the string “abracadabra”.

0014<figref idrefs="DRAWINGS">FIG. 3</figref> shows a physical model suggesting how an entropy coding compressor works.

0015<figref idrefs="DRAWINGS">FIGS. 4A-4C</figref> show some possible formats for the compressed data.

0016<figref idrefs="DRAWINGS">FIG. 5</figref> is a flow chart outlining decompression according to an embodiment of the invention.

0017<figref idrefs="DRAWINGS">FIGS. 6A and 6B</figref> show two more compressed-data formats.

0018<figref idrefs="DRAWINGS">FIG. 7</figref> shows a computer system that can implement an embodiment of the invention.

0019<figref idrefs="DRAWINGS">FIG. 8</figref> shows how an embodiment of the invention can be encoded and transmitted across a data distribution network.

DETAILED DESCRIPTION

0020Embodiments of the invention attempt to improve adaptive entropy coding compression methods by collecting literal symbols that would normally be emitted in the compressed data stream and collecting those symbols into a group. The literals are then compressed together and and placed at a discernible location in the compressed stream (e.g., at the beginning or end of the stream, or before or after blocks of data processed together). Properties of the literals are examined in detail to show what literal compression approach is likely to be most effective. Finally, techniques for building compression and decompression contexts are described, and modifications to obtain further performance improvements are explained.

0021The following descriptions will make basic assumptions about the implementation environment within which an embodiment of the invention operates. Since data compression is often performed by a computer, typical binary-computer operations will be assumed. Data subjected to compression will be considered to be represented as a series of eight-bit symbols. The principles described are applicable to operations in other bases and data in other representations, but maintaining full generality in the descriptions would be more confusing than enlightening.

0022<figref idrefs="DRAWINGS">FIG. 1</figref> outlines the operations of an adaptive entropy coding compressor including an embodiment of the invention. The following explanation will track the compressor through the flow chart as it processes an input string, “abracadabra”. Compression can be thought of as building a model of the input data and picking a minimal set of clues about the model to send to a decompressor, so that the decompressor can replicate the model and reproduce the input string. <figref idrefs="DRAWINGS">FIG. 2</figref> shows “contexts” of the model. Each context corresponds to symbols the compressor has recently encoded (or symbols the decompressor has recently recovered). The compressor examined in this example uses three-symbol contexts (i.e., each context corresponds to the three most-recently-encountered input symbols). Shorter contexts (two-character, one-character, and no-character contexts) also appear in the model. All the contexts together make up a probability model that, in some sense, represents estimates of the likelihood that a particular symbol will be seen at a certain point in the input.

0023The information in a context can be thought of as a map to sub-segments of a part of a pin (as described in reference to <figref idrefs="DRAWINGS">FIG. 3</figref>). A fully-populated context would have entries giving the length of the pin-segment allocated to each corresponding input symbol. However, since this is an adaptive compressor, each context starts out empty (rather than divided into twenty-six segments for each letter, or 256 segments for each possible eight-bit symbol). As input symbols are encountered, contexts add segments and/or adjust the boundaries between segments so that the context can efficiently encode the input.

0024Although all of the contexts, and the symbols each can encode, are shown in <figref idrefs="DRAWINGS">FIG. 2</figref>, they accumulate over time (as described below). The model starts out empty, with the initial context <b>200</b> able to encode only an escape symbol. The escape symbol is distinct from the 256 possible symbols that could be present in a stream of eight-bit characters.

0025The compressor retrieves the first input symbol (<b>100</b>), a. The current context, <b>200</b>, cannot (yet) encode a (<b>105</b>) so the compressor emits an escape token (<b>110</b>) and moves to a shorter context. Since context <b>200</b> is the shortest (zero-character) context, the compressor is out of contexts (<b>115</b>). It buffers the literal a (<b>120</b>) and adds a to each of the escaped contexts (<b>125</b>). (Element <b>201</b> indicates the a added to context <b>200</b>.) The compressor has not reached the end of its input (<b>130</b>), so it loops back to get the next input symbol (<b>100</b>).

0026The next symbol is b, and the context is a (<b>210</b>). Since context <b>210</b> cannot (yet) encode b (<b>105</b>), the compressor emits an escape token (<b>110</b>) and moves to a shorter context. The next-shortest context is <b>200</b>, so the compressor is not out of contexts (<b>135</b>) and loops back to consider context <b>200</b>. Context <b>200</b> is also unable to encode b (<b>105</b>) (it can currently encode only escape and a), so the compressor emits another escape token (<b>110</b>) and moves to a shorter context. Again, context <b>200</b> is the shortest context, so the compressor is out of contexts (<b>115</b>). The literal, b, is buffered and also added to each escaped context (<b>202</b>, <b>212</b>). So far, the compressor has emitted three escapes and buffered two literals. Only the escape from context <b>200</b> on input symbol b required any bits to encode; all the other escapes were from contexts that could only encode the escape. The physical analogue of this situation is a pin segment that can only encode one symbol: the mark could be anywhere along the whole segment and still convey the necessary information.

0027The next symbol is r and the context is ab (<b>220</b>). Context <b>220</b> cannot encode r (<b>105</b>), so the compressor emits an escape token (<b>110</b>) and moves to shorter context b (<b>230</b>). Context <b>230</b> also cannot encode r (<b>105</b>), so the compressor emits another escape token (<b>110</b>) and moves to shorter context <b>200</b>. Context <b>200</b> cannot encode r (<b>105</b>), so the compressor emits another escape token (<b>110</b>) but is out of contexts (<b>115</b>). Literal r is buffered and added to contexts <b>200</b>, <b>220</b> and <b>230</b> (see <b>203</b>, <b>223</b> and <b>233</b>). The end of the input has still not been reached (<b>130</b>), so the compressor loops back yet again.

0028For the next input symbol, a, the compressor starts at context <b>240</b> and escapes through <b>240</b>, <b>250</b> and <b>260</b> (adding codings <b>244</b>, <b>254</b> and <b>264</b>) before discovering that context <b>200</b> can encode the input symbol (<b>140</b>). Therefore, the compressor emits the appropriate code (<b>145</b>) and loops back again.

0029The following table summarizes the activity of the compressor working through the input string. “<EOS>” signifies the end of the string. “Escapes” is the number of contexts escaped from before a context that can encode the current symbol is found, or a literal must be buffered. “Coding Context” identifies the context that was able to encode a symbol, while “Literal” indicates that the compressor buffered a literal and updated one or more escaped-from contexts.

0000<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="5"><colspec colname="1" colwidth="42pt" align="center" /><colspec colname="2" colwidth="42pt" align="left" /><colspec colname="3" colwidth="42pt" align="center" /><colspec colname="4" colwidth="49pt" align="center" /><colspec colname="5" colwidth="42pt" align="center" /><thead><row><entry namest="1" nameend="5" rowsep="1">TABLE 1</entry></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row><row><entry>Symbol</entry><entry>Start Context</entry><entry>Escapes</entry><entry>Coding Context</entry><entry>Literal</entry></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row></thead><tbody valign="top"><row><entry>a</entry><entry>200 Ø</entry><entry>1</entry><entry /><entry>a</entry></row><row><entry>b</entry><entry>210 a</entry><entry>2</entry><entry /><entry>b</entry></row><row><entry>r</entry><entry>220 ab</entry><entry>3</entry><entry /><entry>r</entry></row><row><entry>a</entry><entry>240 abr</entry><entry>3</entry><entry>200</entry></row><row><entry>c</entry><entry>270 bra</entry><entry>4</entry><entry /><entry>c</entry></row><row><entry>a</entry><entry>275 rac</entry><entry>3</entry><entry>200</entry></row><row><entry>d</entry><entry>280 aca</entry><entry>4</entry><entry /><entry>d</entry></row><row><entry>a</entry><entry>285 cad</entry><entry>3</entry><entry>200</entry></row><row><entry>b</entry><entry>290 ada</entry><entry>3</entry><entry>200</entry></row><row><entry>r</entry><entry>295 dab</entry><entry>3</entry><entry>200</entry></row><row><entry>a</entry><entry>240 abr</entry><entry /><entry>240</entry></row><row><entry><EOS></entry><entry>270 bra</entry><entry>4</entry><entry /><entry><EOS></entry></row><row><entry namest="1" nameend="5" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>

0030After escaping from context <b>270</b> and buffering the the end-of-stream literal, the compressor determines that the end of input has been reached (<b>150</b>). Now, it compresses the buffered literals and emits them in a discernible position relative to the encoded data bits (for example, at the beginning of the encoded stream, at the end of the stream, or at a block boundary in the stream). Concerns affecting the placement of the buffered, compressed literals are discussed below.

0031Several points are important to notice. First, the compressor must emit an enormous number of escapes—often three or four escapes for each input symbol. The escaped-from contexts have only a few different symbols that they can encode (the “pin segment” is divided into only a few, relatively large, sub-segments), so the escapes do not consume many output bits. However, one embodiment of the invention can often obtain an improvement in compression performance by coalescing multiple escape tokens into one “escape n times” token (where n is an integer). For example, context <b>240</b> might encode an “Escape-3” token, which would be used when the second a was encountered. In general, for an n-symbol context, an embodiment adds n+1 one-or-more-level escape tokens: Escape-1, Escape-2, . . . , Escape-n, Escape-n+1. The probabilities (pin-segment lengths) for each of these multilevel escape tokens are adjusted adaptively by the compressor and decompressor, just as are the probabilities for other symbols the context can encode.

0032Second, the <EOS> literal will be encountered exactly once, and will always be the last literal. Therefore, it often does not require any bits to encode (the decompressor can infer its existence and location from other information from the compressed stream). This also means that no literal symbol with more than eight bits will ever be produced, even if the input stream contains at least one symbol for each value.

0033Third, no other literal symbol will be emitted more than once. For an embodiment that deals with eight-bit symbols, a maximum of 256 literal symbols will be buffered, compressed and emitted. No literal will be repeated, so a compression algorithm that depends on repeated characters or sequences will be unable to compress the literals. However, the non-repeating property allows a compressor (and decompressor) to make certain inferences about the literals, which enable them to be encoded in fewer bits (i.e., to be compressed). Specifically, there are 257 different literal values (0-255 symbol values, plus an end-of-stream indicator). The first literal encountered in the stream will have a value between 0 and 255 (an end of stream indicator at this point means that the input is an empty stream, which can be most easily represented in “compressed” form as another empty stream). The second literal encountered can have one of 256 distinct values (either one of the other literal values, or the end of stream indicator), the third, one of 255 values, and so on. The 256^thliteral can have one of two values—the last literal value that has not been seen, or the end of stream indicator. There is no need to code the 257^thliteral: it can only be the end of stream indicator. Using this property that the number of as-yet unseen literals is always decreasing, the literals can be represented in a smaller number of bits than 256×8=2,048.

0034Specifically, denoting the base-2 logarithm function as log₂( ) and the least integer greater than or equal to its argument function as ceil( ), it is trivial to show that the possible permutations of literals can be encoded in

0000<br />ceil(log₂(256)+log₂(256)+log₂(255)+ . . . +log₂(2))   Eq. 1

0000bits, or 1,692 bits (which is actually 211.5 eight-bit bytes, rounded up to 212). Input streams that use fewer than all input symbols can store all their literals in an even smaller number of bits.

0035Furthermore, the order that the literals appear in the buffered series is related to the probabilities of those literals appearing in the input data. Therefore, if the literal-compressor algorithm is preloaded with known or estimated probabilities, then its performance may improve. For example, if the input was English text, then preloading the literals compressor with the symbol distribution for English (e.g., ‘e’ more probable than ‘Q’) will improve the compression of the buffered literals. Alternatively, the probabilities determined by compressing/decompressing a previous stream may be retained for compressing the literals of a succeeding stream. For example, the literals from compressing “abracadabra” were “abrcd<EOS>”. If the next stream is “abraham”, the literals would be “abrhm<EOS>”. Clearly, using information from the “abrcd<EOS>” literals would permit greatly improved compression for the “abrhm<EOS>” literals.

0036<figref idrefs="DRAWINGS">FIGS. 4A-4C</figref> illustrate potential formats of a compressed data stream. <figref idrefs="DRAWINGS">FIG. 4A</figref> shows how, in a prior-art compressor, a series of codes <b>410</b> is interrupted by a literal byte <b>420</b>. The literal is followed by more codes <b>430</b>, which are again interrupted by a second literal <b>440</b>. The code sequences (<b>410</b>, <b>430</b>) can be thought of as an extended binary fraction that expresses the location along a unit-length pin where the message mark lies. As explained above, literals <b>420</b> and <b>440</b> must be emitted at at least a bit boundary, and more likely (for convenience) at a byte boundary. Thus, any fractional bits at the end of code sequences <b>410</b> and <b>430</b> are lost when a literal is emitted.

0037<figref idrefs="DRAWINGS">FIG. 4B</figref> shows how an embodiment of the invention improves this situation: a single, uninterrupted series of compressed codes <b>450</b> are followed by a block of compressed literals <b>460</b>. Since compressed codes <b>450</b> are not interrupted, no fractional bits are lost. <figref idrefs="DRAWINGS">FIG. 4C</figref> shows a modification that improves handling of a compressed data stream prepared according to an embodiment of the invention. Compressed codes <b>450</b> are the same as in <figref idrefs="DRAWINGS">FIG. 4B</figref>, but the compressed literals <b>460</b> have been reversed, <b>470</b>. (Note that the black-filled circles at the left of <b>460</b> are shown at the right of <b>470</b>, indicating this reversal.) This permits the decompressor to read compressed codes using a file pointer <b>480</b> that advances to the right from the beginning of the stream, and to read compressed literals using a file pointer <b>490</b> that advances to the left from the end of the stream. Codes from pointer <b>480</b> are fed directly into adaptive coding decompressor <b>485</b>, while compressed literals are passed to literals decompressor <b>495</b> before being supplied to adaptive coding decompressor <b>485</b>. Decompressor <b>485</b> reconstructs the context model that the compressor built, and uses the decompressed literals and the context model to reconstitute the original input stream.

0038<figref idrefs="DRAWINGS">FIG. 5</figref> is a flow chart outlining the operations of an entropy coding data decompressor according to an embodiment of the invention. The decompressor initializes its context model identically to the compressor's initialized model (<b>510</b>). Recall that despite the large number of contexts (shown in <figref idrefs="DRAWINGS">FIG. 2</figref>) that exist after compressing an input stream, the compressor and decompressor start with just one state, <b>200</b>, that can encode just one symbol, escape.

0039Next, the decompressor gets some compressed bits from the compressed data stream. For example, it may read some data from file pointer <b>480</b> as shown in <figref idrefs="DRAWINGS">FIG. 4C</figref>. The number of compressed bits necessary to decide what to do next varies from time to time, depending on the state of the decompression context. For example, when decompression has just started and context <b>200</b> can only encode escape, no bits are required—the decompressor knows that the compressor must have emitted an escape, because that is the only thing it could emit. Consequently, the escape is encoded in zero bits.

0040Since the first compressed bits encode escape (<b>530</b>), the decompressor moves to a shorter context (<b>540</b>). However, since context <b>200</b> is already the shortest context, the decompressor is out of contexts (<b>555</b>) and requires a literal. It obtains the next literal from the literal decompressor (<b>560</b>), checks to ensure that it has not reached the end-of-stream (<b>565</b>) and outputs the literal as the reconstituted data (<b>570</b>). Referring to Table <b>1</b>, it is clear that the first compressed literal was a, so that symbol is output.

0041Any contexts used (e.g., escaped from) are updated (<b>580</b>), and the decompressor loops back to get more compressed bits (<b>520</b>). (Again, no compressed bits have been used yet, because no existing context could encode anything except Escape.)

0042Now, the decompressor is in context <b>210</b>, because it has just produced the symbol a. Context <b>210</b> is unable to encode any symbol except escape, so the decompressor again consumes zero bits to determine that the next encoded symbol is escape (<b>530</b>). Now, the decompressor moves to the next-shorter context (<b>540</b>), which is context <b>200</b>. It is not out of contexts (<b>550</b>), so it loops back to get more compressed bits (<b>520</b>).

0043Context <b>200</b> currently encodes escape and a, so some information (at least a portion of a compressed bit) is required to decide which. This compressed bit encodes another escape (<b>530</b>). This is the third escape mentioned above in [0026]. The decompressor moves to a shorter context (<b>540</b>) and runs out of contexts (<b>555</b>), so it gets the next literal from the compressed literals (<b>560</b>), notes that it is not end-of-stream (<b>565</b>), and outputs it (<b>570</b>). Recall that the second literal produced during compression was b. The contexts escaped from (<b>210</b>, <b>200</b>) are updated (<b>580</b>) and the decompressor loops back again.

0044This process continues until the characters abr have been recovered and output. The decompressor is in state <b>240</b> and gets some more compressed bits (<b>520</b>). States <b>240</b>, <b>250</b> and <b>260</b> only encode escapes, so no bits are consumed as the decompressor escapes to shorter contexts. When it reaches context <b>240</b>, it discovers that the next compressed bits encode a (<b>535</b>), so it outputs this symbol (<b>590</b>), updates the appropriate contexts (<b>580</b>) and loops back to process more compressed bits.

0045The decompressor continues working through the compressed bits, extracting literals as necessary from the compressed literals block, until there are no more compressed bits to examine. At this point, the original input symbol sequence has been reconstituted and emitted.

0046Note that the decompression process requires literals from the compressed block fairly early in its operations (in fact, the very first thing it does is infer an escape from zero compressed bits, extract a compressed literal and output it). Thus, it is important for the decompressor to have access to the compressed literals as soon as possible. If the decompressor has access to the entire compressed data stream, as shown in <figref idrefs="DRAWINGS">FIG. 4C</figref>, then it can use the dual-file-pointer method depicted to access the literals as necessary. However, if the decompressor is receiving the compressed data stream from a non-seekable source, it must buffer the data until it can determine where the compressed literals are.

0047<figref idrefs="DRAWINGS">FIG. 6A</figref> shows another data layout that may be used to alleviate the buffering requirement. Here, the compressed literals are positioned at the beginning of the compressed data stream (at <b>610</b>), ahead of the uninterrupted compressed symbols <b>620</b>. This arrangement is the best because the decompressor has easy access to all the compressed literals and need not buffer its reconstituted output at all, but it requires the compressor to buffer the compressed symbols <b>620</b> until all but one of the possible literals have been seen (or until the input stream is exhausted). This may place an unsupportable burden on the compressor.

0048A third embodiment, shown in <figref idrefs="DRAWINGS">FIG. 6B</figref>, represents a compromise between forcing either the compressor or decompressor to buffer a large amount of compressed data (potentially, almost all the data), and wasting fractional bits by interrupting coded sequences with compressed literals. The compressor buffers the first portion of compressed codes, up to an even bit (or byte) boundary, or to a maximum buffer length. Any literals emitted to that point are compressed and sent to the output stream (<b>630</b>), followed by the first buffered portion of the compressed symbols (<b>640</b>). More input symbols are compressed and buffered, as are any further literals. When the second buffered codes reach a bit or byte boundary, or fill a maximum buffer length, the collected literals are again compressed and sent (<b>650</b>), ahead of the second buffer of codes (<b>660</b>). This structure repeats until all but one literal have been seen, compressed and sent, and then subsequent output codes (<b>670</b>) may be sent without buffering. In practical implementations of entropy coders, rather than work with arbitrary-precision binary fractions, most compressors and decompressors renormalize the working fraction when it becomes too small to be represented in the computer's natural integer size (e.g., 16 bits, 32 bits or 64 bits). When renormalization occurs, an even bit (or byte) boundary has been reached, so collected literals may be compressed and output.

0049This compromise runs the risk of losing a fraction of a bit for every block of compressed literals. For example, if the compressor emits a block of compressed literals at the first bit boundary in the output stream when there are 16 literals ready to be compressed and output, the compressed literals will occupy 1,700 total bits in the output—losing about 0.5 bits per block of literals.

0050If it is not possible to buffer enough data to arrange for all the compressed literals to appear at either the beginning or end of the compressed data, a reasonable fallback approach would be to accumulate enough literals to have more than a predetermined number of compressed-literal bits in each block of compressed literals. If the predetermined number was, say, 64, then no more than 27 compressed-literals blocks would be required, with the final block being 28 bits long. Each 64-or-greater-bit block would be emitted at the at the next bit or byte boundary in the encoded symbol stream, as discussed in reference to <figref idrefs="DRAWINGS">FIG. 6B</figref>.

0051In more general terms, embodiments of the invention can be thought of as separating the compressed output data stream of an adaptive coder into two parts: encoded symbols that were present in the coder's probability model, and literal symbols that were not present. Symbols that were not present may be added to the model during the “context update” phase of compression and decompression. The first part of the compressed data stream (the encoded symbols that were present in the model) contains only two types of information: encoded versions of input symbols, and encoded “escape” tokens. In some embodiments, all the escape tokens are semantically indistinguishable (each one means “go to the next-shorter context”) although the bits used to encode them may change as the context model adapts. In other embodiments, multi-level escape tokens mean “go to the context that is n symbols shorter than the current context.” Whenever the shortest (zero-symbol) context is escaped, it means “an input symbol that is not not presently part of the model was encountered.” However, the identity of the input symbol is not contained in the first part of the compressed data. To find out what input token was not in the model, one must refer to the literals that were collected, compressed separately, and emitted as the second part of the data output stream.

0052Embodiments of the invention achieve modest improvements in compression efficiency, as measured by the output data size compared to the input data size. For example, literals compression affects at most 256 output bytes—even if the literals compression was able to completely eliminate these bytes, rather than simply shrink them to 212 bytes (or perhaps somewhat fewer, if prior information is used in the compression), the number of saved bytes is small and has a proportionally diminishing effect as the size of the input grows. Placing the compressed literals together in a block, rather than dispersing them throughout the compressed data stream, prevents the waste of no more than 256 fractional bits. Even assuming that each wasted fractional bit was actually a complete bit, blocking the compressed literals can save no more than 32 output bytes. The effect of multi-level escapes is more difficult to assess, because single-level escapes can often be encoded with zero bits, while the availability of several different types of escapes means that any particular escape may require some fraction of a bit to be represented. In any case, as the input data size grows, the compressor's model fills in and escapes become less common. Eventually, for a large and varied data set, every context will have a prediction for every symbol, and no more escapes will be generated. Thus, again, the effect of various embodiments of the invention diminishes with increasing input data set size.

0053However, the compression ratio improvements offered by an embodiment of the invention are not insignificant or diminishing in certain applications. When the compressor must process many independent, moderately-sized blocks, all of the techniques are producing their gains. Many or most literals are typically generated near the beginning of a compression session. A proportionally larger number of escapes are also generated as the contexts fill up. Furthermore, with moderately-sized blocks, the compressor and decompressor are quite likely to be able to buffer the complete input stream, so all the compressed literals can be placed together at the beginning or end of the block, rather than distributed in chunks throughout the input. Also, in many applications, although the individual blocks must be processed independently, there are similarities in data symbol distributions, so the literals compression algorithm can capitalize on probabilities learned from processing other blocks, although the blocks are independent. Therefore, embodiments of the invention may be most useful in processing a large number of independent blocks of modest size (e.g., 512 bytes to 16,384 bytes). (These sizes do not represent a fixed range, outside of which embodiments are not useful, but rather suggest a size range where embodiments are most likely to repay the increased computational costs with correspondingly improved compression ratios.)

0054Applications where a large number of independent, moderately-sized data blocks are processed, and which may benefit from improved compression of those blocks include: block level compression for hard disks (disk block sizes typically run from about 512 bytes to 4,096 bytes); network packet compression (network packet sizes typically run from 64 bytes to 1,536 or 2,048) bytes; and text messaging protocols such the Short Message Service (“SMS,” where cellular message transmission is expensive). Instant Messaging (“IM”) protocols and electronic mail transmission systems may also benefit.

0055<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates a diagrammatic representation of a machine in the exemplary form of a computer system <b>700</b> within which a set of instructions, for causing the machine to perform any one or more of the methodologies discussed herein, may be executed. In alternative embodiments, the machine may be connected (e.g., networked) to other machines in a Local Area Network (LAN), an intranet, an extranet, or the Internet. The machine may operate in the capacity of a server or a client machine in a client-server network environment, or as a peer machine in a peer-to-peer (or distributed) network environment. The machine may be a personal computer (PC), a tablet PC, a set-top box (STB), a Personal Digital Assistant (PDA), a cellular telephone, a web appliance, a server, a network router, switch or bridge, or any machine capable of executing a set of instructions (sequential or otherwise) that specify actions to be taken by that machine. Further, while only a single machine is illustrated, the term “machine” shall also be taken to include any collection of machines (e.g., computers) that individually or jointly execute a set (or multiple sets) of instructions to perform any one or more of the methodologies discussed herein.

0056The exemplary computer system <b>700</b> includes a processor <b>702</b>, a main memory <b>704</b> (e.g., read-only memory (ROM), flash memory, dynamic random access memory (DRAM) such as synchronous DRAM (SDRAM) or Rambus DRAM (RDRAM), etc.), a static memory <b>706</b> (e.g., flash memory, static random access memory (SRAM), etc.), and a secondary memory <b>718</b> (e.g., a data storage device), which communicate with each other via a bus <b>730</b>.

0057Processor <b>702</b> represents one or more general-purpose processing devices such as a microprocessor, central processing unit, or the like. More particularly, the processor <b>702</b> may be a complex instruction set computing (CISC) microprocessor, reduced instruction set computing (RISC) microprocessor, very long instruction word (VLIW) microprocessor, processor implementing other instruction sets, or processors implementing a combination of instruction sets. Processor <b>702</b> may also be one or more special-purpose processing devices such as an application specific integrated circuit (ASIC), a field programmable gate array (FPGA), a digital signal processor (DSP), network processor, or the like. Processor <b>702</b> is configured to execute the processing logic <b>726</b> for performing the operations and steps discussed herein.

0058The computer system <b>700</b> may further include a network interface device <b>708</b>. The computer system <b>700</b> also may include a video display unit <b>710</b> (e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)), an alphanumeric input device <b>712</b> (e.g., a keyboard), a cursor control device <b>714</b> (e.g., a mouse), and a signal generation device <b>716</b> (e.g., a speaker).

0059The secondary memory <b>718</b> may include a machine-readable storage medium (or more specifically a computer-readable storage medium) <b>731</b> on which is stored one or more sets of instructions (e.g., software <b>722</b>) embodying any one or more of the methodologies or functions described herein. The software <b>722</b> may also reside, completely or at least partially, within the main memory <b>704</b> and/or within the processing device <b>702</b> during execution thereof by the computer system <b>700</b>, the main memory <b>704</b> and the processing device <b>702</b> also constituting machine-readable storage media. The software <b>722</b> may further be transmitted or received over a network <b>720</b> via the network interface device <b>708</b>.

0060The machine-readable storage medium <b>731</b> may also be used to store a dispatcher and/or application manager, and/or a software library containing methods that call management applications and/or dispatchers. While the machine-readable storage medium <b>731</b> is shown in an exemplary embodiment to be a single medium, the term “machine-readable storage medium” should be taken to include a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions. The term “machine-readable storage medium” shall also be taken to include any medium that is capable of storing or encoding a set of instructions for execution by the machine and that cause the machine to perform any one or more of the methodologies of the present invention. The term “machine-readable storage medium” shall accordingly be taken to include, but not be limited to, solid-state memories, and optical and magnetic media.

0061An embodiment of the invention may be a machine-readable medium having stored thereon data and instructions (software) to cause a programmable processor to perform operations as described above. In other embodiments, the operations might be performed by specific hardware components that contain hardwired logic. Those operations might alternatively be performed by any combination of programmed computer components and custom hardware components.

0062In some embodiments, the instructions for a programmable processor may be treated as data and manipulated as described in <figref idrefs="DRAWINGS">FIG. 8</figref>. At a first station, a carrier signal is modulated to encode data representing the instructions for a programmable processor (<b>810</b>). The modulated, data-bearing signal is transmitted over a distributed data network (<b>820</b>) such as the Internet, where it is received by a second station (<b>830</b>). The signal is demodulated to recover the data representing instructions for a programmable processor (<b>840</b>), and those instructions are saved on one or more machine-readable media (<b>850</b>). Finally, a programmable processor at the second station executes the instructions (<b>860</b>) to cause the second station to perform operations according to an embodiment of the invention. In the vernacular, such modulation and transmission are known as “serving” the instructions, while receiving and demodulating are often called “downloading.” In other words, one embodiment “serves” (i.e., encodes and sends) the instructions of an embodiment to a client, often over a distributed data network like the Internet. The instructions thus transmitted can be saved on a hard disk or other data storage device at the receiver to create another embodiment of the invention, meeting the description of a machine-readable medium storing data and instructions to perform some of the operations discussed above. Executing such an embodiment at the receiver may result in the receiver performing operations according to a third embodiment.

0063Instructions for a programmable processor may be stored in a form that is directly executable by the processor (“object” or “executable” form), or the instructions may be stored in a human-readable text form called “source code” that can be automatically processed by a development tool commonly known as a “compiler” to produce executable code. Instructions may also be specified as a difference or “delta” from a predetermined version of a basic source code. The delta (also called a “patch”) can be used to prepare instructions to implement an embodiment of the invention, starting with a commonly-available source code package that does not contain an embodiment.

0064In the foregoing description, numerous details were set forth. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In some instances, well-known structures and devices were shown in block diagram form, rather than in detail, in order to avoid obscuring the present invention.

0065Some portions of the detailed descriptions were presented in terms of algorithms and symbolic representations of operations on data bits within a computer memory. These algorithmic descriptions and representations are the means used by those skilled in the data processing arts to most effectively convey the substance of their work to others skilled in the art. An algorithm is here, and generally, conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of electrical or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

0066It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the foregoing discussion, it is appreciated that throughout the description, discussions utilizing terms such as “sending,” “receiving,” “attaching,” “forwarding,” “caching,” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

0067The present invention also relates to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general purpose computer selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, and magnetic-optical disks, read-only memories (ROMs), random access memories (RAMs), EPROMs, EEPROMs, magnetic or optical cards, or any type of media suitable for storing electronic instructions, each coupled to a computer system bus.

0068The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general purpose systems may be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear as set forth in the description below. In addition, the present invention was not described with reference to any particular programming language. It will be appreciated that a variety of programming languages may be used to implement the teachings of the invention as described herein.

0069The present invention may be provided as a computer program product, or software, that may include a machine-readable medium having stored thereon instructions, which may be used to program a computer system (or other electronic devices) to perform a process according to the present invention. A machine-readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine-readable (e.g., computer-readable) medium includes a machine (e.g., a computer) readable storage medium (e.g., read only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices, etc.), a machine (e.g., computer) readable transmission medium (electrical, optical, acoustical or other form of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.)), etc.

0070The applications of the present invention have been described largely by reference to specific examples and in terms of particular allocations of functionality to certain hardware and/or software components. However, those of skill in the art will recognize that the performance (compression ratio) of adaptive coding compression algorithms can be improved by software and hardware that distribute the functions of embodiments of this invention differently than herein described. Such variations and implementations are understood to be captured according to the following claims.