Compression method for a data transfer that is independent of computer architecture and/or decompression method for a data record

• US 8,650,217 B2
• Filed: 11/21/2006
• Issued: 02/11/2014
• Est. Priority Date: 11/23/2005
• Status: Active Grant

• Current Assignee: Christian Werner
• Original Assignee: Universitat Zu Lubeck
• Inventors: Werner, Christian
• Primary Examiner(s): Hwa, Shyue Jiunn
• Application Number:
  US12/094,761
• Publication Number:
  US 20090193045A1
• Time in Patent Office: 2,639 Days
• Field of Search: None
• US Class Current: 707/796
• 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

A compression method for a data transfer that is independent of computer architecture and/or a decompression method for a data record that contains structural indicators and variable values are provided. The method includes the following steps: provision of a string automaton, which represents the structuring rules of the data record in a unit that compresses the original data record; input of the data record into the string automaton; generation of a second, shorter data record by the string automaton, the record containing the variable values of the first data record and control symbols that are specific to the string automaton equipment, the symbols representing a switch from an automaton condition to a sequence condition; and transmission of the second data record to a similar string automaton, which interprets the control symbols, whereby a copy of the original data record with an identical data structure is generated.

Claims

1. A method usable for compressing data records that comply with predefined structuring rules, the method comprising:

inputting a data record into a string automaton of a compression apparatus, wherein the data record comprises structure tags and unstructured values and complies with said predefined structuring rules, and wherein the string automaton represents predefined structuring rules of the data record as state transitions of the string automaton; and

compressing the input data record by the string automaton to thereby produce a compressed data record, wherein the compressed data record comprises the unstructured values of the data record and control symbols representing state transitions of the string automaton'"'"'s flow path caused by the structure tags of the input data record, with bit representations of the control symbols based on at least one of probabilities and frequencies of the state transitions encoded by the control symbols, and wherein compressing the input data record comprises;

replacing structure tags of the input data record by control symbols, wherein a respective structure tag is replaced by a control symbol to denote the state transition of the string automaton, in case the state transition from a current state to a subsequent state of the string automaton caused by the respective structure tag is ambiguous, and

removing structure tags of the input data record, wherein a respective structure tag of the input data record is removed, in case the state transition from the current state to the subsequent state of the string automaton caused by the respective structure tag is unambiguous.

2. The method according to claim 1, further comprising transmitting the compressed data record to a decompression apparatus.

3. The method according to claim 1, wherein the data record is an eXtensible Markup Language (XML) document.

4. The method according to claim 1, wherein processing the input data record by the string automaton comprises controlling external functional groups or modules.

5. The method according to claim 1, wherein the unstructured values of the data record are output by the string automaton in an at least partially altered, encoded form or are recognized and converted by said string automaton.

6. The method according to claim 1, further comprising storing additional coding rules in the string automaton relating to state transitions.

7. The method according to claim 1, further comprising determining bit representations of the control symbols for coding state transitions of the string automaton based on dynamically changing memory content.

8. The method according to claim 1, and the method comprises determining whether a state transition of from a current state to a subsequent state caused by the respective structure tag is ambiguous or unambiguous taking into account whether the current state allows for transitions to plural subsequent states.

9. The method according to claim 8, wherein the string automaton is implemented by circuitry comprising a push-down stack and determining whether a state transition of from a current state to a subsequent state caused by the respective structure tag is ambiguous or unambiguous is further taking into account the state of the push-down stack.

10. A method for decompressing a compressed data record, the method comprising:

inputting the compressed data record into a string automaton of a decompression apparatus, wherein the compressed data record comprises unstructured values of the uncompressed data record and control symbols representing state transitions of the string automaton'"'"'s flow path caused by the structure tags of the uncompressed data record upon compression, with bit representations of the control symbols based on at least one of probabilities and frequencies of the state transitions encoded by the control symbols, and wherein the string automaton represents predefined structuring rules of the data record as state transitions of the string automaton; and

decompressing, by the string automaton, the input compressed data record to generate the uncompressed data record comprising structure tags and unstructured values, wherein control symbols of the compressed data record and unambiguous state transitions of the string automaton'"'"'s flow path caused by the input compressed data record are replaced by structure tags to thereby generate the uncompressed data record.

11. The method according to claim 10, wherein, in addition or alternatively to generating the decompressed data record, processing the input compressed data record comprises controlling functional groups or modules by the string automaton.

12. The method according to claim 10, further comprising storing additional coding rules for state transitions of the string automaton.

13. The method according to claim 10, further comprising determining bit representations of the control symbols for coding state transitions of the string automaton based on dynamically changing memory content.

14. The method according to claim 10, wherein the string automaton is implemented by circuitry comprising a push-down stack and replacing control symbols of the compressed data record and unambiguous state transitions of the string automaton'"'"'s flow path caused by the input compressed data record by structure tags is taking into account the state of the push-down stack.

15. A compression apparatus for compressing of a data record, the compression apparatus comprising:

circuitry implementing a string automaton representing predefined structuring rules of the data record as state transitions of the string automaton,

wherein the circuitry implementing the string automaton is operable to compress a data record input to the string automaton to thereby produce a compressed data record, wherein the input data record comprises structure tags and unstructured values and complies with the predefined structuring rules,

wherein the circuitry implementing the string automaton is further operable to

replace structure tags of the input data record by control symbols, wherein a respective structure tag is replaced by a control symbol to denote the state transition of the string automaton with bit representations of the control symbols based on at least one of probabilities and frequencies of the state transitions encoded by the control symbols, in case the state transition from a current state to a subsequent state of the string automaton caused by the respective structure tag is ambiguous, and

remove structure tags of the input data record, wherein a respective structure tag of the input data record is removed in case the state transition from the current state to the subsequent state caused by the respective structure tag is unambiguous.

16. The compression apparatus according to claim 15, further comprising a push-down stack and wherein the circuitry implements a state machine.

17. A micro-chip comprising a compression apparatus according to claim 15.

18. The compression apparatus according to claim 15, wherein the circuitry implementing the string automaton is comprising a push-down stack, and is further operable to determine whether a state transition of from a current state to a subsequent state caused by the respective structure tag is ambiguous or unambiguous taking into account whether the current state allows for transitions to plural subsequent.

19. The compression apparatus according to claim 18, wherein the circuitry implementing is further operable to determine whether a state transition of from a current state, allowing for transitions to plural subsequent states, to a subsequent state caused by the respective structure tag is ambiguous or unambiguous taking into account the state of the push-down stack.

20. A decompression apparatus for decompressing a compressed data record, the decompression apparatus comprising:

circuitry implementing a string automaton representing predefined structuring rules of the data record as state transitions of the string automaton,

wherein the circuitry implementing the string automaton is operable to decompress a compressed data record input to the string automaton to thereby produce an uncompressed data record, wherein the input compressed data record comprises unstructured values and control symbols representing state transitions of the string automaton'"'"'s flow path caused by the structure tags of the uncompressed data record upon compression with bit representations of the control symbols based on at least one of probabilities and frequencies of the state transitions encoded by the control symbols,

wherein the circuitry implementing the string automaton is further operable to replace control symbols of the compressed data record and unambiguous state transitions of the string automaton'"'"'s flow path caused by the input compressed data record by structure tags to thereby generate the uncompressed data record.

21. The decompression apparatus according to claim 20, wherein the circuitry implementing the string automaton, in addition or alternatively to generating the decompressed data record, is operable to control functional groups or modules by the string automaton.

22. The decompression apparatus according to claim 20, further comprising a push-down stack and wherein the circuitry implements a state machine.

23. A micro-chip comprising a decompression apparatus according to claim 20.

24. The decompression apparatus according to claim 20, wherein the circuitry implementing the string automaton is comprising a push-down stack, and the circuitry implementing the string automaton is further operable to replace control symbols of the compressed data record and unambiguous state transitions of the string automaton'"'"'s flow path caused by the input compressed data record by structure tags taking into account the state of the push-down stack.