Adaptive packet compression apparatus and method

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

Claim 2

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.

Claim 21

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.

Claim 22

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.

Claim 24

A method for compressing a sequence of a plurality of data packets P 1 , P 2 , P 3 . . . , each consisting of an arbitrary number of text characters, into a sequence of corresponding compressed data packets C 1 , C 2 , C 3 . . . , 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.

Claim 25

A method for compressing a sequence of a plurality of data packets P 1 , P 2 , P 3 . . . , each consisting of an arbitrary number of text characters, into a sequence of corresponding compressed data packets C 1 , C 2 , C 3 . . . , 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.