Methods and apparatus for reducing storage size

• US 7,936,932 B2
• Filed: 07/06/2007
• Issued: 05/03/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,297
• Publication Number:
  US 20080050026A1
• Time in Patent Office: 1,397 Days
• Field of Search: 382/125, 382/204, 382/224, 382/232, 382/233, 382/243, 382/238, 341/51, 341/90, 324/88, 345/24, 345/26, 707/999.101
• US Class Current: 382/232
• 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 machine-implemented data compaction/decompaction method comprising:

identifying one or more times of expected slack in user initiated demand for a finite data throughput rate capability of a storage drive;

within a computer associated with the storage drive, during one or more of the identified slack times, automatically fetching one or more files stored on the storage drive, the one or more files comprising a set of digital symbols;

within the computer, dividing at least a portion of the fetched one or more files into segments, each segment identifying a corresponding subset of the digital symbols;

within the computer, ordering the segments according to their predictive similarity to provide a coding order; and

within the computer, predictive encoding the ordered segments 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, and encoding steps to determine a division and ordering that produces a most efficient encoding.

6. The method of claim 1, wherein for each segment, a statistical distribution of the corresponding subset of symbols is less random as compared to a statistical distribution for the set of digital symbols.