Adaptive packet compression apparatus and method
First Claim
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 Pm ;
(b) parsing said packet Pm, such that the sequence of data elements of said packet Pm 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 Pm ;
(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.
9 Assignments
0 Petitions
Accused Products
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 Pm ; (b) parsing the packet Pm, such that the sequence of data elements of the packet Pm 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 Pm.
-
Citations
45 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 Pm ; (b) parsing said packet Pm, such that the sequence of data elements of said packet Pm 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 Pm ; (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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19)
-
-
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 Cm ; (b) decoding said packet Cm 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. - View Dependent Claims (21)
-
-
22. A method for compressing a sequence of a plurality of data packets P1, P2, P3 . . . , each consisting of an arbitrary number of text characters, into a sequence of corresponding compressed data packets C1, C2, C3 . . . , the method comprising the steps of:
-
(a) receiving a current packet Pm 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 Pm ; (c) parsing said current packet Pm in accordance with a scheme derived from the LZ77 technique and operating on said text history window, thereby converting said current packet Pm 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 Pm ; (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 Pm into a compressed packet Cm according to encoding tables generated on the basis of data that is independent of said current packet Pm ; (e) providing an output including said compressed packet Cm ; (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 Pm, 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. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45)
-
Specification