Methods and apparatus for reducing storage size

• US 7,881,544 B2
• Filed: 07/06/2007
• Issued: 02/01/2011
• Est. Priority Date: 08/24/2006
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Dell Products LP (Dell Technologies Inc.)
• Inventors: Brueggemann, Eric, Rao, Goutham, George, Carter, Bashyam, Murali
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US11/774,278
• Publication Number:
  US 20080050047A1
• Time in Patent Office: 1,306 Days
• Field of Search: 382/232, 382/233, 382/236, 382/238, 382/239, 382/224, 382/243, 382/305, 341/51, 341/107, 345/473, 345/422, 345/418, 345/426, 707/999.101, 707/E17.002, 1/1
• US Class Current: 382/232
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

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 mechanism for reducing storage size needed for information represented by input data present in a randomly accessible memory window, the mechanism comprising:

(a) a prediction-based entropy encoder operatively coupled to receive an input data stream sourced from the memory window;

(b) a walk generator operatively coupled to the memory window for defining a sequence of address signals supplied to the memory window;

(c) a compression efficiency evaluator operatively coupled to measure a length of encoded output produced by the entropy encoder in response to an input data stream received from the memory window for a given sequence of address signals defined by said walk generator and operatively coupled to measure a length of input data stream supplied to the entropy encoder in response to the given sequence of address signals;

the compression efficiency evaluator calculating a corresponding compression efficiency value as a function of said measured lengths of encoded output and length of input data stream; and

(d) a walk modifier operatively coupled to the compression efficiency evaluator and to the walk generator and structured to supply two or more different walk definitions to the walk generator and structured to determine, by trial and error operation of the walk generator and of the encoder, which of the two or more walk definitions causes the compression efficiency evaluator to calculate a superior compression efficiency value.

2. The storage size reducing mechanism of claim 1 wherein:

(c.1) said length of encoded output is measured so as to indicate number of bits of encoded output.

3. The storage size reducing mechanism of claim 1 wherein:

(c.1) said length of encoded output is measured so as to indicate number of storage words consumed by the encoded output.

4. The storage size reducing mechanism of claim 1 wherein:

(c.1) said length of input data stream is measured so as to indicate number of bits of plaintext input.

5. The storage size reducing mechanism of claim 1 wherein:

(c.1) said length of input data stream is measured so as to indicate number of symbol of plaintext input where the symbols are those of a predefined alphabet.

6. The storage size reducing mechanism of claim 1 wherein:

(c.1) said length of input data stream is measured so as to indicate number of storage words consumed by the input data stream.

7. The storage size reducing mechanism of claim 1 and further comprising:

(e) a walk definition storage for storing at least a walk definition that has been determined to be a currently used one, the walk definition storage being operatively coupled to the walk generator for causing the walk generator to trace along one or more walk definitions stored therein.

8. The storage size reducing mechanism of claim 7 and further comprising:

(f) a variable bit sampler operatively coupled to the memory window for defining subsets of bits to be optionally excluded from the input data stream received by the entropy encoder.

9. The storage size reducing mechanism of claim 1 wherein:

(a.1) the prediction-based entropy encoder includes an adaptive predictor that maintains a variable prediction model corresponding to a history of received data received in the input data stream, where the predictor outputs a forecast upon which the encoder relies when performing its encoding operations; and

(b.1) the walk generator is structured to cause sequences of address signals to be supplied to the memory window so that sequentially efficiently compressible (SEC) data sequences will be supplied to the entropy encoder as the input data stream received from the memory window.

10. The storage size reducing mechanism of claim 9 wherein:

(b.2) the walk generator is structured to generate U-turning address walks within predefined segment areas of the memory window.

11. The storage size reducing mechanism of claim 10 wherein:

(b.3) the U-turning address walks are major walks that step from one predefined memory tile area to a next adjacent memory tile area; and

(b.4) the walk generator is structured to generate in-tile minor address walks within the memory tile areas where each in-tile minor address walk steps from a first subarea of its respective tile area to a touching next subarea of the respective tile area.

12. The storage size reducing mechanism of claim 11 wherein:

(b.5) the walk generator is structured to generate different in-tile minor address walks depending on direction of stepping of the major walk from one predefined memory tile area to the next.

13. The storage size reducing mechanism of claim 12 wherein:

(a.2) the adaptive predictor is responsive at least to the direction of the current major walk when generating a current probabilities forecast for use by the encoder.

14. The storage size reducing mechanism of claim 4 wherein:

(b.1) the walk generator is structured to generate jumping address walks between spaced apart ones of predefined segment areas of the memory window.

15. The storage size reducing mechanism of claim 1 and further comprising:

(e) a pre-compression data definer operatively coupled to the memory window for defining data contained in the memory window prior to a supplying of a given input data stream from the memory window and towards the entropy encoder.

16. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes packing into the memory window fragments from different files where the packed in file fragments are perfectly-alike and/or are predictively alike with respect to one another.

17. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes packing into the memory window different files where the packed in files are perfectly-alike and/or are predictively alike with respect to one another.

18. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes packing into the memory window fragments from different files where the packed in file fragments are sequenced so as to be progressively-alike with respect to one another.

19. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes packing into the memory window different files where the packed in files are sequenced by the pre-compression data definer so as to be progressively-alike with respect to one another.

20. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes causing a first intercept vector to point to data placed within the memory window.

21. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes fixing predefined insignificant bits within data words of the memory window to zero or another predefined pattern.

22. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes subtracting a predefined DC bias from data words of the memory window that belong to one or more segments identified for such removal of a DC bias.

23. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes subtracting a predefined perfectly-ordered sequence from a corresponding sequence of data words of the memory window that belong to one or more segments identified for such removal of a perfectly-ordered sequence.

24. The storage size reducing mechanism of claim 15 wherein:

(e.1) said defining of data contained in the memory window prior to a supplying includes replacing data values found in one or more identified segments of the memory window with index values obtained from a predefined substitution table where said one or more identified segments are pre-identified for such value substitution.

25. The storage size reducing mechanism of claim 1 wherein:

(d.1) said walk modifier is configured to automatically smooth out boundaries of initially defined segment areas that respectively identify groups of data sequence segments within the memory window.

26. The storage size reducing mechanism of claim 25 wherein:

(d.1a) said automatic smooth out produces boundary definitions that are expressible as one or more linear equations.

27. The storage size reducing mechanism of claim 25 wherein:

(d.1a) said automatic smooth out produces boundary definitions that are expressible as one or more Bezier curves.

28. The storage size reducing mechanism of claim 25 wherein:

(d.2) after said automatic smooth out, the walk modifier submits the corresponding modified walk definition to the walk generator and the walk modifier determines by trial and error operation of the walk generator and of the encoder with use of the modified walk definition, whether the modified walk definition reduces compression efficiency by more than a predefined percentage or amount relative to a compression efficiency earlier calculated by the compression efficiency evaluator for a predefined pre-modification walk.

29. The storage size reducing mechanism of claim 1 wherein:

(a.1) said entropy encoder includes an arithmetic encoder.

30. The storage size reducing mechanism of claim 1 wherein:

(a.1) said entropy encoder implements a Burrows-Wheeler Transform (BWT).

31. The storage size reducing mechanism of claim 1 wherein:

(a.1) said entropy encoder implements a Move To Front process.

32. The storage size reducing mechanism of claim 1 wherein:

(a.1) said entropy encoder includes a Run Length encoder.

33. The storage size reducing mechanism of claim 1 wherein:

(a.1) said entropy encoder includes a Huffman encoder.