Stem for dynamically compressing and decompressing electronic data

• US 4,876,541 A
• Filed: 10/15/1987
• Issued: 10/24/1989
• Est. Priority Date: 10/15/1987
• Status: Expired due to Term

• Current Assignee: James A. Storer
• Original Assignee: Data Compression Corporation
• Inventors: Storer, James A.
• Primary Examiner(s): Shoop, Jr., William M.
• Assistant Examiner(s): Hoff, Marc S.
• Application Number:
  US07/108,929
• Time in Patent Office: 740 Days
• Field of Search: 340/347 DD, 358/261, 341/51, 341/65, 341/67, 341/69, 341/106
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A data compression system for encoding and decoding textual data, including an encoder for encoding the data and for a decoder for decoding the encoded data. Both encoder and decoder have dictionaries for storing frequently-appearing strings of characters. Each string is identified by a unique pointer. The input data stream is parsed and matched with strings in the encoder dictionary using a novel matching algorithm. The pointer associated with the matched string is then transmitted to a remote location for storage or decoding. Thereafter, using a novel update algorithm the encoder dictionary is updated to include new strings of data based on the matched string of data. If required, a novel deletion algorithm is employed to remove infrequently used strings of data to provide room for the newly generated strings of data. The strings of data may be arranged using a modified least recently used queue.

The decoder matches each unique pointer in the stream of compressed input data with a corresponding pointer in the decoder dictionary. The decoder then transmits the string of character data associated with the matched pointer, thereby providing textual data in original, uncompressed form. Thereafter, using the novel update and deletion algorithms, new strings of data are added to, and old strings of data are deleted from, the decoder dictionary, so as to ensure both encoder and decoder dictionaries contain identical strings of data.

Claims

1. An apparatus for dynamically compressing and decompressing an input stream of data characters into a compressed stream code and for decompressing said compressed stream of code into uncompressed data characters, the apparatus comprising:

first dictionary means for storing a first plurality of strings of data characters, said first dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said first plurality of strings, wherein said first plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said first plurality of strings;

second dictionary means for storing a second plurality of strings of data characters, said second dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said second plurality of strings, wherein said second plurality of strings comprises an initial set of unique data characters that is identical to said initial set of unique data characters in said first plurality of strings, with each character in said initial set in said second plurality of strings being positioned in the one of said second plurality of strings that is identified by the same unique code as the string in said first plurality of strings in which the identical character from said initial set of characters in said first plurality of strings is positioned;

first match means for receiving and parsing said input stream of data characters into parsed strings of data characters and for comparing each of said parsed strings of data characters with said first plurality of strings so as to locate the one of said first plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one of said parsed strings is identified as the current match;

first transmitting means for transmitting the one of said plurality of unique codes identifying the one of said first plurality of stored strings that matches said current match, for each current match;

second match means for receiving said one unique code transmitted by said first transmitting means for each current match, and for comparing each said one unique code with said plurality of unique codes identifying said second plurality of strings so as to locate the one of said plurality of unique codes in said second dictionary means that matches said each said one unique code received from said first transmitting means;

second transmitting means for transmitting the string of character data in said second plurality of strings identified by the one of said plurality of unique codes in said second dictionary means that matches said one unique code received from said first transmitting means, for each string of character data matched by said second match means;

first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique codes to each of said new strings; and

second update means for adding said N new strings of data characters to said second dictionary means for each current match, including means for assigning the same one of said plurality of unique codes to each of said N new strings added to said second dictionary means that is assigned to corresponding respective ones of said N new strings added to said first dictionary means.

2. An apparatus according to claim 1, further wherein said first match means parses said input data stream so that each of said parsed strings is the longest string possible that will match a corresponding one of said first plurality of stored strings.

3. An apparatus according to claim 1, further comprising:

input buffer means for storing a portion of said input data stream; and

limited lookahead means for comparing said portion of said input data stream with said first plurality of strings stored in said first dictionary means so as to choose a parsing of said portion that, over time, allows said input data stream to be represented with substantially the fewest number of said plurality of unique codes possible, wherein a string from said portion chosen by said parsing of said portion is used as the current match.

4. An apparatus according to claim 3, further wherein:

said input buffer means comprises a looksize portion sized to hold from between 2 to 100 characters of input data and a maxmatch portion adjacent said looksize portion sized to hold from between 1 to 1000 characters of input data, wherein said maxmatch portion contains only character data forming part of a string of data that begins in the looksize portion and extends into the maxmatch portion; and

said limited lookahead means comprises comparison means for;

(a) matching various strings of characters at least partially contained in said looksize portion with said first plurality of strings in said first dictionary means, and determining the number of bits required to represent each of said various strings of characters in compressed form by (1) determining the number of bits required to represent each of said plurality of unique codes identifying the ones of said first plurality of strings that match corresponding respective ones of said various strings of characters, and (2) determining the number of bits required to represent each of said various strings of characters in uncompressed form;

(b) calculating a compression ratio for each of said various strings of characters by dividing the number of bits required to represent said each of said various strings in compressed form by the number of bits required to represent said each of said various string in uncompressed form;

(c) comparing the compression ratios for each of said various strings of characters with others of said various strings so as to determine a parsing of said various strings that requires the fewest possible of said plurality of unique codes to represent said various strings in compressed form; and

(d) using one of said various strings of characters as said current match.

5. An apparatus according to claim 4, wherein said looksize portion holds about 8 characters and said maxmatch portion holds about 25 characters.

6. An apparatus according to claim 1,

wherein said strings in said first plurality of strings containing said characters of the initial set together define an array, and wherein said array comprises a plurality of unique root nodes and each of said unique root nodes contains a character from said initial set, and wherein each of said first plurality of strings depends from one of said plurality of unique root nodes, further wherein the number of said first plurality of strings that depend from a single root node is equal to about the number of characters in said initial character set;

and

wherein said strings in said second plurality of strings containing said characters of the initial sot together define an array, and wherein said array comprises a plurality of unique root nodes and each of said unique root nodes contains a character from said initial set, and wherein each of said second plurality of strings depends from one of said plurality of unique root nodes, further wherein the number of said second plurality of strings that depend from a single root node is equal to about the number of characters in said initial set of characters.

7. An apparatus according to claim 6, wherein said arrays in said first and second dictionary means each comprise about 256 root nodes.

8. An apparatus according to claim 6, wherein each character in said first and second plurality of strings, except for the characters contained in the root nodes of said first and second plurality of strings, is positioned at a descendant node, further wherein the number of descendant nodes that are permitted to depend from any given descendant node is equal to about 5 to 10 percent of the total number of root nodes in said array.

9. An apparatus according to claim 8, only about 12 to 25 descendant nodes are permitted to depend from any given descendant node.

10. An apparatus according to claim 1, wherein said first and second update means each comprise deletion means for deleting strings of data from said first and second dictionary means, respectively, so as to provide room for said N new strings of data added to said first and second dictionary means.

11. An apparatus according to claim 10, wherein said first and second dictionary means are each initialized with a set of characters prior to the receipt by said first match means of the first string in said input stream, and further wherein said deletion means of said first and second dictionary means never delete said initialized set of characters from said first and second dictionary means, respectively.

12. An apparatus according to claim 10, wherein said first and second plurality of strings are arranged in said first and second dictionary means, respectively, in a least recently used queue by successively increasing frequency of use, with the least frequently used ones of said first and second plurality of strings being positioned at the end of the queue and the most frequently used ones of said first and second plurality of strings being positioned at the front of the queue.

13. An apparatus according to claim 10, wherein said first and second plurality of strings each comprise a selected number of strings and wherein each of said first and second plurality of strings is arranged in a modified least recently used queue that is organized so that:

(a) said last current match and current match prefix concatenations are positioned after said prefixes of said current match;

(b) said last current match and current match prefix concatenations are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes, and said current match prefixes are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes;

(c) said current match prefixes are positioned at the beginning of said queue, except when said current match follows one of said initial set of characters in which case said current match prefixes are positioned after said last match and current match prefix concatenations;

(d) said characters of the initial set are not included in said queue;

(e) if a prefix of a last match and current match concatenation or a prefix of a current match is already in said queue said prefix is deleted from said queue when said N new strings are added to said first and second dictionary means; and

(f) strings are deleted from the end of said queue to provide room for N new strings whenever the total number of strings in said first and second dictionary means exceeds said selected number.

14. An apparatus according to claim 10, wherein each character in said first and second plurality of strings, except for the characters contained in the root nodes of said first and second plurality of strings, is positioned at a descendant node, and wherein each of said plurality of strings is arranged in a modified least recently used queue that is organized so that the ancestors of any given descendant node positioned closer to the front of said modified least recently used queue than said given descendant node.

15. An apparatus according to claim 1, wherein each of said current matches is represented by data bits, and wherein each of said unique codes in said first and second dictionary means is represented by a selected number of data bits and said selected number is related to the number of strings in said first and second plurality of strings, said first and second plurality of strings each having an identical number of strings, further wherein said apparatus comprises:

means for computing the rate of data compression achieved by said apparatus by dividing, for each current match, the number of bits in said unique code identifying the one of said first plurality of strings that matches said each current match by the number of bits in said each current match;

first means for varying the number of strings in said first plurality of strings pursuant to said rate of data compression achieved by said apparatus so as to maximize said rate of data compression achieved by said apparatus; and

second means for varying the number of strings in said second plurality of strings whenever said first means varies the number of strings in said first plurality of strings so that said first and second plurality of strings comprise identical numbers of strings.

16. An apparatus according to claim 1 further comprising means for increasing or decreasing the number of strings in said first and second plurality of strings so as to minimize the number of said unique codes required to represent a given number of input stream data characters.

17. An apparatus according to claim 1 further comprising:

a first downsize dictionary that is identical to and performs the same functions as said first dictionary means, except that said first downsize dictionary contains half as many strings in its first plurality of strings as said first dictionary means;

a first upsize dictionary that is identical to and performs the same functions as said first dictionary means, except that said first upsize dictionary contains twice as many strings in its first plurality of strings as said first dictionary means;

a second downsize dictionary that is identical to and performs the same functions as said second dictionary means, except that said second downsize dictionary contains half as many strings in its second plurality of strings as said second dictionary means;

a second upsize dictionary that is identical to and performs the same functions as said second dictionary means, except that said second upsize dictionary contains twice as many strings in its second plurality of strings as said second upsize dictionary means;

further wherein;

(a) said first match means additionally compares each of said parsed strings with the first plurality of strings stored in said first downsized dictionary and said first upsize dictionary so as to locate that one of said stored strings, for both said first downsize dictionary and said first upsize dictionary, that matches a corresponding one of said parsed strings, and wherein the most recently matched one of said parsed strings in said first downsized dictionary is identified as the downsized current match and wherein the most recently matched one of said parsed strings in said first upsize dictionary is identified as the upsize current match;

(b) said first transmitting means transmit the unique codes identifying the three ones of said first plurality of strings stored in said first dictionary means, said first downsize dictionary, and said first upsize dictionary that match, respectively, said current match, said downsize current match, and said upsize current match, wherein said unique codes identifying said three ones of said first plurality of strings stored in said first dictionary means, said first downsize dictionary, and said first upsize dictionary are together identified as the match code;

(c) said second match means compares, respectively, said three ones of said strings in said match code with said unique codes identifying said second plurality of strings in said second dictionary means, said second downsize dictionary, and said second upsize dictionary, so as to locate, respectively, the three ones of said unique codes in said second dictionary means, said second downsize dictionary, and said second upsize dictionary that match, respectively, said three ones of said first plurality of strings in said match code received from said first transmitting means;

(d) said second transmitting means transmits the strips of character data identified by said three ones of said unique code in said second dictionary means, said second downsize dictionary, and said second upsize dictionary, that match, respectively, said three ones of said first plurality of strings in said match code;

(e) said first update means additionally adds said N new strings of data to said first downsize dictionary, and said first upsize dictionary;

(f) said second update means additionally adds said N new strings of data to said second downsize dictionary and said second upsize dictionary;

said apparatus additionally comprising;

dictionary comparison means for comparing the number of characters in said current match, said downsize current match, and said upsize current match, with, respectively, (a) the number of characters in the unique code identifying the one of said first plurality of strings in said first dictionary means that matches said current match, (b) the number of characters in the unique code identifying the one of said first plurality of strings in said first downsize dictionary that matches said downsize current match, and (c) the number of characters in the unique code identifying the one of said first plurality of strings in said first upsize dictionary that matches said upsize current match, so as to determine the rates of data compression achieved using, respectively, said first dictionary means, said first downsize dictionary, and said first upsize dictionary;

means for reducing the number of strings in said first plurality of strings in said first dictionary means by one half if a higher rate of data compression is achieved using said first downsize dictionary than is achieved using said first dictionary means;

means for doubling the number of strings in said first plurality of strings in said first dictionary means if a higher rate of compression is achieved using said first upsize dictionary than is achieved using said first dictionary means;

means for changing the number of strings in said second dictionary means whenever said means for reducing or said means for doubling changes the number of strings in said first plurality of strings in said first dictionary means, so that said second dictionary means contains the same number of strings in its second plurality of strings as said first dictionary means.

43. An apparatus according to claim 1, further comprising bypass means for passing said input stream of data characters through said apparatus so that said data is neither compressed or decompressed.

46. An apparatus according to claim 1, wherein said deletion means of said first and second dictionary means each comprise means for selecting a special set of characters, wherein characters in said special set of characters are never deleted from said first and second dictionary means.

47. An apparatus according to claim 1, said first update means and said second update means each comprising maxmatch means for limiting the length of each of said N new strings of data characters to maxmatch characters long, wherein maxmatch ranges from 1 to the number of strings in said plurality of strings in said first and second dictionary means.

48. An apparatus according to claim 47, wherein maxmatch ranges from 10 to 100.

53. An apparatus according to claim 1 wherein said apparatus is designated to operate in either a compression mode or a decompression mode, further wherein said apparatus comprises means for switching said apparatus (a) to said compression mode upon receipt of a first signal in said input stream of data characters and (b) to said decompression mode upon receipt of a second signal in said input stream.

18. An apparatus for dynamically compressing an input stream of data characters into a stream of compressed code, and for dynamically decompressing said stream of compressed code into said input stream of data characters, the apparatus comprising:

encoder module means for encoding said stream of characters and for transmitting said stream of characters in encoded form;

decoder module means for decoding said encoded stream of characters and for transmitting said stream of characters in uncoded form;

wherein said encoder module means and said decoder module means each comprise;

dictionary means for storing a plurality of strings of said characters, wherein each of said plurality of strings has a unique address;

first match means (1) for receiving said input stream of data characters, (2) for matching strings of characters from said input stream of characters with ones of said plurality of strings of characters in said dictionary means in said encoder module, and (3) for transmitting the address of matched ones of said plurality of strings;

second match means for (1) receiving the addresses of strings with which matches have been made, (2) matching said each of said addresses with the addresses of said plurality of strings in said dictionary means in said decoder module, and (3) transmitting the characters in those of said plurality of strings having addresses that match said addresses received by said second match means;

update means for updating said dictionary means in said encoder module and said decoder module so that said plurality of strings stored therein contain strings of characters frequently present in said stream of characters, and for concatenating the last matched string with the currently matched string; and

deletion means for deleting from said plurality of strings of characters in said dictionary means in said encoder module and in said dictionary means in said decoder module those strings with which strings of characters from said input stream are approximately least frequently matched by arranging said plurality of strings in said dictionary means in said encoder and decoder modules in a reverse order arrangement with the currently matched strings appearing after said concatenation of the last matched string and the currently matched string.

54. An apparatus according to claim 18 wherein said apparatus is designated to operate in either a compression mode or a decompression mode, further wherein said apparatus comprises means for switching said apparatus (a) to said compression mode upon receipt of a first signal in said input stream of data characters and (b) to said decompression mode upon receipt of a second signal in said input stream.

19. An apparatus for dynamically compressing an input stream of data characters into a compressed stream of code, the system comprising:

dictionary means for storing a plurality of strings of data characters, said dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said plurality of strings, wherein said plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said plurality of strings;

match means for receiving and parsing said input stream of data characters into parsed strings and for comparing each of said parsed strings of data characters with said plurality of strings in said dictionary means so as to locate the one of said stored plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one on said parsed strings is identified as the current match;

transmitting means for transmitting said unique code identifying the one of said plurality of stored strings that matches said current match; and

update means for adding N new strings of data characters to said dictionary means, wherein N equals the number of characters current match concatenated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique address codes to each of said N new strings.

20. An apparatus according to claim 19, further wherein said match means parses said input data stream so that each of said parsed strings is the longest string possible that will match a corresponding one of said plurality of stored strings.

21. An apparatus according to claim 19, further comprising:

input buffer means for storing a portion of said input data stream; and

limited lookahead means for comparing said portion of said input data stream with said plurality of strings stored in said dictionary means so as to choose a parsing of said portion that, over time, allows said input data stream to be represented with substantially the fewest number of said plurality of unique codes possible, wherein a string from said portion closed by said parsing of said portion is used as the current match.

22. An apparatus according to claim 21, further wherein:

said input buffer means comprises a looksize portion sized to hold from between 2 to 100 characters of input data and a maxmatch portion adjacent said looksize portion sized to hold from between 1 to 1000 characters of input data, wherein said maxmatch portion contains only character data forming part of a string of data that begins in the looksize portion and extends into the maxmatch portion; and

said limited lookahead means comprises comparison means for;

(a) matching various strings of characters at least partially contained in said looksize portion with said plurality of stored strings in said dictionary means, and determining the number of bits required to represent each of the various strings of characters in compressed form by (1) determining the number of bits required to represent each of the plurality of unique codes associated with the ones of said plurality of stored strings that match corresponding respective ones of said various strings of characters, and (2) determining the number of bits required to represent each of said various strings of characters in uncompressed form;

(b) calculating a compression ratio for each of said various strings of characters by dividing the number of bits required to represent said each of said various strings in compressed form by the number of bits required to represent said each of said various string in uncompressed form;

(c) comparing the compression ratios for each of said various strings of characters with others of said various strings so as to determine a parsing of said various strings that requires the fewest possible of said plurality of unique codes to represent said various strings in compressed form; and

(d) using one of said various strings of characters as said current match.

23. An apparatus according to claim 22, wherein said looksize portion holds about 8 characters and said maxmatch portion holds about 25 characters.

24. An apparatus according to claim 19,

wherein said strings in said plurality of strings containing said characters of the initial set in said dictionary means together define an array, and wherein said array comprises a plurality of unique root nodes and each of said unique root nodes contains a character from said initial set, and wherein each of said plurality of strings depends from one of said plurality of unique root nodes, further wherein the number of said plurality of strings that depend from a single root node is equal to about the number of characters in said initial character set.

25. An apparatus according to claim 24, wherein said array in said dictionary means comprises about 256 root nodes.

26. An apparatus according to claim 24, wherein each character in said plurality of strings in said dictionary means, except for the characters contained in the root node of said plurality of strings, is positioned at a descendant node, further wherein the number of descendant nodes that are permitted to depend from any given descendant node is equal to about 5 to 10 percent of the total number of root nodes in said array.

27. An apparatus according to claim 26, wherein only about 12 to 25 descendant nodes are permitted to depend from any given descendant node.

28. An apparatus according to claim 19, wherein said update means comprises deletion means for deleting strings of data from said dictionary means so as to provide room for said N new strings of data added to said dictionary means.

29. An apparatus according to claim 28, wherein said dictionary means is initialized with a set of characters prior to the receipt by said match means of the first string in said input stream, and further wherein said deletion means never deletes said initialized set of characters from said dictionary means.

30. An apparatus according to claim 28, wherein said plurality of strings in said dictionary means are arranged in a least recently used queue, with said plurality of strings being arranged in the queue by successively increasing frequency of use, with the least frequently used one of said plurality of strings being positioned at the end of the queue and the most frequently used one of said plurality of strings being positioned at the front of the queue.

31. An apparatus according to claim 28, wherein said plurality of strings in said dictionary means comprises a selected number of strings and wherein said plurality of strings is arranged in a modified least recently used queue that is organized so that;

(a) said last current match and current match prefix concatenations are positioned after said prefixes of said current match;

(b) said last current match and current match prefix concatenations are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes, and said current match prefixes are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes;

(c) said current match prefixes are positioned at the beginning of said queue, except when said current match follows one of said initial set of characters in which case said current match prefixes are positioned after said last current match and current match prefix concatenations;

(d) said characters of the initial set are not included in said queue;

(e) if a prefix of a last current match and current match concatenation or a prefix of a current match is already in said queue said prefix is deleted from said queue when said N new strings are added to said dictionary means; and

(f) strings are deleted from the end of said queue to provide room for N new strings whenever the total number of strings in said dictionary means exceeds said selected number.

32. An apparatus according to claim 28, wherein each character in said plurality of strings in said dictionary means is positioned at a descendant node, and wherein each of said plurality of strings is arranged in a modified least recently used queue that is organized so that the ancestors of any given descendant node are positioned closer to the front of said modified least recently used queue than said given descendant node.

33. An apparatus according to claim 19, wherein each of said current matches is represented by data bits, and wherein each of said unique codes in said dictionary means is represented by a selected number of data bits and said selected number is related to the number of strings in said plurality of strings in said dictionary means, further wherein said apparatus comprises:

means for computing the rate of data compression achieved by said apparatus by dividing, for each current match, the number of bits in said unique code identifying the one of said plurality of strings in said dictionary means that matches said each current match by the number of bits in said each current match;

means for varying the number of strings in said plurality of strings in said dictionary means pursuant to said rates of data compression achieved by the apparatus so as to maximize the rates of data compression achieved by the apparatus

34. An apparatus according to claim 19, further comprising means for increasing or decreasing the number of said plurality of strings in said dictionary means so as to minimize the number of said unique codes required to represent a given number of input stream data characters.

44. An apparatus according to claim 19, further comprising bypass means for passing said input stream of data characters through said apparatus so that said data is neither compressed or decompressed.

49. An apparatus according to claim 19, said update means further comprising maxmatch means for limiting the length of each of said N new strings of data to maxmatch characters long, wherein maxmatch ranges from 1 to the number of strings in said plurality of strings in said first and second dictionary means.

50. An apparatus according to claim 49, wherein maxmatch ranges from 10 to 100.

35. A system for dynamically decompressing a compressed stream of code into uncompressed data characters, the system comprising:

dictionary means for storing a plurality of strings of data characters, said dictionary means comprising a plurality of unique codes for identifying a corresponding respective one of said plurality of strings, wherein said plurality of strings comprises an initial set of unique data characters, with each character in said initial set being positioned in a corresponding respective one of said plurality of strings;

match means for receiving said compressed stream code, and for comparing said stream of code with said plurality of unique codes identifying said plurality of strings in said dictionary means so as to locate the ones of said plurality of unique codes in said dictionary means that match corresponding ones of code in said stream of code received by said match means, wherein the most recently matched one of said plurality of unique codes in said dictionary means is identified as the current match;

transmitting means for transmitting the strings of character data identified by the ones of said plurality of unique codes in said dictionary that match said corresponding ones of said stream of code received by said match means; and

update means for adding N new strings of data characters to said dictionary means for each string of characters transmitted by said transmitting means, wherein N equals the number of characters in a current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match, and including means for assigning a unique address code to each of said new strings.

36. An apparatus according to claim 35, wherein said update means comprises deletion means for deleting strings of data from said dictionary means so as to provide room for said N new strings of data added to said dictionary means.

37. An apparatus according to claim 36, wherein said dictionary means is initialized with a set of characters prior to the receipt by said match means of the first string in said compressed stream of code, and further wherein said deletion means never deletes said initialized set of characters from said dictionary means.

38. An apparatus according to claim 35, wherein said plurality of strings in said dictionary means are arranged in a least recently used queue, with the strings being arranged in the queue by successively increasing frequency of use, with the least frequently used strings being positioned at the end of the queue and the most frequently used strings being positioned at the front of the queue.

39. An apparatus according to claim 35, wherein said plurality of strings in said dictionary means comprises a selected number of strings and wherein said plurality of strings is arranged in a modified least recently used queue that is organized so that:

(a) said last current match and current match prefix concatenations are positioned after said prefixes of said current match;

(b) said last current match and current match prefix concatenations are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes, and said current match prefixes are arranged by length, so that the shortest prefix appears before the next longest prefix, and successively longer prefixes appear thereafter, with the longest prefix being positioned after all shorter prefixes;

(c) said current match prefixes are positioned at the beginning of said queue, except when said current match follows one of said initial set of characterizing which case said current match prefixes are positioned after said last match and current match prefix concatenations;

(d) said characters of the initial set are not included in said queue;

(e) if a prefix of a last match and current match concatenation or a prefix of a current match is already in said queue said prefix is deleted from said queue when said N new strings are added to said dictionary means; and

(f) strings are deleted from the end of said queue to provide room for N new strings whenever the total number of strings in said dictionary means exceeds said selected number.

40. An apparatus according to claim 35, wherein each character in said plurality of strings in said dictionary means is positioned at a descendant node, and wherein each of said plurality of strings is arranged in a modified least recently used queue that is organized so that the ancestors of any given descendant node are positioned closer to the front of said modified least recently used queue than said given descendant node.

41. An apparatus according to claim 35, wherein each of said current matches is represented by data bits, and wherein each of said plurality unique codes in said dictionary means is represented by a selected number of data bits and said selected number is related to the number of strings in said plurality of strings in said dictionary means, further wherein said apparatus comprises:

means for computing the rate of data compression achieved by said apparatus by dividing, for each current match, the number of bits in said unique code identifying the one of said plurality of strings in said dictionary means that matches said each current match by the number of bits in said each current match;

means for varying the number of strings in said plurality of strings in said dictionary means pursuant to said rates of data compression achieved by the apparatus so as to maximize the rates of data compression achieved by the apparatus.

42. An apparatus according to claim 35, further comprising means for increasing or decreasing the number of said plurality of strings in said dictionary means so as to minimize the number of said unique codes required to represent a given number of input stream data characters.

45. An apparatus according to claim 35, further comprising bypass means for passing said input stream of data characters through said apparatus so that said data is neither compressed or decompressed.

51. An apparatus according to claim 35, said update means further comprising maxmatch means for limiting the length of each of said N new strings of data to maxmatch characters long, wherein maxmatch ranges from 1 to the number of strings in said plurality of strings in said first and second dictionary means.

52. An apparatus according to claim 51, wherein maxmatch ranges from 10 to 100.

55. An apparatus for dynamically compressing and decompressing an input stream of data characters into a compressed stream of code and for decompressing said compressed stream of code into uncompressed data characters, the apparatus comprising:

first dictionary means for storing a first plurality of strings of data characters, said first dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said first plurality of strings;

second dictionary means for storing a second plurality of strings of data characters, said second dictionary means comprising a plurality of unique codes each for identifying a corresponding respective one of said second plurality of strings;

first match means for receiving and parsing said input stream of data characters into parsed strings of data characters and for comparing each of said parsed strings of data characters with said first plurality of strings so as to locate the one of said first plurality of strings that matches a corresponding one of said parsed strings, wherein the most recently matched one of said parsed strings is identified as the current match;

first transmitting means for transmitting the one of said plurality of unique codes identifying the one of said first plurality of stored strings that matches said current match, for each current match;

second match means for receiving said one unique code transmitted by said first transmitting means for each current match, and for comparing each said one unique code with said plurality of unique codes identifying said second plurality of strings as to locate the one of said plurality of unique codes in said second dictionary means that matches said each one unique code received from said first transmitting means;

second transmitting means for transmitting the string of character data in said second plurality of strings identified by the one of said plurality of unique codes in said second dictionary means that matches said one unique code received from said first transmitting means, for each string of character data matched by said second match means;

first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concentrated with each non-empty prefix of said current match, and including means for assigning one of said plurality of unique codes to each of said new strings; and

second update means for adding said N new strings of data characters to said second dictionary means for each current match, including means for assigning the same one of said plurality of unique codes to each of said N new strings added to aid second dictionary means that is assigned to corresponding respective ones of said N new strings added to said first dictionary means.