Methods and apparatus for reducing storage size
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.
1. A method of reducing storage size of information represented initially by first digital data stored in a first storage space within a first memory, the method including machine-implemented steps comprising:
retrieving the first digital data from the first memory;
(a) within a processor associated with the first memory, identifying within the first digital data, first data sequences that are predictively alike to one another, where the first data sequences are spaced apart storage address-wise in the first storage space from one another;
(b) within the processor, physically or logically grouping the identified first data sequences for consecutive presentation as part of an input data stream to a data compression engine implemented by the processor 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 implemented by the processor and obtaining corresponding first compressed code from the compression engine;
(d) storing the first compressed code in a second memory; 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 statistics 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. The reducing method of claim 1 , wherein the first and second memories comprise a single memory.
23. The reducing method of claim 1 , wherein the first and second memories comprise separate memories.