Methods and apparatus for reducing storage size

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.

1. A method of compressing digital symbols stored in an electronic memory over an address space, comprising:
 dividing at least a portion of the address space into segments, each address space segment identifying a corresponding subset of the symbols stored over the entire address space, wherein for each segment, a statistical distribution of the corresponding subset of symbols is less random as compared to a statistical distribution for that subset of symbols over the remaining address space segments; 
 ordering the segments according to their predictive similarity to provide a coding order; 
 according to the coding order, successively retrieving the subset of symbols corresponding to each segment from the memory; and 
 predictive encoding the successively retrieved subset of symbols into encoded symbols. 
 
     
     
       2. The method of  claim 1 , wherein the predictive encoding is an arithmetic encoder. 
     
     
       3. The method of  claim 1 , wherein the predictive encoding is a predictive entropy encoding. 
     
     
       4. The method of  claim 1 , wherein the digital symbols correspond to a digital image. 
     
     
       5. The method of  claim 1 , further comprising: repeating the dividing, ordering, retrieving, and encoding steps to determine that division and ordering that produces a most efficient encoding.