System and method for incremental and continuous data compression

• US 6,856,651 B2
• Filed: 05/31/2001
• Issued: 02/15/2005
• Est. Priority Date: 07/25/2000
• Status: Expired due to Term

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Peribit Networks, Inc. (Juniper Networks Incorporated)
• Inventors: Singh, Amit P.
• Primary Examiner(s): NGUYEN, DUNG X
• Application Number:
  US09/872,184
• Publication Number:
  US 20020037035A1
• Time in Patent Office: 1,356 Days
• Field of Search: 274/240, 274/219, 274/220, 348/384.1
• US Class Current: 375/240
• 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/3084 using adaptive string matching, e.g. the Lempel-Ziv method
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

A data compression system and method for that is capable of detecting and eliminating repeated phrases of variable length within a window of virtually unlimited size.

Claims

1. A method for compressing a data stream comprising the steps of:

receiving a data stream having a plurality of data symbols;

identifying a first data phrase as a first repeated phrase, said first data phrase being a combination of a first data term and at least a second data term, if said first data phrase matches a first library phrase, said first library phrase is one of a plurality of library phrases in a phrase library;

replacing said first data phrase with a first data phrase identifier associated with said first library phrase to generate a compressed data stream if said first data phrase is identified as said first repeated phrase;

storing said first data phrase as a second library phrase if said first data phrase does not match any of said plurality of library phrases;

replacing said first data phrase with a second data phrase identifier associated with said second library phrase to generate a compressed data stream if said first data phrase is not identified as said first repeated phrase; and

transmitting said compressed data stream while still receiving additional data symbols in said data stream;

wherein each of said data phrases includes a fixed number of data terms;

wherein each of said data terms is one of a data symbol and a data phrase identifier.

2. The method of claim 1, wherein said fixed number of data terms in each of said library phrases is two.

3. The method of claim 1, wherein values of said data stream are not known in advance of receipt, wherein said compressed data stream does not lose any data, and wherein the compression method operates with the data stream having any length.

4. The method of claim 1, wherein said first data phrase is stored as a second library phase only if said first data phrase has occurred a fixed number of times in a first portion of data stream;

and

wherein said first data phrase is replaced with said second data phrase identifier only if said first data phrase has occurred a fixed number of times in a first portion of data stream.

5. The method of claim 4, further comprising the step of:

transmitting library phrases, including the steps of;

identifying a first set of library phrases that have not been transmitted;

transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

6. The method of claim 5, further comprising the step of:

deleting a third library phrase of said plurality of library phrases based upon a first criteria.

7. The method of claim 6, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

8. The method of claim 7, further comprising the step of:

deleting a fourth library phrase when said fourth library phrase includes said third library phrase.

9. The method of claim 4, further comprising the steps of:

receiving said compressed data stream; and

determining said library phrases based upon said compressed data stream.

10. The method of claim 1, further comprising the step of:

transmitting library phrases, including the steps of;

identifying a first set of library phrases that have not been transmitted;

transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

11. The method of claim 10, further comprising the step of:

deleting a third library phrase of said plurality of library phrases based upon a first criteria.

12. The method of claim 11, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

13. The method of claim 12, further comprising the step of:

deleting a fourth library phrase when said fourth library phrase includes said third library phrase.

14. The method of claim 1, further comprising the steps of:

receiving said compressed data stream; and

determining said library phrases based upon said compressed data stream.

15. The method of claim 1, further comprising the step of:

deleting a third library phrase of said plurality of library phrases based upon a first criteria.

16. The method of claim 15, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

17. A system for compressing a data stream comprising:

receiving means for receiving a data stream having a plurality of data symbols;

identifying means for identifying a first data phrase as a first repeated phrase, said first data phrase being a combination of a first data term and at least a second data term, if said first data phrase matches a first library phrase, said first library phrase is one of a plurality of library phrases in a phrase library;

first replacing means for replacing said first data phrase with a first data phrase identifier associated with said first library phrase to generate a compressed data stream if said first data phrase is identified as said first repeated phrase;

first storing means storing said first data phrase as a second library phrase if said first data phrase does not match any of said plurality of library phrases;

second replacing means for replacing said first data phrase with a second data phrase identifier associated with said second library phrase to generate a compressed data stream if said first data phrase is not identified as said first repeated phrase; and

transmitting means for transmitting said compressed data stream while still receiving additional data symbols in said data stream;

wherein each of said data phrases includes a fixed number of data terms;

wherein each of said data terms is one of a data symbol and a data phrase identifier.

18. The system of claim 17, wherein said fixed number of data terms in each of said library phrases is two.

19. The system of claim 17, wherein values of said data stream are not known in advance of receipt, wherein said compressed data stream does not lose any data, and wherein the compression method operates with the data stream having any length.

20. The system of claim 17, wherein said first data phrase is stored as a second library phase only if said first data phrase has occurred a fixed number of times in a first portion of data stream;

and

wherein said first data phrase is replaced with said second data phrase identifier only if said first data phrase has occurred a fixed number of times in a first portion of data stream.

21. The system of claim 20, further comprising:

phrase identifying means for identifying a first set of library phrases that have not been transmitted;

phrase transmitting means for transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

22. The system of claim 21, further comprising:

phrase deletion means for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

23. The system of claim 22, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

24. The system of claim 23, wherein said phrase deletion means deletes a fourth library phrase when said fourth library phrase includes said third library phrase.

25. The system of claim 20, further comprising:

receiving means for receiving said compressed data stream; and

library creation means for determining said library phrases based upon said compressed data stream.

26. The system of claim 17, further comprising:

phrase identifying means for identifying a first set of library phrases that have not been transmitted;

phrase transmitting means for transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

27. The system of claim 26, further comprising:

phrase deletion means for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

28. The system of claim 27, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

29. The system of claim 28, wherein said phrase deletion means deletes a fourth library phrase when said fourth library phrase includes said third library phrase.

30. The system of claim 17, further comprising:

receiving means for receiving said compressed data stream; and

library creation means for determining said library phrases based upon said compressed data stream.

31. The system of claim 17, further comprising:

phrase deletion means for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

32. The system of claim 31, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

33. The system of claim 32, wherein said phrase deletion means deletes a fourth library phrase when said fourth library phrase includes said third library phrase.

34. A system for compressing a data stream comprising:

a data receiver for receiving a data stream having a plurality of data symbols;

a phrase library having a plurality of library phrases;

a detector unit, coupled to said data receiver including;

a first identification unit for identifying a first data phrase as a first repeated phrase, said first data phrase being a combination of a first data term and at least a second data term, if said first data phrase matches a first library phrase, said first library phrase is one of a plurality of library phrases in a phrase library;

a library building unit for storing said first data phrase as a second library phrase if said first data phrase does not match any of said plurality of library phrases; and

a replacing unit for replacing said first data phrase with a first data phrase identifier associated with said first library phrase to generate a compressed data stream if said first data phrase is identified as said first repeated phrase and for replacing said first data phrase with a second data phrase identifier associated with said second library phrase to generate a compressed data stream if said first data phrase is not identified as said first repeated phrase; and

a transmitting unit for transmitting said compressed data stream while still receiving additional data symbols in said data stream;

wherein each of said data phrases includes a fixed number of data terms; and

wherein each of said data terms is one of a data symbol and a data phrase identifier.

35. The system of claim 34, wherein said fixed number of data terms in each of said library phrases is two.

36. The system of claim 34, wherein values of said data stream are not known in advance of receipt, wherein said compressed data stream does not lose any data, and wherein the compression method operates with the data stream having any length.

37. The system of claim 34, wherein said first data phrase is stored as a second library phase only if said first data phrase has occurred a fixed number of times in a first portion of data stream;

and

wherein said first data phrase is replaced with said second data phrase identifier only if said first data phrase has occurred a fixed number of times in a first portion of data stream.

38. The system of claim 37, further comprising:

library phrase identifier for identifying a first set of library phrases that have not been transmitted;

library transmitter for transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

39. The system of claim 38, further comprising:

a deletion unit for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

40. The system of claim 39, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

41. The system of claim 40, wherein said deletion unit deletes a fourth library phrase when said fourth library phrase includes said third library phrase.

42. The system of claim 37, further comprising:

receiving unit for receiving said compressed data stream; and

library determining unit for determining said library phrases based upon said compressed data stream.

43. The system of claim 34, further comprising:

library phrase identifier for identifying a first set of library phrases that have not been transmitted;

library transmitter for transmitting said first set of library phrases before a data phase identifier associated with any of said library phrases in said first set is transmitted as part of said compressed data stream.

44. The system of claim 43, further comprising:

a deletion unit for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

45. The system of claim 44, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

46. The system of claim 45, wherein said deletion unit deletes a fourth library phrase when said fourth library phrase includes said third library phrase.

47. The system of claim 34, further comprising:

receiving unit for receiving said compressed data stream; and

library determining unit for determining said library phrases based upon said compressed data stream.

48. The system of claim 34, further comprising:

a deletion unit for deleting a third library phrase of said plurality of library phrases based upon a first criteria.

49. The system of claim 48, wherein said first criteria is one of an expiration of a first time period during which said third library phrase is not referenced, and a receiving of a first number of symbols in which said third data phrase is not referenced.

50. The system of claim 49, wherein said deletion unit deletes a fourth library phrase when said fourth library phrase includes said third library phrase.