Method and system for value-based data compression

• US 7,079,053 B2
• Filed: 11/29/2004
• Issued: 07/18/2006
• Est. Priority Date: 11/29/2004
• Status: Expired due to Fees

• Current Assignee: Honeywell International Inc.
• Original Assignee: Honeywell International Inc.
• Inventors: Kolavi, Shashi Kumar M
• Primary Examiner(s): JeanPierre, Peguy
• Assistant Examiner(s): NGUYEN, KHAI M
• Application Number:
  US10/999,098
• Publication Number:
  US 20060114131A1
• Time in Patent Office: 596 Days
• Field of Search: 341/65, 341/67, 341/87, 341/95
• US Class Current: 341/67
• 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

Abstract

Data in a data structure is compressed by exploiting prior knowledge of the format of the data structure. A portion of the data structure is captured. A metadata component is selected for the portion. A data buffer is updated by using the selected metadata component and the captured portion. This compression technique achieves real-time data compression suitable for use with data structures used for the synchronization of the state of communication entities. The compression technique reduces the volume of data to be communicated for the synchronization of the state of communication entities and, therefore, provides faster synchronization. The present technique is suitable for use in redundant systems.

Claims

1. A method of communicating data structures among communication entities of a data communication system, the data structures comprising at least one data element, the method comprising:

capturing a current value of the data element pertaining to at least a portion thereof;

encoding the data element by selecting a metadata component characterizing the data element to enable data compression;

updating a data buffer using the metadata component and the portion;

repeating the capturing, the encoding, and the updating for all of the data elements in the data structure;

communicating the data buffer to at least one receiving communication entity in the data communication system;

analyzing the metadata component associated with an encoded data element in the data buffer to obtain a size of the portion;

extracting the portion from the data buffer using the size;

reconstructing the data element from the portion by matching the size of the portion of the data element to the size of the data element; and

,

repeating the analyzing, the extracting and the reconstructing for all of the encoded data elements in the data buffer.

2. The method according to claim 1, wherein the capturing comprises using all bits from the most significant non-zero bit of the data element to the least significant bit of the data element as the portion and discarding one or more pairs of adjacent zero bits, if any, in bit positions that are more significant than the most significant non-zero bit of the data element.

3. The method according to claim 1, wherein the selecting of the metadata component characterizing the data element comprises:

selecting the size of the metadata component based on the metadata component associated with a data type of the data element; and

,

evaluating the value of the metadata component based on the current value of the data element.

4. The method according to claim 3, wherein the evaluating value of the metadata component comprises:

identifying a range of data element values from a predefined set of ranges of data element values pertaining to the data type of the data element, wherein the current value of the data element lies within the range; and

,

selecting a predefined metadata value associated with the identified range as the metadata component value.

5. The method according to claim 3, wherein the data type of each data element in the data structure is known to at least the receiving communication entity prior to the method execution.

6. The method according to claim 3, wherein the data type of each data element in the data structure is communicated to at least the receiving communication entity by another communication entity prior to the method execution.

7. The method according to claim 3, wherein the size of the metadata component for a data element of data type BOOLEAN, SHORT INTEGER, INTEGER, LONG INTEGER or DOUBLE is selected from a group consisting of zero bits, two bits, three bits, and four bits.

8. The method according to claim 1 wherein the updating of the data buffer comprises concatenating the metadata component and the portion to the data buffer.

9. The method according to claim 1, wherein the reconstructing comprises prefixing zeros to the portion to match the size thereof to the size of the data element.

10. The method according to claim 1, wherein the receiving communication entity comprises a redundant server.

11. The method according to claim 1, wherein the data communication system comprises a redundant system.

12. The method according to claim 1, wherein the metadata component indicates the size of the portion.

13. A method of compressing a data structure comprising at least one data element to obtain a data buffer representing the data structure, the method comprising:

capturing a current value of the data element pertaining to at least a portion thereof;

encoding the data element by selecting a metadata component characterizing the data element to enable data compression;

updating the data buffer using the metadata component and the portion; and

,

repeating the capturing, the encoding and the updating for all of the data elements in the data structure.

14. The method according to claim 13, wherein the metadata component indicates the size of the portion.

15. The method according to claim 13, wherein the capturing comprises using all bits from the most significant non-zero bit of the data element to the least significant bit of the data element as the portion and discarding one or more pairs of adjacent zero bits, if any, in bit positions that are more significant than the most significant non-zero bit of the data element.

16. The method according to claim 13, wherein the selecting of the metadata component using a data element comprises:

selecting a size of the metadata component based on the metadata component associated with the data type of the data element; and

,

evaluating the value of the metadata component based on the current value of the data element.

17. The method according to claim 16, wherein the evaluating of the value of the metadata component comprises:

identifying a range of data element values from a predefined set of ranges of data element values pertaining to a data type of the data element, wherein the current value of the data element lies within the range; and

,

selecting a predefined metadata value associated with the identified range as the metadata component value.

18. A method of decompressing a data buffer representing a data structure to obtain the data structure, the data buffer comprising at least one encoded data element, each encoded data element representing a data element of the data structure, the method comprising:

analyzing a metadata component associated with an encoded data element in the data buffer to obtain a size of a portion of the data element represented by the encoded data element;

extracting the portion from the data buffer by using the size;

reconstructing the data element from the portion by matching the size of the extracted portion of the data element to the size of the data element; and

,

repeating the analyzing, the extracting and the reconstructing for all of the encoded data elements in the data buffer.

19. A method of communicating data structures in a compressed format for synchronization of the state of communication entities in a data communication system, the data structures comprising at least one data element, the method comprising:

capturing a current value of the data element by discarding one or more pairs of adjacent zero bits, if any, that occupy bit positions more significant than the most significant non-zero bit of the data element and by retaining the remaining bits of the data element to obtain a portion;

selecting a size of a metadata component based on the metadata component associated with a data type of the data element;

identifying a range of data element values from a predefined set of ranges of data element values pertaining to the data type of the data element, wherein the current value of the data element lies within the range;

selecting a predefined metadata value associated with the identified range as the metadata component value;

concatenating the metadata component and the portion to the data buffer;

repeating the capturing, the selecting, the identifying, the selecting, and the concatenating for all of the data elements in the data structure;

communicating the data buffer to at least one receiving communication entity in the data communication system;

analyzing the metadata component associated with an encoded data element in the data buffer to obtain a size of the portion;

extracting the portion from the data buffer using the size of the portion;

prefixing zeros to the portion to match a size thereof to the size of the data element;

repeating the analyzing, the extracting, and the prefixing for all of the data elements in the data buffer to reproduce a data structure; and

,

synchronizing the state of the receiving communication entity to the state of a communication entity that communicated the data buffer based on the reproduced data structure.

20. A system for communicating data structures in a compressed format for synchronization of the state of communication entities in a data communication system, the data structures comprising at least one data element, the system comprising:

a current value capturing block that captures a current value of the data element pertaining to at least one portion thereof, wherein the current value capturing block is adapted to reside in at least one communication entity;

an encoding block that encodes the data element by selecting a metadata component characterizing the data element to enable data compression, wherein the encoding block is adapted to reside in at least one communication entity;

a data buffer updating block that updates a data buffer using the metadata component and the portion, wherein the data buffer updating block is adapted to reside in at least one communication entity;

a communicating block that communicates the data buffer to at least one communication entity in the data communication system, wherein the communicating block is adapted to reside in at least one communication entity;

a metadata component analyzing block that analyzes the metadata component associated with an encoded data element in the data buffer to obtain a size of the portion, wherein the metadata component analyzing block is adapted to reside in at least one communication entity;

a portion extracting block that extracts the portion from the data buffer using the size of the portion, wherein the portion extracting block is adapted to reside in at least one communication entity;

a data element reconstructing block that reconstructs the data element from the portion by matching size of the portion of the data element to the size of the data element, wherein the data element reconstructing block is adapted to reside in at least one communication entity; and

,

a synchronizing block that synchronizes the state of at least one communication entity using the reconstructed data element.

21. The system according to claim 20, wherein the current value capturing block comprises a bit identifying block that identifies all bits from the most significant non-zero bit of the data element to the least significant bit of the data element.

22. The system according to claim 20, wherein the encoding block comprises:

a size selecting block that selects the size of the metadata component based on the metadata component associated with the data type of the data element, wherein the size selecting block is adapted to reside in at least one communication entity; and

,

a value evaluating block that evaluates the value of the metadata component based on the current value of the data element, wherein the value evaluating block is adapted to reside in at least one communication entity.

23. The system according to claim 22, wherein the value evaluating block comprises:

a range identifying block that identifies a range of data element values from a predefined set of ranges of data element values pertaining to the data type of the data element, wherein the current value of the data element lies within the range, wherein the range identifying block is adapted to reside in at least one communication entity; and

,

a predefined metadata value block that selects a predefined metadata value associated with the identified range as the metadata component value, wherein the predefined metadata value block is adapted to reside in at least one communication entity.

24. The system according to claim 20, wherein the data buffer updating block comprises a concatenating block that concatenates the metadata component and the portion to the data buffer.

25. The system according to claim 20, wherein the data element reconstructing block comprises a zero prefixing block that prefixes zeros to the portion of the data element to match size thereof to the size of the data element.

26. The system according to claim 20, wherein at least one of the communication entities comprises a redundant server.

27. The method according to claim 20, wherein the data communication system comprises a redundant system.

28. A system for compressing a data structure comprising at least one data element to obtain a data buffer representing the data structure, the system comprising:

a current value capturing block that captures a current value of the data element pertaining to at least one portion thereof, wherein the current value capturing block is adapted to reside in at least one communication entity;

a data element encoding block that encodes the data element by selecting a metadata component characterizing the data element to enable data compression, wherein the data element encoding block is adapted to reside in at least one communication entity; and

,

a data buffer updating block that updates the data buffer using the metadata component and the portion, wherein the data buffer updating block is adapted to reside in at least one communication entity.

29. A system for decompressing a data buffer representing a data structure to obtain the data structure, the data buffer comprising at least one encoded data element, each encoded data element representing a data element of the data structure, the system comprising:

a metadata component analyzing block that analyzes a metadata component associated with an encoded data element in the data buffer to obtain a size of a portion of the data element represented by the encoded data element, wherein the metadata component analyzing block is adapted to reside in at least one communication entity;

a data element extracting block that extracts the portion of the data element from the data buffer using the size, wherein the data element extracting block is adapted to reside in at least one communication entity; and

,

a data element reconstructing block that reconstructs the data element from the portion by matching size of the portion of the data element to the size of the data element, wherein the data element reconstructing block is adapted to reside in at least one communication entity.

30. A computer readable medium having program stored thereon code, wherein the program code, when executed, communicates data structures in a compressed format to a communication entity in a data communication system, the data structures comprising at least one data element, the program code comprising:

first program code that captures a current value of the data element pertaining to at least one portion thereof;

second program code that encodes the data element by selecting a metadata component characterizing the data element to enable data compression;

third program code that updates a data buffer using the metadata component and the portion; and

,

fourth program code that communicates the data buffer to at least one receiving communication entity in the data communication system.

31. The computer readable medium according to claim 30, wherein the first program code comprises fifth program code that identifies all bits from the most significant non-zero bit of the data element to the least significant bit of the data element.

32. The computer readable medium according to claim 30, wherein the second program code comprises:

fifth program code that selects the size of the metadata component based on the metadata component associated with the data type of the data element; and

,

sixth program code that evaluates the value of the metadata component based on the current value of the data element.

33. The computer readable medium according to claim 32, wherein the sixth program code comprises:

seventh program code that identifies a range of data element values from a predefined set of ranges of data element values pertaining to the data type of the data element, wherein the current value of the data element lies within the range; and

,

eighth program code that selects a predefined metadata value associated with the identified range as the metadata component value.

34. A computer readable medium having program stored thereon code, wherein the program code, when executed, decompresses a data buffer corresponding to a data structure in a compressed format, the data buffer comprising a portion of a data element of the data structure and a metadata component corresponding to the portion, the program code comprising:

first program code that analyzes the metadata component associated with the portion to obtain a size of the portion;

second program code that extracts the portion from the data buffer using the size of the portion; and

,

third program code that reconstructs the data element from the portion by matching size of the portion of the data element to the size of the data element.

35. The computer readable medium according to claim 34, wherein the third program code comprises fourth program code that prefixing zeros to the portion to match the size thereof to the size of the data element.