Patent Description:
Typically, compression can be accomplished by removing redundancy in the information. As an example, if a text file is being compressed, it is possible and highly likely that certain words or phrases repeatedly appear in the uncompressed text file. For example, in this very patent application, certain words will be repeated with varying degrees of frequency. Compression could involve using a word dictionary that replaces certain commonly used human-readable text sequences with smaller non-human-readable replacements. Another way is to use a combination of literal text and copy instructions in the compressed form. As an example, the LZ4 compression method compresses by replacing the text by a combination of literals and copy instructions from prior portions of the uncompressed text.

Rather, this background is only provided to illustrate one exemplary technology area where some embodiments describe herein may be practiced.

The README. md page for gztool at GitHub describes that gzip is file indexer, compressor and data retriever and the gztool creates small indexes for gzipped files and uses them for quick and random data extraction.

The Wikipedia article on gzip describes that gzip is a file format and software application used for filed compression and decompression that is based on the DEFLATE algorithm, which is a combination of LZ77 and Huffman coding.

The principles described herein relate to compression of data being done in a way that permits direct reconstruction of arbitrary portions of the uncompressed data. Conventional compression is done such that decompression has to begin either at the very beginning of the data, or at particular large intervals (e.g., at block boundaries - every <NUM> kilobytes) within the data. However, the principles described herein permit decompression to begin at any point within the compressed data, without having to decompress any prior portion of the data. Thus, the principles described herein permit rapid random access of the compressed data. In accordance with the principles described herein, this is accomplished by using an index that correlates positions within the uncompressed data with positions within the compressed data, wherein the correlations within the index include, for each of the at least some positions in the uncompressed data, the following: an identity of the compressed segment and an uncompressed offset within that compressed segment.

The invention is exclusively defined by the appended claims.

Understanding that these drawings depict only typical examples useful to understand the claimed invention and are not therefore to be considered to be limiting in scope, examples will be described and explained with additional specificity and details through the use of the accompanying drawings in which:.

The principles described herein relate to compression of data being done in a way that permits direct reconstruction of arbitrary portions of the uncompressed data. Conventional compression is done such that decompression has to begin either at the very beginning of the data, or at particular large intervals (e.g., at block boundaries - every <NUM> kilobytes) within the data. However, the principles described herein permit decompression to begin at any point within the compressed data, without having to decompress any prior portion of the data. Thus, the principles described herein permit rapid random access of the compressed data. In accordance with the principles described herein, this is accomplished by using an index that correlates positions within the uncompressed data with positions within the compressed data.

Whatever compression technique is used, the compression tracks correlations between at least some positions in the uncompressed data and corresponding positions in the compressed data. The compression then constructs an index that records the correlation between the positions in the uncompressed data and the corresponding positions in the compressed data. An index that includes these correlations is constructed and associated with the compressed data, so that the index is available for construction of arbitrary portions of the uncompressed data from the index and from the compressed data. For example, the index could include an entry for every regular interval of bytes in the uncompressed data (e.g., for each uncompressed byte address location that is a multiple of <NUM>).

As an example, in one embodiment, the compression occurs one compressed segment at a time, so that the compressed data includes a sequence of compressed segments. The index includes (for every so many uncompressed bytes) the identity of the compressed segment as well as the uncompressed offset within that compressed segment that represents that information (e.g., segment portion <NUM>, <NUM> uncompressed bytes in).

This permits random access during decompression at any defined start position of a piece of uncompressed data to be accessed. Given that start position, the decompression uses the index to identify a corresponding position in the compressed data. The decompression then navigates to that position, and from there traverses an appropriate number of further uncompressed bytes to find the beginning of the uncompressed portion to access. The decompression then begins decompressing until an appropriate size of uncompressed portion is formed.

As an example, suppose that the uncompressed data to access is from uncompressed byte <NUM> to uncompressed byte <NUM> (so <NUM> uncompressed bytes long). Suppose further that the compressed data is formed of a sequence of compressed segments, and that there is an index entry at regular intervals of <NUM> uncompressed bytes. The decompression will use the index entry for uncompressed byte address <NUM> to identify the compressed segment and uncompressed byte offset that corresponds to uncompressed byte address <NUM>. Suppose that that index entry identifies compressed segment <NUM> and <NUM> uncompressed bytes in. The decompression would obtain compressed segment <NUM>, and traverse <NUM> bytes from the beginning of the compressed segment (potentially reaching into subsequent compressed segments) to reach the start position. Then, the decompression would decompress from that position for <NUM> more uncompressed bytes to extract the desired portion.

Because the principles described herein are performed in the context of a computing system, some introductory discussion of a computing system will be described with respect to <FIG>.

As illustrated in <FIG>, in its most basic configuration, a computing system <NUM> includes at least one hardware processing unit <NUM> and memory <NUM>. The processing unit <NUM> includes a general-purpose processor. Although not required, the processing unit <NUM> may also include a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or any other specialized circuit. In one embodiment, the memory <NUM> includes a physical system memory. That physical system memory may be volatile, non-volatile, or some combination of the two. In a second embodiment, the memory is non-volatile mass storage such as physical storage media. If the computing system is distributed, the processing, memory and/or storage capability may be distributed as well.

The computing system <NUM> also has thereon multiple structures often referred to as an "executable component". For instance, the memory <NUM> of the computing system <NUM> is illustrated as including executable component <NUM>. The term "executable component" is the name for a structure that is well understood to one of ordinary skill in the art in the field of computing as being a structure that can be software, hardware, or a combination thereof. For instance, when implemented in software, one of ordinary skill in the art would understand that the structure of an executable component may include software objects, routines, methods (and so forth) that may be executed on the computing system. Such an executable component exists in the heap of a computing system, in computer-readable storage media, or a combination.

One of ordinary skill in the art will recognize that the structure of the executable component exists on a computer-readable medium such that, when interpreted by one or more processors of a computing system (e.g., by a processor thread), the computing system is caused to perform a function. Such structure may be computer readable directly by the processors (as is the case if the executable component were binary). Alternatively, the structure may be structured to be interpretable and/or compiled (whether in a single stage or in multiple stages) so as to generate such binary that is directly interpretable by the processors. Such an understanding of example structures of an executable component is well within the understanding of one of ordinary skill in the art of computing when using the term "executable component".

While not all computing systems require a user interface, in some embodiments, the computing system <NUM> includes a user interface system <NUM> for use in interfacing with a user. The user interface system <NUM> may include output mechanisms 112A as well as input mechanisms 112B. The principles described herein are not limited to the precise output mechanisms 112A or input mechanisms 112B as such will depend on the nature of the device. However, output mechanisms 112A might include, for instance, speakers, displays, tactile output, virtual or augmented reality, holograms and so forth. Examples of input mechanisms 112B might include, for instance, microphones, touchscreens, virtual or augmented reality, holograms, cameras, keyboards, mouse or other pointer input, sensors of any type, and so forth.

For the processes and methods disclosed herein, the operations performed in the processes and methods may be implemented in differing order.

In accordance with the principles described herein, a mechanism is described that allows any arbitrary portion of uncompressed data to be accessed from compressed data. Part of this mechanism involves the way the uncompressed data is compressed, which is described by way of example with respect to <FIG>. Thereafter, a mechanism to access a portion of the uncompressed data from that compressed data will then be described with respect to <FIG>.

First, compression is described. <FIG> illustrates a flowchart of a method <NUM> for compressing so as to permit reconstruction of arbitrary portions of the uncompressed data, in accordance with the principles described herein. <FIG> illustrates an environment <NUM> in which compression and decompression can occur and will be frequently be referred to when describing the compression of <FIG>. As an example, the compression of <FIG> may be performed by a computing system, such as the computing system <NUM> of <FIG>. In that case, the method <NUM> may be performed by an executable component, such as the executable component <NUM> of <FIG>.

The method includes generating compressed data from uncompressed data (act <NUM>), and while doing so, tracking correlations between at least some positions in the uncompressed data and corresponding positions in the compressed data (act <NUM>). The compression also constructs an index that records these correlations (act <NUM>). The compression also associates the index with the compressed data (act <NUM>) so that the index is available during decompression. The decompression then can use the index to reconstruct arbitrary portions of the uncompressed data from the compressed data.

As an example, in <FIG>, the uncompressed data <NUM> is compressed into compressed data <NUM>. The compressed data <NUM> could be a file, a database, or any other data structure that is suitable for accessing arbitrary portions of the data structure. Furthermore, the compression formulates an index <NUM> of correlations between positions of the compressed data <NUM> and corresponding compressed positions.

As an example, the index <NUM> includes correlation entries <NUM> that include entries 331A through 331N that correlate respective uncompressed positions A through N within the uncompressed data <NUM> with corresponding compressed positions within the compressed data <NUM>. The index <NUM> is associated with the compressed data <NUM> as represented by the line <NUM>. Compression of the uncompressed data <NUM> into compressed data <NUM> and the associated index <NUM> is generally represented by arrow <NUM>. On the other hand, decompression of arbitrary portions of the uncompressed data <NUM> from the compressed data <NUM> and associated index <NUM> is generally represented by arrow <NUM>. The combination of the compressed data <NUM> and the index <NUM> fully represent content of the uncompressed data <NUM>, albeit in compressed form.

In one example, there is a correlation for positions at fixed intervals of the uncompressed data. For example, <FIG> illustrates that there are several locations A through N at fixed intervals within the uncompressed data <NUM>. In one embodiment, the fixed interval is spaced by a fixed amount that falls between <NUM>^<NUM> and <NUM>^<NUM> uncompressed bytes, inclusive. It is advantageous to have that fixed interval be a binary power (i.e., <NUM>^m where "m" is a whole number) of uncompressed bytes. This would allow the decompression to rapidly find the appropriate entry corresponding to any uncompressed byte address within the index <NUM> using the most significant bits (all bits other than the m least significant bits) in the uncompressed byte address. This would also allow the decompression to rapidly find an uncompressed byte offset from the interval boundary using the m least significant bits.

In a simple example, if the interval was every <NUM> (<NUM>^<NUM>) uncompressed bytes and there were only <NUM> (<NUM>^<NUM>) intervals altogether, each uncompressed byte can be uniquely identified using a single <NUM>-bit number. If the uncompressed byte address were binary <NUM>, then the three most significant bits <NUM> can be used to determine that the uncompressed byte is within the sixth (<NUM>) interval (i.e., <NUM> would be the first interval), and is at seventh uncompressed byte (<NUM>) uncompressed bytes in that interval (note <NUM> would be the first uncompressed byte in that interval). Thus, use of intervals in binary powers assists with rapid use of the index during decompression.

In one more specific embodiment, the fixed interval is between <NUM>^<NUM> and <NUM>^<NUM> uncompressed bytes, inclusive. A fixed interval smaller than <NUM>^<NUM> uncompressed bytes would cause the index to be a significant percentage of the uncompressed data size, thereby working against the objective of achieving a good compression ratio. As an example, if each index entry were two bytes, and the uncompressed interval was <NUM> (or <NUM>^<NUM>) uncompressed bytes, the index would be roughly <NUM> percent of the original data size, and that is just for the index. On the other hand, if the spacing is <NUM> (or <NUM>^<NUM>) uncompressed bytes, the average number of uncompressed bytes to traverse to get to a compressed position that corresponds to the beginning of the interval (a maximum of <NUM> bytes, but an average of about <NUM> bytes) would be large, thereby increasing latency for accessing arbitrary portions of the uncompressed data. Thus, the fixed interval is some binary power of uncompressed bytes between <NUM>^<NUM> and <NUM>^<NUM>. It is possible that a central portion of this range <NUM>^<NUM> or <NUM>^<NUM> uncompressed bytes for the fixed interval may provide a sweet spot balancing compression ratio and decompression latency.

<FIG> shows an environment <NUM> that is similar to the environment <NUM> of <FIG>, except that the environment <NUM> shows the compressed data <NUM> as an example of the compressed data <NUM>. The compressed data <NUM> includes a sequence <NUM> of compressed segments. While this sequence <NUM> could include any number of compressed segments, by way of illustration and example only, the sequence <NUM> is shown as including compressed segments <NUM> through <NUM>. In such a case, each of the correlation entries 331A through 331D includes an identity of the compressed segment and an uncompressed offset. Each compressed segment compresses a range of uncompressed bytes. The uncompressed byte offset represents an uncompressed byte position within that range. As an example, a compressed segment <NUM> perhaps represents a compressed form of the information from uncompressed byte address <NUM> to <NUM>. If the index entry is for uncompressed byte position <NUM> (which is a multiple of <NUM>), then the uncompressed offset would represent the fifth byte from the beginning because <NUM> minus <NUM> is equal to <NUM>.

Herein, an "identity" of a compressed segment is any value that uniquely identifies a compressed segment amongst the sequence of compressed segments. As an example, that value could be an address of the beginning of the compressed segment. Thus, in this description and in the claims, an "identity" of a compressed segment is broad enough to encompass all ways to uniquely identify a compressed segment, including addresses of the compressed segment. Use of addresses as the identifier is advantageous in that once the identifier address is known, the compressed segment can be obtained without further lookup of another address.

<FIG> illustrates an environment <NUM> that is similar to the environment <NUM> of <FIG>, except that the environment <NUM> shows the compressed data <NUM> as an example of the compressed data <NUM>, and the compressed segments <NUM> through <NUM> as an example of the respective compressed segments <NUM> through <NUM>. In the example of <FIG>, each of at least some of the compressed segments <NUM> through <NUM> includes a literal part (represented in <FIG> as the part of the compressed segments that are not filled in), and a copy instruction part (represented in <FIG> as the part of the compressed segments that have leftward-leaning hash marks).

The literal part includes literal uncompressed bytes of the uncompressed data. These are parts where no substantial redundant information was found to take advantage of in order to compress the data. In <FIG>, each of the compressed segments <NUM> through <NUM> includes a literal part constituting bytes copied from the uncompressed data. For instance, compressed segment <NUM> is entirely a literal part, and compressed segments <NUM> through <NUM> each include a respective literal part 532A through 537A.

The copy instruction part includes instructions to copy from one or more byte ranges of one or more prior compressed segments in the sequence of compressed segments. The copy instruction part provides instructions to copy that will be followed during decompression, and includes a location within the compressed data to copy from as well as the number of bytes to copy. This copy instruction part enables compression to occur as the copy instruction is represented more compactly than the bytes that will be copied in order to decompress. In the illustrated example, the compressed segments <NUM> through <NUM> includes corresponding copy instruction parts 532B through 537B. As an example, as represented by arrow <NUM>, the copy instruction part 536B of the compressed segment <NUM> includes an instruction to copy from the compressed segment <NUM>. Thus, in the example of <FIG>, during compression of each compressed segment one at a time, the compression looks for redundant information in the compressed data, and represents that information with an instruction to copy, rather than including all of those bytes.

An example will now be described in which the uncompressed data is text. Suppose that the following text is to be compressed. [
{ "name": "Scott", "city": "Redmond", "lastSignedOn": "<NUM>-<NUM>-<NUM>" },
{ "name": "Amy", "city": "Salt Lake City", "lastSignedOn": "<NUM>-<NUM>-<NUM>" },.

This could potentially be compressed as in the following Table <NUM>, where each row represents a distinct compressed segment, and the left column represents literals, while the right column represents the text that is formulated by a copying from a previous compressed segment (a higher row when represented in table form), or from the literal part of the current compressed segment.

The copy instruction part instructs to copy from one or more previous compressed segments in the sequence of compressed segments. However, the compression ensures that the one or more prior compressed segments from which bytes can be copied are confined to be no earlier in the sequence of compressed segments than a predetermined number of bytes. For instance, this limitation in the copying is represented in <FIG> by bracket <NUM>. The predetermined number of bytes may be kept low enough that the bytes may be read from the sequence <NUM> in a single read request, thereby enabling faster decompression. Furthermore, this allows the decompression process to be bound. As an aside, a smart compressor could improve compression ratio by putting the literal "lastSignedOn": "<NUM>-<NUM>-<NUM>", }, earlier, so that it could later copy reusable parts of this literal.

In one embodiment, the predetermined number of bytes is a binary power (i.e., of size <NUM>^n where "n" is a whole number). The lower "n" is, the less opportunity for compression, but the lower the memory needed to keep the number of bytes in order to compress and decompress. On the other hand, the higher "n" is, the more opportunity there is for compression, but the higher the memory needed to compress and decompress. If "n" is very high, it is possible that multiple read requests will be needed to access compressed data during any given reconstruction of arbitrary portions of the uncompressed data. Thus, there is a balance between compression ratio on the one hand, and on the other hand, memory usage and access latency. In one embodiment, "n" is at least ten to ensure a good compression ratio. In another embodiment, "n" is at most fifteen in order to ensure population of memory during a single read request. In yet another embodiment, "n" is a whole number between ten and fifteen, inclusive.

Although the principles described herein show each compressed segment as including at most one literal part and one copy instruction part, in some embodiments, a compressed portion can include multiple literals and copy instructions parts, or may include zero literal parts (only copy instruction part(s)) or zero copy instruction parts (only literal part(s)). However, sufficient header information is used for each part that the decompression can identify the boundary between literal parts and copy instruction parts. Thus, given the uncompressed byte address, the decompression process can still traverse the compressed segment counting uncompressed bytes that it traverses in order to find an appropriate position to begin decompression from.

Now that an example compression mechanism has been described with respect to <FIG>, a decompression method will now be described with respect to <FIG> illustrates a flowchart of a method <NUM> for decompressing arbitrary portions of compressed data, in accordance with the principles described herein. As an example, the decompression of <FIG> may be performed by a computing system, such as the computing system <NUM> of <FIG>. In that case, the method <NUM> may be performed by an executable component, such as the executable component <NUM> of <FIG>.

The decompression can be done starting from an identified start position of the uncompressed data. Accordingly, the method <NUM> begins by identifying a start position of a portion of the uncompressed data to be accessed (act <NUM>). Rather than having this start position necessarily be at the beginning of the uncompressed data, or at the beginning of any given block, the start position can be from any byte of the uncompressed data. Thus, the identified start position can be a byte address of the uncompressed data.

The method <NUM> also includes accessing an index associated with the compressed data (act <NUM>). This index correlates between locations in the compressed data and corresponding locations in the uncompressed data. In the example of <FIG>, this index is the index <NUM>, which includes correlations 331A through 331N between positions A through N of the compressed data <NUM> and corresponding positions within the compressed data <NUM> for <FIG>, compressed data <NUM> for <FIG>, and compressed data <NUM> for <FIG>. There is no temporal dependency between the identification of the start position (act <NUM>) and the accessing of the index (act <NUM>). Accordingly, acts <NUM> and <NUM> are shown in parallel.

The decompression method <NUM> process then finds a correlation within the index that includes a corresponding position in the uncompressed data that is prior to the identified start position of the portion of the uncompressed data to access (act <NUM>). The decompression method <NUM> then uses that correlation to find an exact position in the compressed data that corresponds to the identified start position of the portion of uncompressed data to access (act <NUM>). From there, the decompression method <NUM> decompresses from the found exact position until the entire portion of uncompressed data is decompressed (act <NUM>). The end of the decompression process does not need to be at the end of the compressed data, nor at any boundary between blocks. Rather, the end of the portion of the uncompressed file that is being accessed may be any byte address. Thus, any arbitrary portion of the uncompressed data can be accessed directly from the compressed data.

This might best be illustrated by way of an example. Suppose that the index is structured to include the information in the following Table <NUM>.

This example includes an entry every <NUM> uncompressed bytes, and tells how to get to the corresponding position in the compressed portion. Specifically, to get to a particular compressed position that corresponds to the uncompressed byte address of the entry, the process would begin from the identified compressed segment and then traverse a certain number of uncompressed bytes.

In a first example, the arbitrary portion of the uncompressed data to access is <NUM> bytes beginning at uncompressed byte address <NUM>. Accordingly, the uncompressed byte address to begin decompression from is identified as uncompressed byte address <NUM> (act <NUM>). Based on this uncompressed byte address start position, the decompression then uses the index (e.g., the information from Table <NUM>) to identify a corresponding position in the uncompressed data that is prior to the identified start position of the portion of the uncompressed data to access (act <NUM>). In this example, uncompressed byte address <NUM> is just prior to the identified start uncompressed address of <NUM>.

Accordingly, the entry correlating the uncompressed byte address <NUM> is used to find the exact position in the compressed data that corresponds to the identified start position of uncompressed byte address <NUM> (act <NUM>). Referring to Table <NUM>, the decompression can identify that uncompressed byte address <NUM> (and thus compressed segment <NUM>) is at or just prior to the exact position that corresponds to the identified start position (act <NUM>) (uncompressed byte address <NUM>).

Furthermore, since the decompression would have to traverse <NUM> uncompressed bytes into the compressed segment to get to the position corresponding to uncompressed byte address <NUM>, and since the start position byte address <NUM> is even <NUM> uncompressed bytes beyond that, the decompression determines to traverse <NUM> bytes into the compressed segment <NUM> to get to the exact start position of the decompression. "Traversing" uncompressed bytes in compressed data means that decompression counts the number of uncompressed bytes it encounters, but does not need to actually know what those traversed uncompressed bytes are. Thus, such traversing does not need to actually decompress anything.

To traverse through compressed segments that include copy instruction parts, the decompression process would load the predetermined number of bytes (see bracket <NUM> of <FIG>) prior to the current compressed segment). From that point, the decompression would be applied to the next <NUM> bytes. The loaded predetermined number of bytes (see bracket <NUM> of <FIG>) will also assist in decompressing should decompression involve interpreting a copy instruction part.

<FIG> illustrates an example compressed segment <NUM> in further detail and will be used to illustrate the first example. In this example, the compressed segment <NUM> includes <NUM> bytes of literal bytes 29A copied directly from the uncompressed data <NUM> during compression, as well as <NUM> additional bytes of copy instruction 29B (from byte <NUM> to byte <NUM>). As previously described, in this example, the compressed segment has the uncompressed byte address <NUM> that corresponds to information <NUM> bytes into compressed portion <NUM>, which is the same as the information that is <NUM> bytes into the literal part 29A of the address portion, as represented by vertical line 601A. Furthermore, to get to uncompressed byte address <NUM> that corresponds to information where decompression is to start from, the decompression actually traverses <NUM> bytes (<NUM> bytes plus <NUM> bytes) into the compressed segment <NUM>, which is the same as the information that is <NUM> bytes into the literal part 29A, as represented by the vertical line 602A. This vertical line (at bytes address <NUM> in the literal part 29A) is the exact position at which decompression is to start.

Accordingly, the decompression proceeds by copying bytes from byte <NUM> in the literal part 29A (from line 602A). Furthermore, since the next six bytes of information happen to all be within the literal part 29A, the decompression of the six bytes of uncompressed data involves simply copying from bytes <NUM> to <NUM> of the literal part 29A of the compressed segment <NUM>. These bytes are represented by the region with the leftward-leaning line fills in Figure 6A between lines 602A and 603A.

The first example was quite simple as all of the uncompressed bytes to be randomly accessed from the compressed data happen to all have been bytes that were literally copied directly from the uncompressed data in the first place. The second example is slightly more complicated and will involve decompression by copying from the literal part 29A as well as partially following a copy instruction in a copy instruction part 29B of the compressed segment <NUM>.

In a second example, the uncompressed byte address to begin decompression from is identified as uncompressed byte address <NUM> (act <NUM>), the same as in the first example. However, the uncompressed portion to access is now <NUM> uncompressed bytes long. The same as in the first example, the decompression traverses to the position <NUM> bytes into the compressed segment <NUM> to begin decompression as again represented by line 602A. Accordingly, the first <NUM> uncompressed bytes can be decompressed simply by copying the remainder (from byte <NUM> to byte <NUM>) of the literal part 29A of the compressed segment <NUM>.

However, <NUM> more uncompressed bytes still are to be decompressed from the compressed portion in order to total <NUM> uncompressed bytes. Accordingly, the decompression follows the copy instruction of the copy instruction part 29B. In this example, suppose that the copy instruction instructs to copy <NUM> bytes from a particular position of a prior compressed segment. As illustrated in Figure 6B, the copied portion 29C represents bytes <NUM> to <NUM> that would be copied should compressed portion <NUM> be decompressed in its entirety (thus the <NUM> bytes of the compressed portion plus some headers, would decompress into <NUM> uncompressed bytes). However, since only <NUM> more uncompressed bytes are needed (ending at line 603B), the decompression only follows the copy instruction with respect to the first <NUM> bytes (from byte <NUM> to byte <NUM>).

In a third example, the uncompressed byte position to begin with is uncompressed byte position <NUM>. The decompression first seeks <NUM> uncompressed bytes from the uncompressed byte <NUM>, or in other words <NUM> uncompressed bytes from the beginning of the compressed segment <NUM>. As apparent from the discussion of the second example, decompression would begin from uncompressed byte <NUM> found in the copied portion 29C. If ten uncompressed bytes were to be obtained, then uncompressed bytes <NUM> through <NUM> would be obtained from the copied portion 29C. If <NUM> uncompressed bytes were to be obtained, then all of the remaining uncompressed bytes <NUM> through <NUM> would be obtained as part of decompressing <NUM> of those <NUM> bytes, and then the first <NUM> bytes of the literal part of the next compressed segment <NUM> would then be copied to complete the extraction.

Accordingly, the principles described herein allow the ability to access any position of compressed data without having to decompress any part of the compressed data except for the portion of the compressed data that actually contains the information to be accessed in uncompressed form. Thus, the principles described herein enable random access of compressed data, opening up a completely new technical usage for compressed data.

Claim 1:
A method (<NUM>) for compressing (<NUM>) data so as to permit reconstruction of arbitrary portions of the uncompressed data (<NUM>), the method comprising:
generating (<NUM>) the compressed data (<NUM>) from the uncompressed data (<NUM>), the compressed data comprising a sequence of compressed segments and where at least some of the sequence of compressed segments comprise:
a literal part that includes literal uncompressed bytes of the uncompressed data, and
a copy instruction part that includes instructions to copy from one or more byte ranges of one or more prior compressed segments in the sequence of compressed segments;
while generating the compressed data, tracking (<NUM>) correlation (331A - 331N) between at least some positions (A-N) in the uncompressed data and corresponding positions in the compressed data;
constructing (<NUM>) an index (<NUM>) that records the correlations between the at least some positions in the uncompressed data and the corresponding positions in the compressed data, wherein the correlations within the index include, for each of the at least some positions in the uncompressed data, the following: an identity of the compressed segment and an uncompressed offset within that compressed segment; and
associating (<NUM>, <NUM>) the index with the compressed data so that the index is available for reconstruction of arbitrary portions of the uncompressed data from the index and compressed data.