Adaptive packet compression apparatus and method

• US 5,945,933 A
• Filed: 01/27/1998
• Issued: 08/31/1999
• Est. Priority Date: 01/27/1998
• Status: Expired due to Term

• Current Assignee: Riverbed Technology Incorporated
• Original Assignee: Infit Ltd.
• Inventors: Kalkstein, Nir
• Primary Examiner(s): YOUNG, BRIAN K
• Application Number:
  US09/013,980
• Time in Patent Office: 581 Days
• Field of Search: 341/50, 341/51, 341/87, 341/67, 341/106, 341/65
• US Class Current: 341/63
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/46 Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream

Abstract

According to the present invention, there is provided a method for compressing each of a plurality of data packets to form a compressed packet for transmission by a communication device, the data packets being composed of a sequence of data elements and the data packets being stored on a first computer such that the method is performed by the first computer, the method comprising the steps of: (a) receiving one of the plurality of data packets designated as packet P_m ; (b) parsing the packet P_m, such that the sequence of data elements of the packet P_m is parsed into a sequence of parsed elements, each of the parsed elements having a form selected from the group consisting of a character, a pair of offset and length components, and a run length encoding consisting of a repetition factor component and a character component, and each of parsed elements and each of the components of the parsed elements having a frequency of occurrence; (c) selecting an encoding table from a historical array, the historical array including at least one encoding table from compression of at least one previously compressed data packet, the encoding table having been constructed according to the frequencies of occurrence of a plurality of parsed elements of the at least one previously compressed data packet, independent of data from the packet P_m.

Claims

1. A method for compressing each of a plurality of data packets to form a compressed packet for transmission by a communication device, the data packets being composed of a sequence of data elements and the data packets being stored on a first computer such that the method is performed by the first computer, the method comprising the steps of:

(a) receiving one of said plurality of data packets designated as packet P_m ;

(b) parsing said packet P_m, such that the sequence of data elements of said packet P_m is parsed into a sequence of parsed elements, each of said parsed elements having a form selected from the group consisting of a character, a pair of offset and length components, and a run length encoding consisting of a repetition factor component and a character component, and each of parsed elements and each of said components of said parsed elements having a frequency of occurrence;

(c) selecting an encoding table from a historical array, said historical array including at least one encoding table from compression of at least one previously compressed data packet, said encoding table having been constructed according to the frequencies of occurrence of a plurality of parsed elements of said at least one previously compressed data packet, independent of data from said packet P_m ;

(d) encoding said sequence of parsed elements according to said encoding table to form encoded data;

(e) packaging said encoded data into the compressed packet;

(f) constructing a historical frequency list of the frequencies of occurrence of said parsed elements;

(g) constructing an additional encoding table according to the frequencies of occurrence of said parsed elements; and

(h) storing said additional encoding table in said historical array.

2. The method of claim 1, wherein said packet Pm is a first packet of the plurality of data packets and said encoding table in said historical array is constructed according to a preselected distribution.

3. The method of claim 1, wherein said encoding table includes a Huffman tree.

4. The method of claim 1, wherein said encoding table includes a pair of Huffman trees, a first Huffman tree being constructed according to the frequencies of occurrence of:

(a) said parsed elements having said form of said character;

(b) said repetition factor component and said character component of said parsed elements having said form of said run length encoding; and

(c) said length component of said parsed elements having said form of said pair of offset and length components;

and a second Huffman tree being constructed according to the frequencies of occurrence of said offset component of said parsed elements having said form of said pair of offset and length components.

5. The method of claim 4, wherein said step of encoding includes encoding each of said parsed elements according to said first Huffman tree if said parsed element has said form of said character or said run-length encoding, and alternatively, if said parsed element has said form of said pair of offset and length components, encoding said length component according to said first Huffman tree and said offset component according to said second Huffman tree.

6. The method of claim 1, wherein said plurality of parsed elements are divided into a plurality of segments, each of said segments being encoded according to an encoding table from said historical array.

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

(i) arranging said elements of said list according to an arranging scheme, such that said historical frequency list is a ranked frequency list.

8. The method of claim 7, wherein said arranging scheme is a sorting scheme.

9. The method of claim 7, wherein said arranging scheme is a partial sorting scheme.

10. The method of claim 1, wherein said step of constructing said historical frequency list includes determining a weight of said frequency of occurrence of the data elements.

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

(i) arranging said elements of said list according to an arranging scheme, such that said historical frequency list is a ranked frequency list.

12. The method of claim 11, wherein said arranging scheme is a sorting scheme.

13. The method of claim 11, wherein said arranging scheme is a partial sorting scheme.

14. The method of claim 1, wherein said encoded data is a compressed packet C_m, the method further comprising the step of decoding said compressed packet C_m according to said encoding table.

15. The method of claim 6, wherein the compressed packet is a compressed packet C_m, further comprising the step of decoding said compressed packet C_m according to said portion of said historical array, said portion being selected according to said designation.

16. The method of claim 1, wherein said step (b) of parsing said packet P_m is performed according to a greedy scheme.

17. The method of claim 1, wherein said step (b) of parsing said packet P_m is performed according to a lookahead scheme.

18. The method of claim 1, wherein the compressed packet is transmitted from a first communication device on the first computer to a second communication device on a second computer.

19. The method of claim 18, further comprising the step of decoding said compressed packet C_m according to said encoding table, said step of decoding being performed by said second computer.

20. A method of decompressing each of a plurality of compressed packets to form a text string, the compressed packets being composed of encoded data and the compressed packets being stored on a first computer such that the method is performed by the first computer, the method comprising the steps of:

(a) receiving one of said plurality of compressed packets designated as packet C_m ;

(b) decoding said packet C_m according to an encoding table selected from an historical array including at least one encoding table from a previously decoded data packet to produce a sequence of parsed data elements, each of said parsed data elements having a form selected from the group consisting of a character, a pair of offset and length components, and a run length encoding and each of said parsed data elements having a frequency of occurrence;

(c) converting said sequence of parsed data elements into the text string;

(d) constructing a historical frequency list of the frequencies of occurrence of said parsed data elements;

(e) constructing an additional encoding table according to the frequencies of said parsed data elements; and

(f) storing said additional encoding table in said historical array.

21. The method of claim 20, wherein said step of constructing said historical frequency list includes determining a weight of the frequencies of occurrence of said parsed data elements.

22. A method for compressing a sequence of a plurality of data packets P₁, P₂, P₃ . . . , each consisting of an arbitrary number of text characters, into a sequence of corresponding compressed data packets C₁, C₂, C₃ . . . , the method comprising the steps of:

(a) receiving a current packet P_m of said sequence;

(b) storing in a text history window a selected number of text characters of at least one most recently received input packet, including at least text characters forming said current packet P_m ;

(c) parsing said current packet P_m in accordance with a scheme derived from the LZ77 technique and operating on said text history window, thereby converting said current packet P_m into a sequence of at least one segment, each segment comprising a sequence of one or more parsed data items each having a form selected from the group consisting of a Character, an (Offset, Length) pair, and a run length encoding, said (Offset, Length) pair having an offset component and a length component, and said run length encoding having a repetition factor component and a character component, each of said data items and said components of said data items having an occurrence frequency relating to the number of times said parsed data item or said component of said parsed data item occurs in said sequence of parsed data items constructed for said current packet P_m ;

(d) substituting said parsed data items of each of said segments by encoded bit strings being extracted from a selected encoding table, said selected encoding table being selected from an array of historical encoding tables, said array including one or more encoding tables generated for selected previous packets, or, for the first packet, including at least one encoding table based on some predetermined distribution of the data items, said encoded bit strings being accompanied by an indicator designating said selected encoding table, thereby encoding the current packet P_m into a compressed packet C_m according to encoding tables generated on the basis of data that is independent of said current packet P_m ;

(e) providing an output including said compressed packet C_m ;

(f) updating a historical frequency list, using a representation of said occurrence frequencies of selected parsed data items in selected already processed packets including said current packet P_m, in preparation for processing subsequent packets;

(g) generating a ranked historical frequency list by arranging said historical frequency list according to a selected arranging scheme;

(h) generating an encoding table using said ranked historical frequency list in accordance with a scheme identical to or derived from the Huffman encoding technique; and

(i) incorporating said generated encoding table in said array of historical encoding tables.

23. The method of claim 22, wherein each of said representations of said occurrence frequencies is derived from a selected function of at least the occurrence frequency of said selected parsed data item.

24. The method of claim 22, wherein said selected arranging scheme includes a sorting scheme.

25. The method of claim 23, wherein said selected arranging scheme includes a sorting scheme.

26. The method of claim 22, wherein said selected arranging scheme includes a partial sorting scheme.

27. The method of claim 23, wherein said selected arranging scheme includes a partial sorting scheme.

28. The method of claim 22, wherein said parsing scheme includes a greedy parsing method.

29. The method of claim 23, wherein said parsing scheme includes a greedy parsing method.

30. The method of claim 24, wherein said parsing scheme includes a greedy parsing method.

31. The method of claim 25, wherein said parsing scheme includes a greedy parsing method.

32. The method of claim 26, wherein said parsing scheme includes a greedy parsing method.

33. The method of claim 27, wherein said parsing scheme includes a greedy parsing method.

34. The method of claim 22, wherein said parsing scheme includes a lookahead parsing method.

35. The method of claim 23, wherein said parsing scheme includes a lookahead parsing method.

36. The method of claim 24, wherein said parsing scheme includes a lookahead parsing method.

37. The method of claim 25, wherein said parsing scheme includes a lookahead parsing method.

38. The method of claim 26, wherein said parsing scheme includes a lookahead parsing method.

39. The method of claim 27, wherein said parsing scheme includes a lookahead parsing method.

40. The method of claim 28, wherein said parsing scheme includes a lookahead parsing method.

41. The method of claim 29, wherein said parsing scheme includes a lookahead parsing method.

42. The method of claim 30, wherein said parsing scheme includes a lookahead parsing method.

43. The method of claim 31, wherein said parsing scheme includes a lookahead parsing method.

44. The method of claim 32, wherein said parsing scheme includes a lookahead parsing method.

45. The method of claim 33, wherein said parsing scheme includes a lookahead parsing method.