Methods and Apparatus for Reducing Storage Size

• US 20080050025A1
• Filed: 07/06/2007
• Published: 02/28/2008
• Est. Priority Date: 08/24/2006
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Ocarina Networks, Inc. (Dell Technologies Inc.)
• Inventors: Brueggemann, Eric, Rao, Goutham, George, Carter, Bashyam, Murali
• Granted Patent: US 7,961,959 B2
• Time in Patent Office: Days
• US Class Current: 382/238
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/002 using neural networks
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: H04N 19/119 Adaptive subdivision aspects, e.g. subdivision of a picture into rectangular or non-rectangular coding blocks
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/129 Scanning of coding units, e.g. zig-zag scan of transform coefficients or flexible macroblock ordering [FMO]
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/136 Incoming video signal characteristics or properties
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/182 the unit being a pixel
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/23 with coding of regions that are present throughout a whole video segment, e.g. sprites, background or mosaic
• CPC Class Codes: H04N 19/593 involving spatial prediction techniques
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/94 Vector quantisation
• CPC Class Codes: H04N 19/97 Matching pursuit coding

Abstract

Prediction-based compression engines are spoon-fed with sequentially efficiently compressible (SEC) streams of input data that make it possible for the compression engines to more efficiently compress or otherwise compact the incoming data than would be possible with streams of input data accepted on a TV-raster scan basis. Various techniques are disclosed for intentionally forming SEC input data streams. Among these are the tight packing of alike files or fragments into concatenation suitcases and the decomposition of files into substantially predictably consistent (SPC) fragments or segments that are routed to different suitcases according to their type. In a graphics-directed embodiment, image frames are partitioned into segment areas that are internally SPC and multidirectional walks (i.e., U-turning walks) are defined in the segment areas where these defined walks are traced during compression and also during decompression. A variety of pre-compression data transformation methods are disclosed for causing apparently random data sequences to appear more compressibly alike to each other. The methods are usable in systems that permit substantially longer times for data compaction operations than for data decompaction operations.

Claims

1. A method of reducing storage size of information represented initially by first digital data stored in first storage space, the method including machine-implemented steps comprising:

(a) identifying within the first digital data, first data sequences that are predictively alike to one another or are overlappingly predictively alike, where the first data sequences are spaced apart storage address-wise in the first storage space from one another although not necessarily spaced apart application-space wise from each other;

(b) physically or logically grouping the identified first data sequences for consecutive presentation as part of an input data stream to a data compression engine that uses an incoming stream statistics predictor when generating compressed code that compactly represents the input data stream;

(c) consecutively supplying partially bit-stripped versions or whole versions of the identified first data sequences as part of the input data stream to the data compression engine and obtaining corresponding first compressed code from the compression engine;

(d) storing the first compressed code; and

(e) deleting from said first storage space the first data sequences that had been used to obtain said corresponding first compressed code from the compression engine.

2. The reducing method of claim 1 wherein said incoming stream predictor is an adaptive predictor that adaptively changes a prediction model thereof in response to changes in symbol statistics of the supplied input data stream.

3. The reducing method of claim 1 wherein said identifying comprises:

(a.1) statistically analyzing the first digital data and responsively partitioning the first storage space into first segments respectively containing the first data sequences and partitioning the first storage space into one or more second segments respectively containing second data sequences that are mutually exclusive of the identified first data sequences and are predictively unalike relative to the identified first data sequences.

4. The reducing method of claim 3 wherein said identifying further comprises:

(a.2) defining respective storage addressing walks that walk through respective ones of the first segments, where the defined addressing walks at least partly define the data of the input data stream supplied to the data compression engine.

5. The reducing method of claim 4 wherein said grouping comprises:

(b.1) defining a sequence of discontinuous addressing jumps including a first jump from an end of a first addressing walk through a corresponding first of the first segments to a start of a second addressing walk through a corresponding second of the first segments and a second jump from an end of the second addressing walk through the second of the first segments to a start of a third addressing walk through a corresponding third of the first segments so as to thereby further define the input stream supplied to the data compression engine.

6. The reducing method of claim 5 wherein said supplying comprises:

(c.1) identifying within data words of the first data sequence addressed by said respective addressing walks, disruptive subsets of bits that reduce the predictive alikeness of the data sequences defined by the addressing walks; and

(c.2) stripping out the identified disruptive subsets of bits so as to produce the partially bit-stripped versions of the first data sequences as the input stream supplied to the data compression engine

and wherein said step (c) of consecutively supplying supplies to the compression engine, the bit-stripped versions of the first data sequences, stripped of their disruptive subsets of bits.

7. The reducing method of claim 5 wherein said supplying comprises:

(c.1) identifying within data words of the first data sequence addressed by said respective addressing walks, perfectly ordered subsets of bits that enhance the predictive alikeness of the data sequences defined by the addressing walks, but where the perfectly ordered subsets of bits do not need prediction because their bit patterns are 100% predictable during said respective addressing walks within their respective segments; and

(c.2) stripping out the identified perfectly ordered subsets of bits so as to produce the partially bit-stripped versions of the first data sequences as the input stream supplied to the data compression engine.

8. The reducing method of claim 1 and further comprising:

(f) identifying within the first digital data, one or more second data sequences that are mutually exclusive of the identified first data sequences and are predictively unalike relative to the identified first data sequences; and

(g) storing further data representing the one or more mutually exclusive second data sequences.

9. The reducing method of claim 8 wherein said stored further data is not compressed.

10. The reducing method of claim 1 wherein said first digital data is assigned by an operating system to a first account and where the first storage space contains second digital data assigned by the operating system to a different second account, the method further comprising:

(f) identifying within the second digital data, second data sequences that are not only predictively alike to one another or are overlappingly predictively alike but are also predictively alike to or are overlappingly predictively alike to the identified first data sequences of the first account, where the second data sequences are spaced apart address-wise in the first storage space from one another;

(g) physically or logically grouping the identified second data sequences with each other and with the first data sequences for consecutive presentation as part of an input data stream to the data compression engine;

(h) consecutively supplying partially bit-stripped versions or whole versions of the identified second data sequences to the data compression engine as part of the input data stream that includes the first data sequences and obtaining corresponding second compressed code from the compression engine;

(i) storing the second compressed code; and

(j) deleting from said first storage space the second data sequences that had been used to obtain said corresponding second compressed code from the compression engine.

11. The reducing method of claim 1 wherein said first storage space is located in a first storage drive a system and wherein the method also reduces storage size of second information represented initially by second digital data stored in second storage space located in a second storage drive of the system, said method further comprising:

(f) identifying within the second digital data, second data sequences that are not only predictively alike to one another or are overlappingly predictively alike but are also predictively alike to or are overlappingly predictively alike to the identified first data sequences of the first storage drive, where the second data sequences are spaced apart address-wise in the second storage space from one another;

(g) physically or logically grouping the identified second data sequences with each other and with the alike first data sequences for consecutive presentation as part of an input data stream to a second data compression engine;

(h) consecutively supplying partially bit-stripped versions or whole versions of the identified second data sequences to the second data compression engine as part of the input data stream that includes the first and second data sequences and obtaining corresponding second compressed code from the compression engine;

(i) storing the second compressed code;

(j) deleting from said second storage space the second data sequences that had been used to obtain said corresponding second compressed code from the compression engine; and

(k) migrating the second compressed code into concatenated storage near the first compressed code so as to thereby reduce amount of fragmented free space in the system.

12. The reducing method of claim 11 and furthering including emptying the first storage drive of user data and shutting power off to the first storage drive.

13. The reducing method of claim 1 wherein said first data sequences that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of graphic image data.

14. The reducing method of claim 1 wherein said first data sequences that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of text strings.

15. The reducing method of claim 1 wherein said first data sequences that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of data representing sampled waveforms.

16. The reducing method of claim 1 wherein said first data sequences that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of data representing samples of bandpass filtered audio waveforms.

17. The reducing method of claim 1 wherein said first data sequences -that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of discrete cosine transform (DCT) coefficients corresponding to a base harmonic.

18. The reducing method of claim 1 wherein said first data sequences that are identified as being predictively alike to one another or are overlappingly predictively alike consist essentially of discrete cosine transform (DCT) coefficients corresponding to a group of harmonics whose coefficients tend statistically to be of approximately same magnitudes.

19. The reducing method of claim 1 wherein said data compression engine includes an arithmetic encoder.

20. The reducing method of claim 1 wherein said first digital data is stored in a concatenation suitcase having a size greater than 10 times a predefined minimal file storage blocking size of the first storage space.

21. The reducing method of claim 1 wherein said first digital data is stored in a concatenation suitcase having a size of at least one megabytes.

22-25. -25. (canceled)

26-27. -27. (canceled)

28-60. -60. (canceled)

61-71. -71. (canceled)

72-78. -78. (canceled)

79-85. -85. (canceled)

86-87. -87. (canceled)

88. A machine-implemented method comprising:

(a) partitioning one or more files each into a plurality of substantially predictably consistent (SPC) fragments;

(b) physically or logically grouping compressibly alike ones of the fragments together into compressible subsets that each contain at least two of said compressibly alike fragments; and

(c) walking one or more times sequentially through the fragments of at least one of the compressible subsets while compressing-wise encoding subset data encountered along the one or more sequential walks through that subset.

89. The method of claim 88 wherein:

(a.1) said partitioning includes separating text-containing fragments from graphics containing fragments.

90. The method of claim 88 wherein:

(a.1) said partitioning includes parsing a file to identify semantically distinct sections of the file.

91. The method of claim 88 wherein:

(a.1) said partitioning includes parsing a file to identify compressibly unalike sections of the file.

92. The method of claim 88 wherein:

(b.1) said physical grouping of the alike file fragments includes packing the fragments tightly into a concatenation suitcase of predefined size.

93. The method of claim 88 wherein:

(b.1) said logical linking of the alike file fragments includes defining a walk-and-jump path for a compression engine to follow through inside the alike file fragments and/or to jump along when switching between the alike file fragments and when encoding data of the alike file fragments.

94. The method of claim 88 wherein:

(c.1) said walking includes at least first and second walks that each sequentially progresses through a first relatively forward fragment of a walked-through at least one compressible subset and through a second relatively rearward fragment of the at least one compressible subset, where said first and second walks respectively cover mutually exclusive first and second areas of the walked-through subset.

95. The method of claim 88 wherein:

(c.1) said walking through includes generating separation indicators indicating where encoding for a first of the encoded fragments ends and encoding for a next of the encoded fragments, if any, begins.

96. The method of claim 88 and further comprising:

(d) prior to said one or more sequential walks through that subset, defining a sequence of the alike fragments in at least one subset, where the defined sequence is subsequently adhered to by said one or more sequential walks through that at least one subset of file fragments.

97. The method of claim 96 wherein:

(d.1) said defining of the sequence is structured for progressively smooth evolution of a progressively adaptive compression that is to be carried out by said compressing-wise encoding of the subset data encountered along the one or more sequential walks.

98. The method of claim 96 wherein:

(d.1) said defining of the sequence is structured to reduce decompaction latency for fragments of files that are expected to be more frequently accessed, where said decompression latency includes time for performing said one or more sequential walks into the subset at least to a depth needed for decompressing the encoded fragments of a desired file.

99. A machine-implemented method comprising:

(a) identifying among a plurality of files that are not all directly logically linked one to the other, compressibly alike ones of the files;

(b) physically or logically grouping the compressibly alike ones of the identified files into compressible subsets that each contain at least two of said files; and

(c) walking one or more times sequentially through the files of at least one of the compressible subsets while compressing-wise encoding subset data encountered along the one or more sequential walks through that subset.

100. A machine-implemented method of reconstituting desired data from compressed content, the method comprising:

(a) intercepting a first referencing signal that references desired file data that no longer resides at a first file storage location represented by the first referencing signal;

(b) substituting for the first referencing signal, a second referencing signal that references a concatenation suitcase holding not only an extractable version of the desired file data or of at least a portion of the desired file data in deflated or inflated form, but also holding other extractable versions of data of other files, where the second referencing signal indicates a location in the deflated concatenation suitcase where the extractable version of the desired file data or portion thereof resides.

101. The method of claim 100 and further comprising:

(c) partially deflating a copy of the concatenation suitcase referenced by said second referencing signal.

102. The method of claim 101 wherein:

(c.1) said partial deflating of the copied concatenation suitcase is carried out on a limited run length basis to an extent needed for deflating up to and including the extractable version of the desired data.

103. The method of claim 101 and further comprising:

(d) applying an inverse transform to the deflated extractable version of the desired data that was obtained by partial deflating of the concatenation suitcase copy, where the inverse transform includes at least one of;

(d.1) a predefined symbol re-sequencing operation; and

(d.2) a predefined bit-masking operation.

104. The method of claim 103 wherein said symbol re-sequencing operation includes:

(d.1a) jumping from one segmented memory area to a next in accordance with a supplied linked list.

105. The method of claim 103 wherein said symbol re-sequencing operation includes:

(d.1a) performing an in-segment addressing walk within a segmented memory area in accordance with a supplied walk definition.

106. The method of claim 100 and further comprising:

(a.1) forming a hash of the first referencing signal.

107. (canceled)

108-115. -115. (canceled)