Coding network grouping data of same data type into blocks using file data structure and selecting compression for individual block base on block data type

• US 6,253,264 B1
• Filed: 03/06/1998
• Issued: 06/26/2001
• Est. Priority Date: 03/07/1997
• Status: Expired due to Term

• Current Assignee: ViaSat Incorporated
• Original Assignee: Intelligent Compression Technologies, Inc. (ViaSat Incorporated)
• Inventors: Sebastian, William
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): NGUYEN, TANH Q
• Application Number:
  US09/036,052
• Time in Patent Office: 1,208 Days
• Field of Search: 341/51, 341/65, 341/107, 707/102, 707/503, 707/504, 707/505, 707/508, 370/474, 710/65, 710/68
• US Class Current: 710/68
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

A preferred coding network uses an architecture called a Base-Filter-Resource (BFR) system. This approach integrates the advantages of format-specific compression into a general-purpose compression tool serving a wide range of data formats. Source data is parsed into blocks of similar data and each parsed blocks are compressed using a respectively selected compression algorithm. The algorithm can be chosen from a static model of the data or can be adaptive to the data in the parsed block. The parsed blocks are then combined into an encoded data file. For decoding, the process is reversed.

Claims

1. A computerized method of coding data having a plurality of data components, each data component structured into a data field of an associated data type according to an organized file format, comprising:

from a source data structure of an organized file format, creating a plurality of blocks based on the source data structure, each block associated with a specific respective data field;

parsing each data component from the source data structure into one of the plurality of blocks based on the data field of the data component;

for each block;

selecting a compression algorithm from a plurality of candidate compression algorithms based on the data type of the data field associated with the block;

applying the selected compression algorithm to compress each data component in the block; and

combining the compressed data components from the plurality of blocks into an encoded data structure.

2. The method of claim 1 wherein the source data structure is organized in a first format and parsing comprises converting the source data structure into a second format.

3. The method of claim 2 wherein converting comprises collecting similar data from the source data structure into respective blocks.

4. The method of claim 2 wherein converting comprises forming a compression model based on the first format.

5. The method of claim 1 wherein the compression algorithms are further determined based on the amount of data in the respective block.

6. The method of claim 1 wherein a compression algorithm is adapted to the respective block.

7. The method of claim 1 wherein selecting comprises forming a customized transform.

8. The method of claim 1 further comprising recovering the source data structure from the encoded data structure.

21. The method of claim 1 wherein the organized file format includes defined data types.

22. The method of claim 21 wherein each data type is determined by the type of structure in which the block appears and the position of the block within the structure.

23. The method of claim 7 further comprises transforming a block based on relationships between data components associated with the block.

9. An article of manufacture, comprising:

a machine-readable medium;

a set of instructions recorded in the machine-readable medium to implement a data coding network having a plurality of data components, each data component structured into a data field of a respective data type according to an organized file format, comprising;

from a source data structure of an organized file format, creating a plurality of blocks based on the source data structure format, each block associated with a specific respective data field;

parsing each data component from the source data structure into one of the plurality of blocks based on the data field of the data component;

for each block;

selecting a compression algorithm from a plurality of candidate compression algorithms based on the data type of the data field associated with the block;

applying the selected compression algorithm to compress each data component in the block; and

combining the compressed data components from the plurality of blocks into an encoded data structure.

10. The article of claim 9 wherein the source data structure is organized in a first format and parsing comprises converting the source data structure into a second format.

11. The article of claim 10 wherein converting comprises collecting similar data from the source data structure into respective blocks.

12. The article of claim 10 wherein converting comprises forming a compression model based on the first format.

13. The article of claim 9 wherein the compression algorithms are further determined based on the amount of data in the respective block.

14. The article of claim 9 wherein a compression algorithm is adapted to the respective block.

15. The article of claim 9 wherein selecting comprises forming a customized transform.

16. The article of claim 9 further comprising recovering the source data structure from the encoded data structure.

24. The article of claim 9 wherein the organized file format includes defined data types.

25. The article of claim 24 wherein each data type is determined by the type of structure in which the block appears and the position of the block within the structure.

26. The article of claim 15 further comprises transforming a block based on relationships between data components associated with the block.

17. An apparatus to code data having a plurality of data components, each data component structured into a data field of a respective data type according to an organized file format, comprising:

a plurality of blocks based on and derived from a source data structure of an organized file format, each block associated with a specific respective data field;

a parser to parse each data component from the source data structure into one of the plurality of blocks based on the data field of the data component;

a selection system for selecting a compression algorithm for a block from a plurality of candidate compression algorithms based on the data type of the data field associated with the block;

a coder for applying the selected compression algorithm to compress each data component in the block and for combining the compressed data components from the plurality of blocks into an encoded data structure.

18. The apparatus of claim 17 wherein the parser groups like data from the source data structure into respective blocks.

19. The apparatus of claim 17 wherein the selection system is adaptive to the data in the block.

20. The apparatus of claim 17 further comprising a recovery system for recovering the source data structure from the encoded data structure.

27. The apparatus of claim 17 wherein the organized file format includes defined data types.

28. The apparatus of claim 27 wherein each data type is determined by the type of structure in which the block appears and the position of the block within the structure.

29. The apparatus of claim 17 further comprising a transformer to transform a block based on relationships between data components associated with the block.