Data Compression Systems and Methods

• US 20110037626A1
• Filed: 02/09/2010
• Published: 02/17/2011
• Est. Priority Date: 12/11/1998
• Status: Active Grant

• Current Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Original Assignee: Realtime Data LLC (Realtime Data Compression Systems, Inc.)
• Inventors: Fallon, James J.
• Granted Patent: US 8,502,707 B2
• Time in Patent Office: Days
• US Class Current: 341/87
• 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/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/3059 Digital compression and data reduction techniques where the original information is represented by a subset or similar information, e.g. lossy compression
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/4006 Conversion to or from arithmetic code
• CPC Class Codes: H04L 65/70 Media network packetisation

Abstract

Systems and methods for providing fast and efficient data compression using a combination of content independent data compression and content dependent data compression. In one aspect, a method for compressing data comprises the steps of: analyzing a data block of an input data stream to identify a data type of the data block, the input data stream comprising a plurality of disparate data types; performing content dependent data compression on the data block, if the data type of the data block is identified; performing content independent data compression on the data block, if the data type of the data block is not identified.

Claims

1. A method comprising:

receiving a data block in a received form;

performing a first compression technique comprising;

compressing said data block in received form with a first encoder to provide a first compressed data block, and

compressing said first compressed data block with a second encoder to provide a second compressed data block;

comparing said second compressed data block against a threshold, wherein said threshold is indicative of data expansion; and

providing said second compressed data block to a device, if no data expansion is determined to have occurred based on said comparing.

2. The method of claim 1, further comprising measuring the time associated with said first compression technique.

3. The method of claim 1, further comprising:

measuring the time associated with said first compression technique; and

comparing said measured time against a time threshold, wherein said providing said second compressed data block is performed if said measured time is less than said time threshold.

4. The method of claim 1, wherein said first compression technique provides lossless compression.

5. The method of claim 1, further comprising providing a descriptor to said device, wherein said descriptor is indicative of said first compression technique.

6. The method of claim 1, wherein said providing comprises storing.

7. The method of claim 1, wherein said providing comprises transmitting.

8. The method of claim 1, further comprising compressing said data block in received form with a second compression technique.

9. The method of claim 1, further comprising:

compressing said data block in received form with a second compression technique to provide a third compressed data block; and

determining whether to provide to said device said third compressed data block from said second compression technique or said second compressed data block from said first compression technique and determining to provide said second data block from said first compression technique.

10. The method of claim 1, further comprising providing said data block in received form with a null descriptor indicative of no compression, wherein data expansion is determined to have occurred based on said comparing.

11. The method of claim 1, further comprising receiving a second data block and compressing said second data block with said first compression technique.

12. The method of claim 1, further comprising comparing said first compression technique against a desirability factor.

13. The method of claim 1, further comprising comparing said first compression technique against a user-defined desirability factor.

14. The method of claim 1, further comprising decompressing said second compressed data block.

15. The method of claim 1, further comprising:

providing a descriptor to said device, wherein said descriptor is indicative of said first compression technique; and

decompressing said second compressed data block based on said descriptor.

16. A method comprising:

receiving a data block;

outputting data, wherein said outputted data is determined to be;

said data block in received form, or

a compressed data block wherein said compressed data block is provided by one of a plurality of compression techniques based on a determination between said plurality of compression techniques, and a determination is made whether data expansion occurred with respect to said compressed data block; and

outputting a descriptor with said outputted data indicative of no compression or the one of said plurality of compression techniques utilized to provide said compressed data block.

17. A method comprising:

associating at least one encoder of a plurality of encoders to each one of a plurality of data types;

determining a data type of a data block, wherein said data block is provided as part of a data stream;

if said determined data type is associated with at least one of said plurality of encoders, compressing said data block with said at least one associated encoder to provide a compressed data block;

determining whether said compressed data block is indicative of data expansion; and

outputting a descriptor with said compressed data block that is indicative of how said compressed data block was compressed.

18. The method of claim 17, further comprising selecting resolution parameters for at least one of said at least one associated encoder.

19. The method of claim 17, further comprising selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution.

20. The method of claim 17, further comprising selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution and said selected resolution is indicative of lossy compression.

21. The method of claim 17, further comprising determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream.

22. The method of claim 17, further comprising:

determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream; and

compressing said second data block with at least one second encoder.

23. The method of claim 17, wherein said at least one associated encoder is lossless.

24. The method of claim 17, wherein said at least one associated encoder is lossy.

25. The method of claim 17, wherein said at least one associated encoder comprises a plurality of associated encoders.

26. The method of claim 17, wherein said data block is a fixed-size data block.

27. The method of claim 17, wherein said data block is a variable-size data block.

28. The method of claim 17, wherein said at least one associated encoder is lossy or lossless dependent on said data type.

29. The method of claim 17, further comprising transmitting said compressed data block.

30. The method of claim 17, further comprising:

transmitting said compressed data block; and

decompressing said compressed data block based on said descriptor.

31. The method of claim 17, wherein said at least one associated encoder comprises a Huffman encoder.

32. The method of claim 17, wherein said at least one associated encoder comprises a Lempel-Ziv encoder.

33. The method of claim 17, wherein said at least one associated encoder comprises a run length encoder.

34. The method of claim 17, wherein said at least one associated encoder comprises an arithmetic encoder.

35. The method of claim 17, wherein said at least one associated encoder comprises a plurality of encoders that operate in parallel.

36. The method of claim 17, wherein said at least one associated encoder comprises a plurality of encoders that operate sequentially.

37. A method comprising:

associating at least one encoder of a plurality of encoders to each one of a plurality of data types;

determining a data type of a data block, wherein said data block is provided as part of a data stream;

if said determined data type is associated with at least one of said plurality of encoders, compressing said data block with said at least one associated encoder to provide a compressed data block;

determining whether said compressed data block is representative of a data compression ratio above a threshold and, if said determination is above said threshold, outputting said compressed data block; and

outputting a descriptor that is indicative of how said compressed data block was compressed.

38. The method of claim 37, further comprising selecting resolution parameters for at least one of said at least one associated encoder.

39. The method of claim 37, further comprising selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution.

40. The method of claim 37, further comprising selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution and said selected resolution is indicative of lossy compression.

41. The method of claim 37, further comprising determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream.

42. The method of claim 37, further comprising:

determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream; and

compressing said second data block with at least one second encoder.

43. The method of claim 37, wherein said at least one associated encoder is lossless.

44. The method of claim 37, wherein said at least one associated encoder is lossy.

45. The method of claim 37, wherein said at least one associated encoder comprises a plurality of associated encoders.

46. The method of claim 37, wherein said data block is a fixed-size data block.

47. The method of claim 37, wherein said data block is a variable-size data block.

48. The method of claim 37, wherein said at least one associated encoder is lossy or lossless dependent on said data type.

49. The method of claim 37, further comprising transmitting said compressed data block.

50. The method of claim 37, further comprising:

transmitting said compressed data block; and

decompressing said compressed data block based on said descriptor.

51. The method of claim 37, wherein said at least one associated encoder comprises a Huffman encoder.

52. The method of claim 37, wherein said at least one associated encoder comprises a Lempel-Ziv encoder.

53. The method of claim 37, wherein said at least one associated encoder comprises a run length encoder.

54. The method of claim 37, wherein said at least one associated encoder comprises an arithmetic encoder.

55. The method of claim 37, wherein said at least one associated encoder comprises a plurality of encoders that operate in parallel.

56. The method of claim 37, wherein said at least one associated encoder comprises a plurality of encoders that operate sequentially.

57. A machine-readable storage medium encoded with machine executable instructions for performing the method comprising:

associating at least one encoder of a plurality of encoders to each one of a plurality of data types;

determining a data type of a data block, wherein said data block is provided as part of a data stream;

if said determined data type is associated with at least one of said plurality of encoders, compressing said data block with said at least one associated encoder to provide a compressed data block;

determining whether said compressed data block is indicative of data expansion; and

outputting a descriptor with said compressed data block that is indicative of how said compressed data block was compressed.

58. The machine-readable storage medium of claim 57, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder.

59. The machine-readable storage medium of claim 57, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution.

60. The machine-readable storage medium of claim 57, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution and said selected resolution is indicative of lossy compression.

61. The machine-readable storage medium of claim 57, further comprising instructions for determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream.

62. The machine-readable storage medium of claim 57, further comprising instructions for:

determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream; and

compressing said second data block with at least one second encoder.

63. The machine-readable storage medium of claim 57, wherein said at least one associated encoder is lossless.

64. The machine-readable storage medium of claim 57, wherein said at least one associated encoder is lossy.

65. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a plurality of associated encoders.

66. The machine-readable storage medium of claim 57, wherein said data block is a fixed-size data block.

67. The machine-readable storage medium of claim 57, wherein said data block is a variable-size data block.

68. The machine-readable storage medium of claim 57, wherein said at least one associated encoder is lossy or lossless dependent on said data type.

69. The machine-readable storage medium of claim 57, further comprising instructions for transmitting said compressed data block.

70. The machine-readable storage medium of claim 57, further comprising instructions for:

transmitting said compressed data block; and

decompressing said compressed data block based on said descriptor.

71. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a Huffman encoder.

72. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a Lempel-Ziv encoder.

73. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a run length encoder.

74. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises an arithmetic encoder.

75. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a plurality of encoders that operate in parallel.

76. The machine-readable storage medium of claim 57, wherein said at least one associated encoder comprises a plurality of encoders that operate sequentially.

77. A machine-readable storage medium encoded with machine executable instructions for performing the method comprising:

associating at least one encoder of a plurality of encoders to each one of a plurality of data types;

determining a data type of a data block, wherein said data block is provided as part of a data stream;

if said determined data type is associated with at least one of said plurality of encoders, compressing said data block with said at least one associated encoder to provide a compressed data block;

determining whether said compressed data block is representative of a data compression ratio above a threshold and, if said determination is above said threshold, outputting said compressed data block; and

outputting a descriptor that is indicative of how said compressed data block was compressed.

78. The machine-readable storage medium of claim 77, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder.

79. The machine-readable storage medium of claim 77, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution.

80. The machine-readable storage medium of claim 77, further comprising instructions for selecting resolution parameters for at least one of said at least one associated encoder, wherein said compressing with said at least one of said at least one associated encoders is performed at said selected resolution and said selected resolution is indicative of lossy compression.

81. The machine-readable storage medium of claim 77, further comprising instructions for determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream.

82. The machine-readable storage medium of claim 77, further comprising instructions for:

determining that no data type is associated with a second data block, wherein said second data block is provided as part of said data stream; and

compressing said second data block with at least one second encoder.

83. The machine-readable storage medium of claim 77, wherein said at least one associated encoder is lossless.

84. The machine-readable storage medium of claim 77, wherein said at least one associated encoder is lossy.

85. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a plurality of associated encoders.

86. The machine-readable storage medium of claim 77, wherein said data block is a fixed-size data block.

87. The machine-readable storage medium of claim 77, wherein said data block is a variable-size data block.

88. The machine-readable storage medium of claim 77, wherein said at least one associated encoder is lossy or lossless dependent on said data type.

89. The machine-readable storage medium of claim 77, further comprising instructions for transmitting said compressed data block.

90. The machine-readable storage medium of claim 77, further comprising instructions for:

transmitting said compressed data block; and

decompressing said compressed data block based on said descriptor.

91. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a Huffman encoder.

92. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a Lempel-Ziv encoder.

93. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a run length encoder.

94. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises an arithmetic encoder.

95. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a plurality of encoders that operate in parallel.

96. The machine-readable storage medium of claim 77, wherein said at least one associated encoder comprises a plurality of encoders that operate sequentially.