Efficient and lossless conversion for transmission or storage of data

• US 20010038347A1
• Filed: 12/29/2000
• Published: 11/08/2001
• Est. Priority Date: 01/03/2000
• Status: Active Grant

• Current Assignee: Efeckta Technologies Corporation
• Original Assignee: Efeckta Technologies Corporation
• Inventors: Avery, N. Caleb, Tobelmann, Ralph
• Granted Patent: US 6,633,244 B2
• Time in Patent Office: Days
• US Class Current: 341/51
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform
• 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/4006 Conversion to or from arithmetic code

Abstract

A system and method for lossless data compression. A mathematical transform equivalent to the content value of the data, and taking fewer bits to represent, is found.

Claims

1. A computer implemented method for compressing a message, comprising:

evaluating a numerical value of the message;

selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message; and

generating a code representing the selected transform and associated state information.

2. The method of

claim 1

, wherein the transform is a mathematical transform.

3. The method of

claim 2

, wherein the transform is an arithmetic transform.

4. The method of

claim 3

, wherein the arithmetic transform comprises an arithmetic function with at least one variable.

5. The method of

claim 4

, wherein selecting the transform and associated state information comprises:

selecting values for all variables of the arithmetic function;

determining a numerical value of the function with the selected variable values;

determining a remainder, the remainder being equal to the difference between the numerical value of the message and the numerical value of the function with the selected variable values; and

wherein the state information comprises the selected variable values and the remainder.

6. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

selecting a first transform and state information associated with the first transform;

determining a numerical value of the first transform with the associated state information;

determining a remainder, the remainder being equal to the difference between the numerical value of the message and the numerical value of the first transform with the associated state information;

selecting a second transform and associated state information, the second transform and state information having a numerical value equal to the numerical value of the remainder; and

wherein the transform and associated state information comprises the first transform and associated state information and the second transform and associated state information.

7. The method of

claim 2

, wherein the transform is a logical transform.

8. The method of

claim 7

, wherein the transform is a finite state machine.

9. The method of

claim 7

, wherein the transform is a disjunctive normal form (DNF) function.

10. The method of

claim 9

, wherein the DNF function comprises a plurality of basis strings.

11. The method of

claim 10

, wherein the plurality of basis strings are stored in a database of basis strings.

12. The method of

claim 10

, further comprising identifying a data type of the message.

13. The method of

claim 12

, wherein the plurality of basis strings are retrieved from a database of basis strings based on the data type of the message.

14. The method of

claim 9

, wherein selecting a set of state information for the transform comprises:

expressing the message in a standard DNF function; and

selecting a reduced expression of the standard DNF function.

15. The method of

claim 14

, wherein selecting the reduced expression of the standard DNF function comprises applying a combinatorial optimization heuristic.

16. The method of

claim 15

, wherein the combinatorial optimization heuristic is a genetic algorithm.

17. The method of

claim 1

, wherein selecting the transform and associated state information comprises testing a plurality of sets of state information.

18. The method of

claim 17

, wherein testing a plurality of sets of state information comprses:

for each of the plurality of sets of state information, generating a code representing the transform and set of state information;

evaluating the size of each code; and

selecting the transform and associated state information having the smallest size code.

19. The method of

claim 18

, the code further representing packet overhead.

20. The method of

claim 1

, wherein the transform is selected from a stored library of transforms.

21. The method of

claim 1

, wherein selecting the transform and associated state information comprises testing a plurality of transforms.

22. The method of

claim 21

, wherein testing the plurality of transforms comprises:

for each of the plurality of transforms, testing a plurality of sets of state information associated with the transform, each transform and set of state information having a numerical value equal to the numerical value of the message;

for each of the plurality of sets of state information, generating a code representing the transform and set of state information;

determining the size of each code; and

selecting the transform and associated state information having the smallest size code.

23. The method of

claim 22

, wherein selecting the transform and associated state information having the smallest size code comprises selecting the transform and associated state information having a code size equal to or less than a target code size.

24. The method of

claim 22

, further comprising, responsive to period of time elapsing, selecting the transform and associated state information tested having the smallest size code.

25. The method of

claim 22

, further comprising, responsive to executing a number of computational cycles, selecting the transform and associated state information tested having the smallest size code.

26. The method of

claim 1

, further comprising identifying a data type of the message.

27. The method of

claim 26

, wherein identifying the data type of the message comprises comparing the message to a database of messages with known data types.

28. The method of

claim 26

, wherein identifying the data type of the message comprises identifying an application that generated the message.

29. The method of

claim 26

, wherein the transform is selected based on the data type of the message.

30. The method of

claim 26

, wherein the state information is selected based on the data type of the message.

31. The method of

claim 1

, further comprising applying a mutation to the message prior to selecting the transform and associated state information.

32. The method of

claim 31

, wherein the code representing the selected transform and associated state information further represents packet overhead.

33. The method of

claim 32

, the packet overhead identifying the applied mutation.

34. The method of

claim 31

, wherein the mutation is selected from the group consisting of a shuffle, a complement, a shift, a compression method, a scaling method, and an XORing method.

35. The method of

claim 26

, further comprising applying a mutation to the message based on the data type of the message.

36. The method of

claim 26

, further comprising:

selecting a transform based on the data type; and

applying a mutation to the message, the mutation applied based on the selected transform.

37. The method of

claim 1

, wherein the code further represents packet overhead.

38. The method of

claim 37

, the packet overhead comprising a flag signifying that the message has been transformed.

39. The method of

claim 37

, the packet overhead comprising a bit-length of the message.

40. The method of

claim 37

, the packet overhead comprising a bit-length of the code.

41. The method of

claim 37

, the packet overhead comprising an identification of the message.

42. The method of

claim 37

, the packet overhead comprising an identification of the selected transform.

43. The method of

claim 37

, the packet overhead comprising information required to interpret the selected state information.

44. The method of

claim 1

, wherein the transform is selected from the group consisting of exponential factoring, power series, geometric series, integer series, trigonometric functions, Bessel functions, asymptotic series, disjunctive normal form functions, finite state automata, de Bruijn sequences, 3-D graph trees, N-dimensional space representations, infinite products, continued fractions, diophantina equations, Mobins functions, algebraic curves, integral transformations, inverse circular (trigonometric) functions, spherical trigonometric functions, logarithmic functions, hyperbole functions, orthogonal polynomials, polylogarithms, Legandra functions, elliptic integrals, sequence transformations (z-transform), and Markov chains.

45. The method of

claim 1

, wherein selecting the transform and associated state information comprises selecting the state information from a precalculated database, the precalculated database including a plurality of sets of state information and, for each of the plurality of sets of state information, a corresponding numerical value of the transform and that set of state information.

46. The method of

claim 45

, wherein selecting the state information from the precalculated database comprises selecting the set of state information in the precalculated database having the corresponding numerical value closest to the numerical value of the message.

47. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

selecting a first transform and associated state information from a precalculated database, the precalculated database including a plurality of sets of state information associated with the first transform and, for each of the plurality of sets of state information, a corresponding numerical value of the first transform and that set of state information;

determining a remainder, the remainder being equal to the difference between the numerical value of the message and a numerical value of the first transform and associated state information;

selecting a second transform and associated state information from the precalculated database; and

wherein the transform and associated state information comprises the first transform and associated state information and the second transform and associated state information.

48. The method of

claim 47

, wherein selecting the first transform and associated state information from the precalculated database comprises selecting the transform and associated state information in the precalculated database having the corresponding numerical value closest to the numerical value of the message.

49. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

retrieving a range of state information from a stored list of prior successful ranges of state information;

iteratively testing different sets of state information within the range of state information using an optimization algorithm;

for each set of state information, generating a code representing the transform and set of state information; and

selecting the tested set of state information having the smallest code.

50. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

applying a combinatorial optimization heuristic to determine a best state information, the best state information having the smallest code size representing the transform and that state information; and

selecting the best state information.

51. The method of

claim 50

, wherein the applied combinatorial optimization heuristic is selected from the group consisting of hill climbing, greedy hill climbing, tabu search, simulated annealing, an artificial neural network, a Boltzman machine, an evolutionary algorithm, and a genetic algorithm.

52. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

applying intelligent agents to determine the best state information, the best state information having the smallest size code representing the transform and that state information; and

selecting the best state information.

53. The method of

claim 52

, wherein the intelligent agents store the transform and associated state information selected for previous messages.

54. The method of

claim 1

, wherein selecting the transform and associated state information comprises:

selecting a plurality of partial solution transforms, the partial solution transforms combining to comprise the transform; and

for each of the plurality of partial solution transforms, selecting state information associated with that partial solution transform, the partial solution transform and state information having a numerical value equal to the numerical value of a portion of the message, the state information associated with each partial solution transform combining to comprise the state information.

55. The method of

claim 54

, wherein selecting the plurality of partial transforms and associated state information comprises applying dynamic programming.

56. The method of

claim 55

, wherein selecting the plurality of partial transforms and associated state information comprises applying one-dimensional dynamic programming.

57. The method of

claim 1

, further comprising storing the code representing the selected transform and associated state information.

58. The method of

claim 57

, wherein the code is stored in a computer readable medium.

59. The method of

claim 1

, further comprising transmitting the code representing the selected transform and associated state information.

60. The method of

claim 1

, further comprising:

evaluating the size of the code representing the selected transform and associated state information;

comparing the size of the code to the size of the message; and

storing the message if the size of the code is larger than the size of the message.

61. The method of

claim 1

, further comprising:

evaluating the size of the code representing the selected transform and associated state information;

comparing the size of the code to the size of the message; and

transmitting the message if the size of the code is larger than the size of the message.

62. A computer implemented method for compressing a message, comprising:

splitting the message into a plurality of segments;

for each segment, evaluating a numerical value of the segment;

for each segment, selecting a transform and associated state information for the segment, the selected transform and associated state information having a numerical value equal to the numerical value of the segment; and

for each segment, generating a code representing the selected transform and associated state information.

63. The method of

claim 62

, wherein splitting the message into a plurality of segments comprises:

determining a data type of the message;

determining an optimum size for the data segments based on the data type; and

splitting the message into data segments of the optimum size.

64. The method of

claim 62

, wherein splitting the message into a plurality of segments comprises:

determining a time constraint for compressing the message;

determining an optimum size for the data segments based on the time constraint; and

splitting the message into data segments of the optimum size.

65. The method of

claim 64

, wherein determining a time constraint for compressing the message comprises determining computing resources available to select the transform and associated state information.

66. The method of

claim 62

, further comprising applying a mutation to a segment.

67. The method of

claim 66

, further comprising applying a mutation to a segment based on the selected transform.

68. The method of

claim 66

, wherein the mutation is a segment-size adjustment.

69. A computer implemented method for compressing a message with a numerical value, comprising:

selecting a transform and associated state information, the transform and associated state information having a numerical value equal to the numerical value of the message; and

generating a code representing the selected transform and associated state information.

70. A computer implemented method for recovering a compressed message, comprising:

receiving a code representing a transform and state information;

calculating a numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message; and

outputting the numerical value as the recovered message.

71. A computer implemented method for recovering a compressed message, comprising:

receiving a plurality of codes, each code representing a transform and associated state information;

calculating the numerical value of each transform and associated state information, the numerical value of each transform and associated state information having a numerical value equal to a numerical value of a segment of the message; and

reconstituting the message by combining the numerical values of all the segments.

72. The method of

claim 71

, wherein a first code received provides information about a second code received.

73. A data compression system comprising:

a pre-processing module that;

receives a message;

splits the message into a plurality of segments, each segment having a numerical value;

for each segment, evaluates the numerical value of the segment; and

for each segment, outputs the numerical value of the segment to a transform module; and

a transform module that;

for each segment, selects a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the segment; and

generates a code representing the selected transform and associated selected state information.

74. A data decompression system comprising:

an unpackaging module that;

receives a plurality of codes, each code representing a transform and state information; and

for each code, outputs the transform and state information to a decoding module;

a decoding module that;

for each transform and state information, calculates a numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the segment; and

reconstitutes a message by concatenating the numerical values of all the segments.

75. A computer readable carrier wave, comprising a code representing a transform and associated state information, the transform and associated state information having a numerical value equal to a numerical value of a message, the code having a length less than the length of the message.

76. A computer program product encoded on computer readable medium and controlling a processor to perform a method for compressing a message, comprising:

evaluating a numerical value of the message;

selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message; and

generating a code representing the selected transform and associated state information.

77. A computer implemented method for compressing and decompressing a message, comprising:

evaluating a numerical value of the message;

selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message;

generating a code representing the selected transform and associated state information;

storing the code representing the selected transform and associated state information;

retrieving the code representing the transform and state information from storage;

and

calculating the numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.

78. A computer implemented method for compressing and decompressing a message, comprising:

evaluating a numerical value of the message;

selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message;

generating a code representing the selected transform and associated state information;

transmitting the code representing the selected transform and associated state information;

receiving the code representing the transform and state information; and

calculating the numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.

79. A system for compressing and decompressing a message, comprising:

a pre-processing module that;

receives a message with a numerical value;

evaluates the numerical value of the message; and

outputs the numerical value of the message to a transform module;

a transform module that;

selects a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message;

generates a code representing the selected transform and associated selected state information; and

outputs the code representing the selected transform and associated selected state information;

an unpackaging module that;

receives the code representing a transform and state information; and

a decoding module that;

calculates the numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.

80. A system for compressing a message, comprising:

means for evaluating a numerical value of the message;

means for selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message; and

means for generating a code representing the selected transform and associated state information.

81. The system of

claim 80

, further comprising means for identifying a data type of the message.

82. The system of

claim 80

, further comprising means for applying a mutation to the message prior to selecting the transform and associated state information.

83. A system for compressing a message, comprising:

means for splitting the message into a plurality of segments;

means for evaluating a numerical value of the segment for each segment;

means for selecting a transform and associated state information for each segment, the selected transform and associated state information having a numerical value equal to the numerical value of the segment; and

means for generating a code representing the selected transform and associated state information for each segment.

84. A system for recovering a compressed message, comprising:

means for receiving a code representing a transform and state information; and

means for calculating a numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.

85. A system for compressing and decompressing a message, comprising:

means for evaluating a numerical value of the message;

means for selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message;

means for generating a code representing the selected transform and associated state information;

means for storing the code representing the selected transform and associated state information;

means for retrieving the code representing the transform and state information from storage; and

means for calculating the numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.

86. A system for compressing and decompressing a message, comprising:

means for evaluating a numerical value of the message;

means for selecting a transform and associated state information, the selected transform and associated state information having a numerical value equal to the numerical value of the message;

means for generating a code representing the selected transform and associated state information;

means for transmitting the code representing the selected transform and associated state information;

means for receiving the code representing the transform and state information; and

means for calculating the numerical value of the transform and associated state information, the numerical value of the transform and associated state information equal to the numerical value of the message.