Adaptive data compression method and apparatus

Claim 2

A dynamic data compression method, comprising the steps (1) providing an encoding table having a plurality of sets of digital codes of varying lengths associated with characters of an alphabet, some of the digital codes being shorter than others, the digital codes being of the same length in a given set but of a different length between sets, said encoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward the beginning of the array and a set of longer codes toward the end of the array; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in response to the presented item of data, selecting a code from one of the sets in the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; and (5) periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the encoding table as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 3

The method of claim 1, wherein the step of periodically adjusting the corresponding relationship of the codes and the characters of the alphabet in the encoding table comprises the steps of: (6) maintaining a character count associated with each character of the alphabet; (7) incrementing the particular character count associated with the particular character represented by an item of data presented for encoding after selecting a code from the encoding table; (8) after incrementing the character count, comparing the particular character count to character count for a preselected character at a position in the array more likely to be associated with a shorter code; and (9) if the particular character count is greater than the character count for the preselected character, exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count with a position in the array more likely to be associated with a shorter code.

Claim 4

The method of claim 2, wherein the preselected character is positioned a predetermined number of positions in the array toward the beginning of the array from the particular character.

Claim 5

The method of claim 3, wherein the predetermined number of positions is sixteen.

Claim 6

The method of claim 1, wherein the step of periodically adjusting the sizes of the sets comprises the steps of: (1) summing the character counts for predetermined groups of consecutive characters to obtain a plurality of group counts; (2) comparing the group count for groups towards the end of the array with the character counts for characters towards the beginning of the array; (3) increasing the size of the set of the shortest digital codes until there is a correspondence between a group count and a character count at the end of the set of shortest digital codes, whereby the size of the set of the shortest digital codes is increased to include more characters having a higher probability of occurrence than any the characters in the set of codes associated with the group counts.

Claim 7

The method of claim 5, wherein there are at least three sets of digital codes, and wherein the set associated with the longest digital codes increases in size in increments of the size of the groups while the set associated with the shortest codes increases in size in increments of a single character.

Claim 8

The method of claim 6, wherein the set associated with the shortest digital codes varies in size between 0 and 15.

Claim 9

The method of claim 6, wherein the set associated with the longest digital codes varies in size between 0 and 240.

Claim 10

The method of claim 6, wherein the shortest digital code is 4 bits, and the longest digital code is 12 bits.

Claim 11

The method of claim 6, wherein the set associated with the shortest digital code initially has 4 members and the set associated with the longest digital code initially has 64 members.

Claim 12

The method of claim 5, wherein the step of periodically adjusting the sizes of the sets is repeated after the occurrence of a predetermined number of items of data presented for encoding.

Claim 13

The method of claim 11, wherein the predetermined number of items between adjustments to the size of the sets is 128.

Claim 14

The method of claim 5, wherein the predetermined groups of consecutive characters have sixteen characters.

Claim 15

The method of claim 1, wherein the step of periodically adjusting the sizes of the sets is taken after every k items of data presented for encoding.

Claim 16

The method of claim 14, where k is 128.

Claim 17

The method of claim 1, wherein there are n characters in the alphabet, wherein the set associated with the shortest digital code has a members, and the set associated with the longest digital code has c members, and wherein the step of periodically adjusting the sizes of the sets comprises changing the relative values of the numbers a and c by taking the following steps: (i) summing the character counts for consecutive groups of m characters to obtain a plurality of n/m group counts; (ii) comparing the group count for group (n/m)-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; (iii) if the group count for group (n/m)-i-1 is less than the character count for character j, then, incrementing i and j and going back to the step (ii); (iv) if the group count for group (n/m)-i-1 is greater than or equal to the character count for character j, then establishing an encoding level of a=j+1 by assigning j+1 of the shortest digital codes, and c=(n/m) x(i+1) of the longer digital codes.

Claim 18

The method of claim 16, wherein there is a set of characters having digital codes sized in between the shortest digital code and the longest digital code and having b members, and wherein b=n-(j+1)-((n/m)×(i+1)).

Claim 19

A data decompression method, comprising the steps of: (1) providing a decoding table having a plurality of sets of digital codes associated with the characters of an alphabet, the digital codes being of the same length in a given set but of a different length between sets, some of the digital codes being shorter than others, said decoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward the beginning of the array and a set of longer codes toward the end of the array; (2) presenting for decoding an item of coded data represented by one of the digital codes; (3) in response to the presented item of coded data, selecting a character from one of the sets in the decoding table which corresponds to the particular digital code represented by the presented item of coded data; (4) providing the selected character as a decoded output; and (5) periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the decoding table as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequently occurring characters become associated with shorter codes in the decoding table.

Claim 20

A data decompression method, comprising the steps of: (1) providing a decoding table having a plurality of sets of digital codes associated with the characters of an alphabet, the digital codes being of the same length in a given set but of a different length between sets, some of the digital codes being shorter than others, said decoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward the beginning of the array and a set of longer codes toward the end of the array; (2) presenting for decoding an item of coded data represented by one of the digital codes; (3) in response to the presented item of coded data, selecting a character from one of the sets in the decoding table which corresponds to the particular digital code represented by the presented item of coded data; (4) providing the selected character as a decoded output; and (5) periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the decoding table as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequently occurring characters become associated with shorter codes in the decoding table.

Claim 21

A dynamic data compression apparatus, comprising: memory means for storing an encoding table comprising a plurality of sets of digital codes associated with characters of an alphabet, some of the digital codes being shorter than others, the digital codes being of the same length in a given set but of a different length between sets, said encoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward a beginning of the array and a set of longer codes toward the end of the array; means for receiving for encoding an item of data represented by one of the characters of the alphabet; means responsive to the presented item of data for selecting a code from one of the sets in the encoding table in said memory means which corresponds to the particular character of the alphabet represented by the presented item of data; output means for providing the selected code as an output; and code/character relationship adjusting means for periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the encoding table in said memory means as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 22

A dynamic data compression apparatus, comprising: memory means for storing an encoding table comprising a plurality of sets of digital codes associated with characters of an alphabet, some of the digital codes being shorter than others, the digital codes being of the same length in a given set but of a different length between sets, said encoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward a beginning of the array and a set of longer codes toward the end of the array; means for receiving for encoding an item of data represented by one of the characters of the alphabet; means responsive to the presented item of data for selecting a code from one of the sets in the encoding table in said memory means which corresponds to the particular character of the alphabet represented by the presented item of data; output means for providing the selected code as an output; and code/character relationship adjusting means for periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the encoding table in said memory means as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters presented for encoding, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 23

The apparatus of claim 19, wherein said adjusting means comprises: means for maintaining a character count associated with each character of the alphabet in said memory means; means for incrementing the particular character count associated with the particular character represented by an item of data presented for encoding after selecting a code from the encoding table; means for comparing the particular character count to the character count for a preselected character at a position in the array more likely to be associated with a shorter code after incrementing the character count; and means responsive to the particular character count being greater than the character count for the preselected character for exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count with a position in the array more likely to be associated with a shorter code.

Claim 24

The apparatus of claim 20, wherein the preselected character is positioned a predetermined number of memory locations in the array toward the beginning of the array from the particular character.

Claim 25

The apparatus of claim 21, wherein the predetermined number of memory locations is sixteen.

Claim 26

The apparatus of claim 19, wherein said set size adjusting means comprises: means for summing the character counts for predetermined groups of consecutive characters to obtain a plurality of group counts; means for comparing the group count for groups towards the end of the array with the character counts for characters towards the beginning of the array; means for increasing the size of the set of the shortest digital codes until there is a correspondence between a group count and a character count at the end of the set of shortest digital codes, whereby the size of the set of the shortest digital codes is increased to include more characters having a higher probability of occurrence than any the characters in the set of codes associated with the group counts.

Claim 27

The apparatus of claim 23, wherein there are at least three sets of digital codes, and wherein the set associated with the longest digital codes increases in size in increments of the size of the groups, while the set associated with the shortest codes increases in size in increments of a single character.

Claim 28

The apparatus of claim 24, wherein the set associated with the shortest digital codes varies in size between 0 and 15.

Claim 29

The apparatus of claim 24, wherein the set associated with the longest digital codes varies in size between 0 and 240.

Claim 30

The apparatus of claim 24, wherein the shortest digital code is 4 bits, and the longest digital code is 12 bits.

Claim 31

The apparatus of claim 24, wherein the set associated with the shortest digital code initially has 4 members and the set associated with the longest digital code initially has 64 members.

Claim 32

The apparatus of claim 23, wherein said set size adjusting means is operative after the occurrence of a predetermined number of items of data presented for encoding.

Claim 33

The apparatus of claim 29, wherein the predetermined number of items between adjustments to the size of the sets is 128.

Claim 34

The apparatus of claim 23, wherein the predetermined groups of consecutive characters have sixteen characters.

Claim 35

The apparatus of claim 19, wherein said set size adjusting means is operative after every k items of data presented for encoding.

Claim 36

The method of claim 32, where k is 128.

Claim 37

The method of claim 19, wherein there are n characters in the alphabet, wherein the set associated with the shortest digital code has a members, and the set associated with the longest digital code has c members, and wherein said set size adjusting means changes the relative values of the numbers a and c and comprises: means for summing the character counts for consecutive groups of m characters to obtain a plurality of n/m group counts; means for comparing the group count for group (n/m)-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; means for incrementing i and j if the group count for group (n/m)-i-1 is less than the character count for character j and returning control to said comparing means; means for assigning a=j+1 of the shortest digital codes and c=(n/m)×(i+1) of the longer digital codes, if the group count for group (n/m)-i-1 is greater than or equal to the character count for character j.

Claim 38

The apparatus of claim 34, wherein there is a set of characters having digital codes sized in between the shortest digital code and the longest digital code having b members, and wherein b=n-(j+1)-((n/m)×(i+1)).

Claim 39

The apparatus of claim 19, wherein said apparatus is employed in a modem.

Claim 40

The apparatus of claim 19, wherein said data receiving means, said code selecting means, said output means, and said code/character relationship adjusting means comprises a programmed microcomputer.

Claim 41

A data decompression apparatus, comprising: memory means for storing a decoding table having a plurality of sets of digital codes associated with the characters of an alphabet, some of the digital codes being shorter than others, the digital codes being of the same length in a given set but of a different length between sets, said decoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward the beginning of the array and a set of longer codes toward the end of the array; means for receiving for decoding an item of coded data represented by one of the digital codes; means responsive to the presented item of coded data for selecting a character from one of the sets in the decoding table in said memory means which corresponds to the particular digital code represented by the presented item of coded data; means for providing the selected character as a decoded output; and means for periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the decoding table in said memory means as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequencyl occurring characters become associated with shorter codes in the decoding table.

Claim 42

A data decompression apparatus, comprising: memory means for storing a decoding table having a plurality of sets of digital codes associated with the characters of an alphabet, some of the digital codes being shorter than others, the digital codes being of the same length in a given set but of a different length between sets, said decoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with a set of shorter codes toward the beginning of the array and a set of longer codes toward the end of the array; means for receiving for decoding an item of coded data represented by one of the digital codes; means responsive to the presented item of coded data for selecting a character from one of the sets in the decoding table in said memory means which corresponds to the particular digital code represented by the presented item of coded data; means for providing the selected character as a decoded output; and means for periodically adjusting the corresponding relationship of the codes, the characters of the alphabet, and the sizes of the sets of digital codes in the decoding table in said memory means as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters resultant from decoding, whereby as the frequency of occurrence of characters over a plurality of characters resultant from decoding changes, the more frequencyl occurring characters become associated with shorter codes in the decoding table.

Claim 43

A dynamically variable data compression method, particularly useful in a series/sequential data transmission application such as a modem, comprising the steps of: (1) providing an alphabet of n characters to be employed in representing information, ranging from 0 to n; (2) arranging the n characters in an initial ordered array; (3) providing a set of z bit codes to be used for encoding said n characters, some of said codes having greater bit lengths than others, with shorter codes being associated with positions in the array toward the beginning and longer codes being associated with positions in the array toward the end; (4) providing a sequential input information stream represented by the characters of said alphabet to be encoded with said codes; (5) for each item x of said sequential input information stream taking the following steps: (i) providing a z bit code as an output chosen from said set of codes as a function of the relative position in the array of the character corresponding to the item x; (ii) incrementing a character count CC associated with the character of said alphabet which represents said particular item x of said sequential input information stream; (iii) comparing the character count CC with the character count associated with each character within a predetermined range toward the beginning of the array; (iv) when the character count CC is found upon comparison to be greater than or equal to the character count for a character toward the beginning of the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count, whereby as the frequency of occurrence of characters in the input information stream changes, the more frequently appearing characters tend to migrate toward the beginning of the array and thereby become associated with shorter ones of said codes.

Claim 44

A dynamically variable data compression method, particularly useful in a series/sequential data transmission application such as a modem, comprising the steps of: (1) providing an alphabet of n characters to be employed in representing information, ranging from 0 to n; (2) arranging the n characters in an initial ordered array; (3) providing a set of z bit codes to be used for encoding said n characters, some of said codes having greater bit lengths than others, with shorter codes being associated with positions in the array toward the beginning and longer codes being associated with positions in the array toward the end; (4) providing a sequential input information stream represented by the characters of said alphabet to be encoded with said codes; (5) for each item x of said sequential input information stream taking the following steps: (i) providing a z bit code as an output chosen from said set of codes as a function of the relative position in the array of the character corresponding to the item x; (ii) incrementing a character count CC associated with the character of said alphabet which represents said particular item x of said sequential input information stream; (iii) comparing the character count CC with the character count associated with each character within a predetermined range toward the beginning of the array; (iv) when the character count CC is found upon comparison to be greater than or equal to the character count for a character toward the beginning of the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count, whereby as the frequency of occurrence of characters in the input information stream changes, the more frequently appearing characters tend to migrate toward the beginning of the array and thereby become associated with shorter ones of said codes.

Claim 45

The method of claim 39, wherein a first predetermined number a of characters in the alphabet are associated with a first code, wherein a second predetermined number b of characters in the alphabet are associated with a second code, the first code being shorter than the second code, and further comprising the step of adjusting the relative values of a and b as a function of the frequency of occurrence of characters in the input information stream.

Claim 46

The method of claim 39, wherein z is at least four.

Claim 47

The method of claim 39, wherein z is selected from the group consisting of four, eight, and twelve.

Claim 48

A dynamic data decompression method, particularly useful in a series/sequential data receiving application such as a modem, comprising the steps of: (1) providing an alphabet of n d characters to be employed in representing information, ranging from 0 to n d ; (2) arranging the n d characters in an initial ordered array, each of the characters being associated with a z bit code used for decoding the characters, some of the codes having greater bit lengths than others, with shorter codes being associated with positions in the array toward the beginning and longer codes being associated with positions in the array toward the end; (3) receiving a sequential data stream encoded with the codes; (4) looking up a character in the alphabet corresponding to the code; (5) providing as an output a character of the alphabet corresponding to the code;

Claim 49

A dynamic data decompression method, particularly useful in a series/sequential data receiving application such as a modem, comprising the steps of: (1) providing an alphabet of n d characters to be employed in representing information, ranging from 0 to n d ; (2) arranging the n d characters in an initial ordered array, each of the characters being associated with a z bit code used for decoding the characters, some of the codes having greater bit lengths than others, with shorter codes being associated with positions in the array toward the beginning and longer codes being associated with positions in the array toward the end; (3) receiving a sequential data stream encoded with the codes; (4) looking up a character in the alphabet corresponding to the code; (5) providing as an output a character of the alphabet corresponding to the code;

Claim 50

(6) maintaining the order of the array for the alphabet by taking the following steps for each item x of the sequential data stream: (i) incrementing a character count CC associated with the character of the alphabet which represents said item x of the output character, (ii) comparing the character count CC with the character count associated with each character within a predetermined range toward the beginning the array; (iii) when the character count CC is found upon comparison to be greater than or equal to the character count for a character toward the begnning of the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count, whereby as the frequency of occurrence of characters being output changes, the more frequently appearing corresponding characters in the alphabet tend to migrate toward the beginning of the decoding array.

Claim 51

(6) maintaining the order of the array for the alphabet by taking the following steps for each item x of the sequential data stream: (i) incrementing a character count CC associated with the character of the alphabet which represents said item x of the output character, (ii) comparing the character count CC with the character count associated with each character within a predetermined range toward the beginning the array; (iii) when the character count CC is found upon comparison to be greater than or equal to the character count for a character toward the begnning of the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count, whereby as the frequency of occurrence of characters being output changes, the more frequently appearing corresponding characters in the alphabet tend to migrate toward the beginning of the decoding array.

Claim 52

A dynamically variable data compression method, particularly useful in a series/sequential data transmission application such as a modem, comprising the steps of: (1) providing an alphabet of n characters to be employed in representing information, ranging from 0 to n; (2) arranging the n characters in an initial ordered array; (3) providing a first set of p-bit codes to be used for encoding a first predetermined number a of said n characters, a second set of q-bit codes to be used for encoding a second predetermined number b of said n characters, and a third set of r-bit codes to be used for encoding a third predetermined number of c of said n characters, where a+b+c=n; (4) providing a sequential input information stream represented by the characters of said alphabet to be encoded with said p-, said q-, or said r-bit codes; (5) for each item x of said sequential input information stream, taking the following steps: (i) providing a z bit code as an output chosen from said first or said second or said third set of codes as a function of the relative position in the array of the character corresponding to the item x, where z is p or q or r; (ii) incrementing a character count CC associated with the character of said alphabet which represents said particular item x of said sequential input information stream; (iii) comparing the character count CC with the character count associated with each character within a predetermined range lower in the array, up to a total of d places lower in the array, where d is a predetermined number less than n; (iv) when the character count CC is found upon comparison to be greater than or equal to the character count for a character lower in the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character lower in the array within said predetermined range having the equal or lesser character count; (6) after every k characters of said sequential input information stream, changing the "encoding level" represented by the relative values of the numbers a, b, and c by taking the following steps: (i) summing the character counts for consecutive groups of m characters to obtain a plurality of n/m group counts; (ii) comparing the group count for group (n/m)-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; (iii) if the group count for group (n/m)--1 is less than the character count for character j, then, incrementing i and j and going back to the step 6(ii); (iv) if the group count for group (n/m)-i-1 is greater than or equal to the character count for character j, then establishing an encoding level of a=j+1 by assigning j+1 character codes having p bits, c=(n/m)×(i+1) character codes having r bits, and b=n-(j+1)-((n/m)×(i+1)) character codes having q bits.

Claim 53

A dynamically variable data compression method, particularly useful in a series/sequential data transmission application such as a modem, comprising the steps of: (1) providing an alphabet of n characters to be employed in representing information, ranging from 0 to n; (2) arranging the n characters in an initial ordered array; (3) providing a first set of p-bit codes to be used for encoding a first predetermined number a of said n characters, a second set of q-bit codes to be used for encoding a second predetermined number b of said n characters, and a third set of r-bit codes to be used for encoding a third predetermined number of c of said n characters, where a+b+c=n; (4) providing a sequential input information stream represented by the characters of said alphabet to be encoded with said p-, said q-, or said r-bit codes; (5) for each item x of said sequential input information stream, taking the following steps: (i) providing a z bit code as an output chosen from said first or said second or said third set of codes as a function of the relative position in the array of the character corresponding to the item x, where z is p or q or r; (ii) incrementing a character count CC associated with the character of said alphabet which represents said particular item x of said sequential input information stream; (iii) comparing the character count CC with the character count associated with each character within a predetermined range lower in the array, up to a total of d places lower in the array, where d is a predetermined number less than n; (iv) when the character count CC is found upon comparison to be greater than or equal to the character count for a character lower in the array within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character lower in the array within said predetermined range having the equal or lesser character count; (6) after every k characters of said sequential input information stream, changing the "encoding level" represented by the relative values of the numbers a, b, and c by taking the following steps: (i) summing the character counts for consecutive groups of m characters to obtain a plurality of n/m group counts; (ii) comparing the group count for group (n/m)-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; (iii) if the group count for group (n/m)--1 is less than the character count for character j, then, incrementing i and j and going back to the step 6(ii); (iv) if the group count for group (n/m)-i-1 is greater than or equal to the character count for character j, then establishing an encoding level of a=j+1 by assigning j+1 character codes having p bits, c=(n/m)×(i+1) character codes having r bits, and b=n-(j+1)-((n/m)×(i+1)) character codes having q bits.

Claim 54

The method of claim 44, wherein the alphabet is the ASCII character set, and n is 256.

Claim 55

The method of claim 44, wherein p<q<r.

Claim 56

The method of claim 46, wherein p is 4, q is 8, and r is 12.

Claim 57

The method of claim 44, wherein upon initialization, a is 4, b is 188, and c is 64.

Claim 58

The method of claim 44, wherein d is 16.

Claim 59

The method of claim 44, wherein k is 128.

Claim 60

The method of claim 44, wherein m is 16.

Claim 61

A dynamically variable data decompression method, particularly useful in a series/sequential data communications device such as a modem, comprising the steps of: (1) providing an alphabet of n d characters; (2) arranging the n d characters of the alphabet in an initial ordered array; (3) providing a first set of p d -bit codes to be used for decoding a first predetermined number a d of said n d characters, a second set of q d -bit codes to be used for decoding a second predetermined number b d of said n d characters, and a third set of r d -bit codes to be used for decoding a third predetermined number c d of said n d characters, where p d <q d <r d , and where a d +b d +c d =n d ; (4) receiving a sequential data stream over a communications link encoded as a z bit code of p-, q-, and r-bit codes, where p, q, and r correspond to p d , q d , and r d ; (5) for each item x of said sequential data stream, taking the following steps: (i) finding a match between the z bit code representing the item x and one of said codes associated with said alphabet of n d characters; (ii) providing as a decompressed output a character of said alphabet of n d characters which corresponds to the code representing the item x; (iii) incrementing a character count CC d associated with the character of said alphabet which represents the output character corresponding to the particular item x of the sequential data stream; (iv) comparing the character count CC d with the character count associated with each character within a predetermined range toward the beginning of the array of said alphabet, up to a total of d d places toward the beginning of the array; and (v) when the character count CC d is found upon comparison to be greater than or equal to the character count for a character toward the beginning of the array of said alphabet within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count; and (6) after every k d characters of said sequential data stream, changing the "decoding level" represented by the relative values of the numbers a d , b d , and c d by taking the following steps: (i) summing the character counts for consecutive groups of m d characters to obtain a plurality of n d /m d group counts; (ii) comparing the group count for group (n d /m d )-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the beginning of the array; (iii) if the group count for group (n d /m d )-i-1 is less than the character count for character j, then, incrementing i and j and going back to the step (6)(ii); and (iv) if the group count for group (n d /m d )-i-1 is greater than or equal to the character count for character j, then establishing a decoding level of a d =j+1 by assigning j+1 character codes having p d bits, c d =(n d /m d )×(i+1) character codes having r d bits, and b d =n d -(j+1)-((n d /m d )×(i+1)) character codes having q d bits.

Claim 62

A dynamically variable data decompression method, particularly useful in a series/sequential data communications device such as a modem, comprising the steps of: (1) providing an alphabet of n d characters; (2) arranging the n d characters of the alphabet in an initial ordered array; (3) providing a first set of p d -bit codes to be used for decoding a first predetermined number a d of said n d characters, a second set of q d -bit codes to be used for decoding a second predetermined number b d of said n d characters, and a third set of r d -bit codes to be used for decoding a third predetermined number c d of said n d characters, where p d <q d <r d , and where a d +b d +c d =n d ; (4) receiving a sequential data stream over a communications link encoded as a z bit code of p-, q-, and r-bit codes, where p, q, and r correspond to p d , q d , and r d ; (5) for each item x of said sequential data stream, taking the following steps: (i) finding a match between the z bit code representing the item x and one of said codes associated with said alphabet of n d characters; (ii) providing as a decompressed output a character of said alphabet of n d characters which corresponds to the code representing the item x; (iii) incrementing a character count CC d associated with the character of said alphabet which represents the output character corresponding to the particular item x of the sequential data stream; (iv) comparing the character count CC d with the character count associated with each character within a predetermined range toward the beginning of the array of said alphabet, up to a total of d d places toward the beginning of the array; and (v) when the character count CC d is found upon comparison to be greater than or equal to the character count for a character toward the beginning of the array of said alphabet within said predetermined range, exchanging the relative positions in the array of the character corresponding to the item x and the character toward the beginning of the array within said predetermined range having the equal or lesser character count; and (6) after every k d characters of said sequential data stream, changing the "decoding level" represented by the relative values of the numbers a d , b d , and c d by taking the following steps: (i) summing the character counts for consecutive groups of m d characters to obtain a plurality of n d /m d group counts; (ii) comparing the group count for group (n d /m d )-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the beginning of the array; (iii) if the group count for group (n d /m d )-i-1 is less than the character count for character j, then, incrementing i and j and going back to the step (6)(ii); and (iv) if the group count for group (n d /m d )-i-1 is greater than or equal to the character count for character j, then establishing a decoding level of a d =j+1 by assigning j+1 character codes having p d bits, c d =(n d /m d )×(i+1) character codes having r d bits, and b d =n d -(j+1)-((n d /m d )×(i+1)) character codes having q d bits.

Claim 63

A dynamically adjusting data compression method, comprising the steps of: (1) providing an encoding table having a plurality of sets of digital codes associated with characters of an alphabet, the digital codes being of the same length in a given set but of a different length between sets, the table being arranged in an initial ordered array of increasing code lengths; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in response to the presented item of data, selecting a code from one of the sets in the the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; (5) in further response to the presented item of data, maintaining a statistical record of the probability of occurrence of the character representing the presented item of data; (6) in further response to the presented item of data, exchanging the position in the array of the character representing the presented item of data with a character having a lower probability of occurrence such that a character having a higher probability of occurrence will move to a position in the array more likely to be associated with a shorter code; and (7) periodically adjusting the sizes of the sets of digital codes a function of the probability of occurrence of the characters associated with the sets.

Claim 64

A dynamically adjusting data compression method, comprising the steps of: (1) providing an encoding table having a plurality of sets of digital codes associated with characters of an alphabet, the digital codes being of the same length in a given set but of a different length between sets, the table being arranged in an initial ordered array of increasing code lengths; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in response to the presented item of data, selecting a code from one of the sets in the the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; (5) in further response to the presented item of data, maintaining a statistical record of the probability of occurrence of the character representing the presented item of data; (6) in further response to the presented item of data, exchanging the position in the array of the character representing the presented item of data with a character having a lower probability of occurrence such that a character having a higher probability of occurrence will move to a position in the array more likely to be associated with a shorter code; and (7) periodically adjusting the sizes of the sets of digital codes a function of the probability of occurrence of the characters associated with the sets.

Claim 65

A dynamically adjusting data decompression method, comprising the steps of: (1) providing a decoding table having a plurality of sets of digital codes associated with characters of the alphabet, the digital codes being of the same length in a given set but of a different length between sets, the table being arranged in an initial ordered array of increasing code lengths; (2) presenting for decoding an item of coded data represented by one of the digital codes; (3) in response to the presented item of coded data, selecting a character from one of the sets in the decoding table which corresponds to the particular digital code represented by the item of coded data; (4) providing the selected character as a decoded output; (5) in further response to the presented item of coded data, maintaining a statistical record of the probability of occurrence of the character resultant from decoding; (6) in further response to the presented item of coded data, exchanging the position in the decoding array of the decoded character with a character having a lower probability of occurrence such that a character having a higher probability of occurrence will move to a position in the array more likely to be associated with a shorter code; and (7) periodically adjusting the sizes of the sets as a function of the probability of occurrence of the characters associated with the sets.

Claim 66

A dynamically adjusting data decompression method, comprising the steps of: (1) providing a decoding table having a plurality of sets of digital codes associated with characters of the alphabet, the digital codes being of the same length in a given set but of a different length between sets, the table being arranged in an initial ordered array of increasing code lengths; (2) presenting for decoding an item of coded data represented by one of the digital codes; (3) in response to the presented item of coded data, selecting a character from one of the sets in the decoding table which corresponds to the particular digital code represented by the item of coded data; (4) providing the selected character as a decoded output; (5) in further response to the presented item of coded data, maintaining a statistical record of the probability of occurrence of the character resultant from decoding; (6) in further response to the presented item of coded data, exchanging the position in the decoding array of the decoded character with a character having a lower probability of occurrence such that a character having a higher probability of occurrence will move to a position in the array more likely to be associated with a shorter code; and (7) periodically adjusting the sizes of the sets as a function of the probability of occurrence of the characters associated with the sets.

Claim 67

A dynamic data compression method, comprising the steps of: (1) providing an encoding table having a plurality of sets of digital codes associated with characters of an alphabet, the digital codes being of different lengths between sets; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in response to the presented item of data, selecting a code from one of the sets in the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; and (5) periodically adjusting the sizes of the sets of digital codes in the encoding table as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters presented for encoding, whereby the numbers of characters represented by different digital codes varies as a function of the frequency of occurrence of characters in the data presented for encoding.

Claim 68

A dynamic data compression method, comprising the steps of: (1) providing an encoding table having a plurality of sets of digital codes associated with characters of an alphabet, the digital codes being of different lengths between sets; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in response to the presented item of data, selecting a code from one of the sets in the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; and (5) periodically adjusting the sizes of the sets of digital codes in the encoding table as a function of the frequency of occurrence of characters of the alphabet over a plurality of characters presented for encoding, whereby the numbers of characters represented by different digital codes varies as a function of the frequency of occurrence of characters in the data presented for encoding.

Claim 69

The method of claim 55, wherein the step of periodically adjusting the sizes of the sets comprises the steps of: (1) summing character counts for predetermined groups of consecutive characters to obtain a plurality of group counts; (2) comparing the group count for groups towards the end of the array with the character counts for characters towards the beginning of the array; (3) increasing the size of the set of the shortest digital codes until there is a correspondence between a group count and a character count at the end of the set of shortest digital codes, whereby the size of the set of the shortest digital codes is increased to include more characters having a higher probability of occurrence than any the characters in the set of codes associated with the group counts.

Claim 70

The method of claim 56, wherein there are at least three sets of digital codes, and wherein the set associated with the longest digital codes increases in size in increments of the size of the groups while the set associated with the shortest codes increases in size in increments of a single character.

Claim 71

The method of claim 55, wherein the step of periodically adjusting the sizes of the sets is repeated after the occurrence of a predetermined number of items of data presented for encoding.

Claim 72

The method of claim 58, wherein the predetermined number of items between adjustments to the size of the sets is 128.

Claim 73

The method of claim 55, wherein there are n characters in the alphabet, wherein a first set associated with the shortest digital code has a members, and a second set associated with the longest digital code has c members, and wherein the step of periodically adjusting the sizes of the sets comprises changing the relative values of the numbers a and c by taking the following steps: (i) summing character counts for consecutive groups of m characters to obtain a plurality of n/m group counts, said character counts corresponding to frequency of occurrence statistics accumulated over a plurality of characters processed with the method; (ii) comparing the group count for group (n/m)-i-1 to the character count for character j, where i is an integer index of group counts beginning at zero and j is an integer index into the array beginning at zero at the top of the array; (iii) if the group count for group (n/m)-i-1 is less than the character count for character j, then, incrementing i and j and going back to the step (ii); (iv) if the group count for group (n/m)-i-1 is greater than or equal to the character count for character j, then establishing an encoding level of a=j+1 by assigning j+1 of the shortest digital codes, and c=(n/m)×(i+1) of the longer digital codes.

Claim 74

The method of claim 60, wherein there is a set of characters having digital codes sized in between the shortest digital code and the longest digital code and having b members, and wherein b=n-(j+1)-((n/m)×(i+1)).

Claim 75

A dynamic data compression method, comprising the steps of: (1) providing an encoding table having a plurality of digital codes of varying lengths associated with characters of an alphabet, said encoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with shorter codes toward the beginning of the array and longer codes toward the end of the array; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in resoponse to the presented item of data, selecting a code from one of the sets in the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; (5) in further response to the presented item of data, incrementing a character count corresponding to the frequency of occurrence of the particular character of the alphabet represented by the presented item of data; (6) in further response to the presented item of data, after incrementing the particular character's character count, comparing the particular character's character count to a character count for a preselected character in the array within a predetermined number of positions toward the beginning of the array; and (7) if the particular character's character count is greater than the character count for the preselected character, exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count with a position in the array more likely to be associated with a shorter code, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 76

A dynamic data compression method, comprising the steps of: (1) providing an encoding table having a plurality of digital codes of varying lengths associated with characters of an alphabet, said encoding table comprising an initial ordered array of the characters in the alphabet and their corresponding digital codes, with shorter codes toward the beginning of the array and longer codes toward the end of the array; (2) presenting for encoding an item of data represented by one of the characters of the alphabet; (3) in resoponse to the presented item of data, selecting a code from one of the sets in the encoding table which corresponds to the particular character of the alphabet represented by the presented item of data; (4) providing the selected code as an output; (5) in further response to the presented item of data, incrementing a character count corresponding to the frequency of occurrence of the particular character of the alphabet represented by the presented item of data; (6) in further response to the presented item of data, after incrementing the particular character's character count, comparing the particular character's character count to a character count for a preselected character in the array within a predetermined number of positions toward the beginning of the array; and (7) if the particular character's character count is greater than the character count for the preselected character, exchanging the relative positions in the array of the character just encoded with the preselected character so as to associate the character having the larger character count with a position in the array more likely to be associated with a shorter code, whereby as the frequency of occurrence of characters over a plurality of characters presented for encoding changes, the more frequently occurring characters become associated with shorter codes in the encoding table.

Claim 77

The method of claim 62, wherein the predetermined number of positions is sixteen.