Adaptive data compression method and apparatus

• US 4,862,167 A
• Filed: 02/24/1987
• Issued: 08/29/1989
• Est. Priority Date: 02/24/1987
• Status: Expired due to Term

• Current Assignee: Telogy Networks, Inc. (Texas Instruments, Inc.)
• Original Assignee: Hayes Microcomputer Products, Inc.
• Inventors: Copeland, John A. III
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): Hoff, Marc S.
• Application Number:
  US07/018,340
• Time in Patent Office: 917 Days
• Field of Search: 341/87, 341/95, 341/106, 341/107, 341/67
• US Class Current: 341/107
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

A method and apparatus for compressing data, particularly useful in a modem. The preferred method is implemented in a microprocessor within a modem, and dynamically adapts to changing data statistics. Parallel encoding and decoding tables are provided at the encoder and the decoder, and are updated for each character processed. Each table has a plurality of digital compression codes associated with characters of an alphabet. In response to an item of data presented for encoding, a compression code which corresponds to the character presented for encoding is selected using the encoding table. The selected compression code is provided as an output. Periodically, the association between the codes and the characters of the alphabet in the table is adjusted as a function of the frequency of occurrence of characters of the alphabet, over a plurality of characters. As the frequency of occurrence of characters presented for encoding changes, the more frequently occurring characters become associated with the shorter codes in the encoding table. By performing the same steps in the decoding table, the compression codes are used at the decoder to select a character of the alphabet, which is provided as a decoded output.

Claims

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15. The method of claim 14, where k is 128.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33. The method of claim 32, where k is 128.

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

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

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

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

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

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

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

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

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

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

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

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

47. The method of claim 44, wherein p<

q<

r.

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

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

50. The method of claim 44, wherein d is 16.

51. The method of claim 44, wherein k is 128.

52. The method of claim 44, wherein m is 16.

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

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

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

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

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

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

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

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

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

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

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

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

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