Efficient and lossless conversion for transmission or storage of data

• US 6,633,244 B2
• Filed: 12/29/2000
• Issued: 10/14/2003
• Est. Priority Date: 01/03/2000
• Status: Expired due to Fees

• Current Assignee: Efeckta Technologies Corporation
• Original Assignee: Efeckta Technologies Corporation
• Inventors: Tobelmann, Ralph, Avery, Caleb
• Primary Examiner(s): WAMSLEY, PATRICK G
• Application Number:
  US09/753,059
• Publication Number:
  US 20010038347A1
• Time in Patent Office: 1,019 Days
• Field of Search: 341/51, 341/60, 341/50, 341/95, 341/80, 382/248, 382/169, 707/102, 707/2, 375/240.01, 375/240.24, 375/240.11, 386/46, 386/33, 348/231.6, 348/391.1
• US Class Current: 341/60
• 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 method of compressing a digital data stream comprising the steps of:

segmenting the digital data stream into discrete segments;

evaluating each discrete segment and selecting a transform for each discrete segment wherein said selected transform along with associated state information has a numerical value indicative of the discrete segment;

generating a code representative of each of said selected transform and associated state information for each of said discrete segments, whereby said generated code and selected state information for each discrete segment represents a numerical value indicative of said discrete segment.

2. The method of claim 1, wherein the transform is a mathematical transform.

3. The method of claim 2, wherein the transform is a logical transform.

4. The method of claim 3, wherein the transform is a disjunctive normal form (DNF) function.

5. The method of claim 4, wherein the DNF function comprises a plurality of basis strings.

6. The method of claim 5, further comprising identifying a data type of the message.

7. The method of claim 6, wherein the plurality of basis strings are retrieved from a database of basis strings based on the data type of the message.

8. The method of claim 5, wherein the plurality of basis strings are in a database of basis strings.

9. The method of claim 4, 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.

10. The method of claim 9, wherein selecting the reduced expression of the standard DNF function comprises applying a combinatorial optimization heuristic.

11. The method of claim 10, wherein the combinatorial optimization heuristic is genetic algorithm.

12. The method of claim 3, wherein the transform is a finite state machine.

13. The method of claim 2, wherein the transform is an arithmetic transform.

14. The method of claim 13, wherein the arithmetic transform comprises an arithmetic function with at least one variable.

15. The method of claim 14, 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.

16. The method of claim 1, wherein selecting the transform and associated state information comprises testing a plurality of sets of state information.

17. The method of claim 16, wherein testing a plurality of sets of state information comprises:

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.

18. The method of claim 17, the code further representing packet overhead.

19. The method of claim 1, wherein selecting the transform and associated state information comprises testing a plurality of transforms.

20. The method of claim 19, 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.

21. The method of claim 20, 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.

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

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

24. The method of claim 1 further comprising applying a mutation to the message prior to selecting the transform and associated state information.

25. The method of claim 24, wherein the code representing the selected transform associated state information further represents packet overhead.

26. The method of claim 25, the packet overhead identifying the applied mutation.

27. The method of claim 24, 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.

28. 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.

29. The method of claim 28, wherein selecting the plurality of partial transforms and associated state information comprising applying dynamic programming.

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

31. The method of claim 1, further comprising identifying a data type of the message.

32. The method of claim 31, wherein identifying the data type of the message comprises comparing the message to a database of messages with known data types.

33. The method of claim 31, wherein identifying the data type of the message comprises identifying an application that generated the message.

34. The method of claim 31, wherein the transform is selected based on the data type of the message.

35. The method of claim 31, wherein the state information is selected based on the data type of the message.

36. The method of claim 31, further comprising applying a mutation to the message based on the data type of the message.

37. The method of claim 31, 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.

38. The method of claim 1, wherein the code further represents packet overhead.

39. The method of claim 38, the packet overhead comprising a flag signifying that the message has been transformed.

40. The method of claim 38, the packet overhead comprising a bit-length of the message.

41. The method of claim 38, the packet overhead comprising a bit-length of the code.

42. The method of claim 38, the packet overhead comprising an identification of the message.

43. The method of claim 38, the packet overhead comprising an identification of the selected transform.

44. The method of claim 38, the packet overhead comprising information required to interpret the selected state information.

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 closes to the numerical value of the message.

49. 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.

50. The method of claim 49, 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.

51. 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.

52. The method of claim 51, wherein the intelligent agents store the transform and associated state information selected for previous messages.

53. 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.

54. The method of claim 1, wherein the transform is selected from a stored library of transforms.

55. The method of claim 39, 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, Diophantine equations, Mobins functions, algebraic curves, integral transformations, inverse circular (trigonometric functions, spherical trigonometric functions, logarithmic functions, hyperbole functions, orthogonal polynomials, polylogarithms, Legandre functions, elliptic integrals, sequence transformations (z-transform), and Markov chains.

56. 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.

57. 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.

58. 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.

59. A method as in claim 1 wherein said generated codes and said associated state information values are stored.

60. A method as in claim 1 wherein said generated codes and said associated state information values are transmitted.