Lempel- Ziv data compression technique utilizing a dictionary pre-filled with frequent letter combinations, words and/or phrases

• US 5,951,623 A
• Filed: 08/06/1996
• Issued: 09/14/1999
• Est. Priority Date: 08/06/1996
• Status: Expired

• Current Assignee: Pinpoint Incorporated (Altitude Capital Partners)
• Original Assignee: Fred Herz, Jason M. Eisner, Jeffrey C. Reynar, Lyle Ungar
• Inventors: Herz, Fred, Eisner, Jason, Ungar, Lyle, Reynar, Jeffrey C.
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US08/692,474
• Time in Patent Office: 1,134 Days
• Field of Search: 364/715.02, 341/50, 341/51, 341/59, 341/60, 341/81, 341/82, 341/87, 341/95, 341/106, 341/55, 358/426, 358/261.1, 382/232
• US Class Current: 708/203
• CPC Class Codes: G06T 9/005 Statistical coding, e.g. Huffman, run length coding
• CPC Class Codes: H03M 7/3086 employing a sliding window, e.g. LZ77
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
• CPC Class Codes: H04N 19/93 Run-length coding

Abstract

An adaptive compression technique which is an improvement to Lempel-Ziv (LZ) compression techniques, both as applied for purposes of reducing required storage space and for reducing the transmission time associated with transferring data from point to point. Pre-filled compression dictionaries are utilized to address the problem with prior Lempel-Ziv techniques in which the compression software starts with an empty compression dictionary, whereby little compression is achieved until the dictionary has been filled with sequences common in the data being compressed. In accordance with the invention, the compression dictionary is pre-filled, prior to the beginning of the data compression, with letter sequences, words and/or phrases frequent in the domain from which the data being compressed is drawn. The letter sequences, words, and/or phrases used in the pre-filled compression dictionary may be determined by statistically sampling text data from the same genre of text. Multiple pre-filled dictionaries may be utilized by the compression software at the beginning of the compression process, where the most appropriate dictionary for maximum compression is identified and used to compress the current data. These modifications are made to any of the known Lempel-Ziv compression techniques based on the variants detailed in 1977 and 1978 articles by Ziv and Lempel.

Claims

1. A data compression method for compressing a text containing a sequence of characters, comprising the steps of:

(a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

(b) initializing a pointer to a first character in said sequence of characters for compression;

(c) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and determining a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary;

(d) storing a dictionary pointer to said longest match in said pre-filled data compression dictionary in a memory as a compressed representation of said characters making up said longest match;

(e) moving said pointer to a character in said sequence of characters which follows said longest match; and

(f) repeating steps c-e for all characters in said sequence of characters to be compressed.

2. A method as in claim 1, comprising the further step of creating said pre-filled data compression dictionary by performing the steps of:

analyzing character sequences in at least one sample sequence of characters which is representative of the sequence of characters to be compressed to determine the frequency of occurrence of said character sequences in said at least one sample sequence of characters; and

selecting as said predetermined combinations those character sequences in said at least one sample sequence of characters which occur most frequently in said at least one sample sequence of characters.

3. A method as in claim 2, wherein said analyzing step comprises the steps of determining a number of occurrences of each of said character sequences in said at least one sample sequence of characters and calculating for each character sequence a product of the number of occurrences of said each character sequence with the difference in bit length of said each character sequence and a bit length of said dictionary pointer.

4. A method as in claim 3, wherein said predetermined combinations selecting step comprises the step of selecting for storage in said pre-filled data compression dictionary those data sequences having the largest product determined in said product calculating step.

5. A method as in claim 4, comprising the further steps of determining whether an entire character set is present in said pre-filled data compression dictionary, and, in the event that all of the characters in said entire character set are not present in said pre-filled data compression dictionary, inserting those characters in said character set which are absent from said pre-filled data compression dictionary into said pre-filled data compression dictionary as new dictionary entries in place of dictionary entries having the smallest product determined in said product calculating step.

6. A method as in claim 1, wherein said step of selecting said pre-filled data compression dictionary comprises the steps of performing steps b-e for a subset of characters of said sequence of data characters to be compressed for a plurality of different pre-filled data compression dictionaries to determine which one of said plurality of different pre-filled data compression dictionaries provides the most compression for said subset of characters, and selecting said one pre-filled data compression dictionary as said pre-filled data compression dictionary for use in compressing said sequence of characters.

8. A method as in claim 1, comprising the further step of (g) transmitting to a recipient said dictionary pointer as said compressed representation of said characters making up said longest match.

9. A method as in claim 8, wherein said step of selecting said pre-filled data compression dictionary comprises the steps of selecting a pre-filled data compression dictionary out of a plurality of pre-filled data compression dictionaries based on whether or not said plurality of pre-filled data compression dictionaries are available to said recipient of data transmitted in step g.

10. A method as in claim 1, wherein said step of selecting a pre-filled data compression dictionary comprises the step of selecting multiple pre-filled data compression dictionaries for use during compression of said sequence of characters to be compressed.

11. A method as in claim 1, comprising the further step of encoding said dictionary pointer so that said dictionary pointer can be represented using fewer address bits.

12. A method as in claim 1, comprising the further step of storing with said compressed representation of said characters making up said longest match a reference to a pre-filled data compression dictionary to be used during a decompression process.

13. A method as in claim 1, comprising the further step of storing a plurality of pre-filled data compression dictionaries containing different genres of text data, wherein said pre-filled data compression dictionary selecting step comprises the step of selecting said pre-filled data compression dictionary from said plurality of pre-filled data compression dictionaries whereby the selected pre-filled data compression dictionary contains data from the most similar genre to said sequence of characters to be compressed.

14. A method as in claim 13, wherein said step of storing said plurality of pre-filled compression dictionaries comprises the step of arranging said plurality of pre-filled data compression dictionaries hierarchically by genre of text data contained within the respective pre-filled data compression dictionaries.

15. A method as in claim 13, wherein said step of storing said plurality of pre-filled compression dictionaries comprises the step of storing common entries in said plurality of pre-filled data compression dictionaries only one time on a storage medium whereby said common entries are shared by said plurality of pre-filled data compression dictionaries.

7. A method as in step 6, wherein said step of selecting said one pre-filled data compression dictionary comprises the step of selecting an empty data compression dictionary in the event that it is determined while performing steps b-e for said subset of characters of said sequence of data characters to be compressed that starting with an empty data compression dictionary would allow for the most compression of said sequence of data characters.

16. A data compression method for compressing a text containing a sequence of characters, comprising the steps of:

(a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

(b) initializing a data specific data compression dictionary;

(c) initializing a pointer to a first character in said sequence of characters for compression;

(d) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and said data specific data compression dictionary and determining a dictionary entry number of a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary and said data specific data compression dictionary;

(e) storing said dictionary entry number and an extension character in a memory as a compressed representation of said characters making up said longest match and said extension character, said extension character being that character in said sequence of characters to be compressed which occurs after said longest match starting at said pointer;

(f) selectively storing said characters making up said longest match and said extension character in said data specific data compression dictionary as a new dictionary entry;

(g) moving said pointer to a character in said sequence of characters which follows said extension character; and

(h) repeating steps d-g for all characters in said sequence of characters to be compressed.

17. A method as in claim 16, comprising the further steps of monitoring compression performance of said pre-filled data compression dictionary and said data specific data compression dictionary during compression of said sequence of characters and, when said data specific data compression dictionary becomes full during compression of said sequence of characters, resetting the data compression dictionary determined in said monitoring step to be providing the lesser data compression performance and using the data compression dictionary determined in said monitoring step to be providing the greater data compression performance as said pre-filled data compression dictionary for compression of subsequent characters in said sequence of characters to be compressed.

18. A method as in claim 16, comprising the further step of storing said data specific data compression dictionary with the new dictionary entries stored therein during compression of said sequence of characters as at least a portion of a pre-filled data compression dictionary for use in compression of a different sequence of characters.

19. A method as in claim 16, comprising the further step of storing with said compressed representation of said characters making up said longest match and said extension character at least one of (1) an indication of which pre-filled data compression dictionary was used to form said compressed representation;

(2) an indication of how dictionary address space is allocated between said data specific data compression dictionary and said pre-filled data compression dictionary, (3) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters, and (4) an indication of what technique to follow when said data specific data compression dictionary becomes filled.

20. A method as in claim 16, wherein said pre-filled data compression dictionary selecting step comprises the step of selecting said pre-filled data compression dictionary from a plurality of pre-filled data compression dictionaries containing different genres of text data, whereby the selected pre-filled data compression dictionary contains data from the most similar genre to said sequence of characters to be compressed.

21. A method as in claim 20, comprising the further step of repeating steps (b)-(g) for a different text from the same genre as said text using the data specific data compression dictionary formed during the compression of said text as the pre-filled data compression dictionary for compression of said different text.

22. A method as in claim 21, wherein said pre-filled data compression dictionary selecting step comprises the step of specifying whether the pre-filled data compression dictionary is formed during the compression of another text.

23. A data compression method for compressing a text containing a sequence of characters, comprising the steps of:

(a) initializing a character window which contains a predetermined number of characters;

(b) appending a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters to said character window;

(c) initializing a pointer to a first character in said sequence of characters for compression;

(d) comparing characters starting at said pointer with sequences of characters in said character window with said pre-filled data compression dictionary appended thereto and determining a window pointer to and a length of a longest match of said characters starting at said pointer with said sequences of characters in said character window with said pre-filled data compression dictionary appended thereto;

(e) storing said window pointer and said length of said longest match in a memory as a compressed representation of said characters making up said longest match;

(f) updating said character window to include the characters making up said longest match;

(g) moving said pointer to a character in said sequence of characters which follows said longest match; and

(h) repeating steps d-g for all characters in said sequence of characters to be compressed.

24. A method as in claim 23, comprising the further step of storing in said memory a literal character pointed to by said pointer when a sequence of characters pointed to by said pointer is not found in said character window with said pre-filled data compression dictionary appended thereto in step d.

25. A method as in claim 23, comprising the further step of transmitting to a recipient said window pointer and said length of said longest match as said compressed representation of said characters making up said longest match.

26. A data compression method for compressing a text containing a sequence of characters, comprising the steps of:

(a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

(b) initializing a character window which contains a predetermined number of characters;

(c) initializing a pointer to a first character in said sequence of characters for compression;

(d) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and with sequences of characters in said character window and determining longest matches of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary and with sequences of characters in said character window;

(e) determining whether greater compression will be obtained by representing said characters starting at said pointer as a dictionary entry number of a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary or by representing said characters starting at said pointer as a window pointer to and a length of a longest match of said characters starting at said pointer with said sequences of characters in said character window;

(f) storing said window pointer and said length of said longest match in a memory as a compressed representation of said characters making up said longest match when it is determined in step e that greater compression will be obtained by representing said characters starting at said pointer as said window pointer to and said length of said longest match of said characters starting at said window pointer with said sequences of characters in said character window;

otherwise storing said dictionary entry number of said longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary;

(g) updating said character window to include the characters making up said longest match;

(h) moving said pointer to a character in said sequence of characters which follows said longest match; and

(I) repeating steps d-h for all characters in said sequence of characters to be compressed.

27. A method as in claim 26, comprising the further step of transmitting to a recipient said window pointer and said length of said longest match when it is determined in step e that greater compression will be obtained by representing said characters starting at said pointer as said window pointer to and said length of said longest match of said characters starting at said window pointer with said sequences of characters in said character window;

otherwise transmitting to said recipient said dictionary entry number of said longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary.

28. A method of decompressing a compressed representation of a sequence of characters, said compressed representation comprising dictionary pointers to respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters stored in a pre-filled data compression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said decompressing method comprising the steps of:

(a) initializing a pointer to a first dictionary pointer in said compressed representation of said characters;

(b) retrieving a dictionary entry from said pre-filled data compression dictionary using said dictionary pointer pointed to by said pointer;

(c)storing said dictionary entry as a decompressed representation of the characters making up said longest match;

(d) moving said pointer to a next dictionary pointer in said compressed representation of said characters; and

(e) repeating steps b-d for all dictionary pointers in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

29. A method as in claim 28, comprising the further step of extracting from said compressed representation of said characters at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters.

30. A method of decompressing a compressed representation of a sequence of characters, said compressed representation comprising extension characters and dictionary entry numbers of respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters stored in a pre-filled data compression dictionary and a data specific data compression dictionary, said extension character being that character in the sequence of characters which occurs after the longest match starting at said pointer, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said decompressing method comprising the steps of:

(a) initializing a data specific data decompression dictionary;

(b) initializing a pointer to a first dictionary entry number in said compressed representation of said characters;

(c) retrieving a dictionary entry and an extension character from one of said pre-filled data compression dictionary and said data specific data decompression dictionary using a dictionary entry number pointed to by said pointer;

(d) selectively storing said characters making up said longest match and said extension character into said data specific data decompression dictionary;

(e) moving said pointer to a next dictionary entry number in said compressed representation of said characters; and

(f) repeating steps c-e for all dictionary entry numbers and extension characters in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

31. A method as in claim 30, comprising the further step of extracting from said compressed representation of said characters at least one of:

(1) an indication of the pre-filled data compression dictionary to use during decompression, (2) an indication of how dictionary address space is allocated between said data specific data compression dictionary and said pre-filled data compression dictionary, (3) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters, and (4) an indication of what technique to follow when said data specific data compression dictionary becomes filled.

32. A method of decompressing a compressed representation of a sequence of characters, said compressed representation comprising window pointers and lengths of respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters in a character window of a predetermined size with a pre-filled data compression dictionary appended thereto, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said decompressing method comprising the steps of:

(a) initializing a pointer to a first window pointer and length in said compressed representation of said characters;

(b) retrieving a number of characters determined by said length starting at a character within a current character window pointed to by a window pointer which is pointed to by said pointer;

(c) storing said retrieved characters as a decompressed representation of the characters making up said longest match;

(d) moving said pointer to a next window pointer and length in said compressed representation of said characters; and

(e) repeating steps b-d for all window pointers and lengths in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

33. A method as in claim 32, comprising the further step of extracting from said compressed representation of said characters at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters.

34. A method of decompressing a compressed representation of a sequence of characters, said compressed representation comprising (1) window pointers and lengths of respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters in a character window of a predetermined size and (2) dictionary entry numbers of respective longest matches of sequences of characters starting at said pointer to particular characters within a pre-filled data decompression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said decompressing method comprising the steps of:

(a) initializing a pointer to a first entry in said compressed representation of said characters;

(b) determining whether a current entry in said compressed representation of said characters pointed to by said pointer is (1) a window pointer and a length or (2) a dictionary entry number;

(c) if said current entry is a window pointer and a length, retrieving a number of characters determined by said length starting at a character within a current character window pointed to by said window pointer;

(d) if said current entry is a dictionary entry number, retrieving characters at a dictionary entry in said pre-filled data decompression dictionary identified by said dictionary entry number;

(e) storing characters retrieved in steps c or d as a decompressed representation of the characters making up the longest match for the current entry;

(f) moving said pointer to a next entry in said compressed representation of said characters; and

(g) repeating steps b-f for all entries in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

35. A method as in claim 34, comprising the further step of extracting from said compressed representation of said characters at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters.

36. A data compression system for compressing a text containing a sequence of characters, comprising:

a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

a memory which stores said text after it has been compressed; and

compressing means for performing the steps of (a) initializing a pointer to a first character in said sequence of characters for compression, (b) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and determining a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary, (c) storing a dictionary pointer to said longest match in said pre-filled data compression dictionary in said memory as a compressed representation of said characters making up said longest match, (d) moving said pointer to a character in said sequence of characters which follows said longest match, and (e) repeating steps b-d for all characters in said sequence of characters to be compressed.

37. A system as in claim 36, further comprising means for creating said pre-filled data compression dictionary, said pre-filled data compression dictionary creating means inserting into said pre-filled data compression dictionary those combinations of characters which most frequently occur in at least one sample sequence of characters which is representative of the sequence of characters to be compressed.

38. A system as in claim 37, wherein said pre-filled data compression dictionary creating means inserts into said pre-filled data compression dictionary those combinations of characters in at least one sample sequence of characters which is representative of the sequence of characters to be compressed which have the greatest product of (a) a number of occurrences of each of said combinations of characters in said at least one sample sequence of characters with (b) a difference in bit length of each said combination of characters and a bit length of said dictionary pointer.

39. A system as in claim 38, wherein said pre-filled data compression dictionary creating means determines whether an entire character set of said sequence of characters to be compressed is present in said pre-filled data compression dictionary, and, in the event that all of the characters in said entire character set are not present in said sequence of characters to be compressed, inserts those characters in said character set which are absent from said pre-filled data compression dictionary into said pre-filled data compression dictionary as new dictionary entries in place of dictionary entries which have the smallest product determined by said pre-filled data compression dictionary creating means.

40. A system as in claim 36, wherein said pre-filled data compression dictionary is one of a number of pre-filled data compression dictionaries, said one pre-filled data compression dictionary containing those combinations of characters which provide more compression of a subset of characters of said sequence of data characters to be compressed than the compression provided to said subset of characters of said sequence of data characters by each of the rest of said number of pre-filled data compression dictionaries.

41. A system as in claim 36, wherein said memory is at a location remote from said compressing means, further comprising means for transmitting said dictionary pointer as said compressed representation of said characters making up said longest match from said compressing means to said memory.

42. A system as in claim 41, wherein said pre-filled data compression dictionary is one of a number of pre-filled data compression dictionaries which is also available at said remote location.

43. A system as in claim 36, wherein said compressing means comprises means for encoding said dictionary pointer so that said dictionary pointer can be represented using fewer address bits.

44. A system as in claim 36, wherein said compressing means stores in said memory with said compressed representation of said characters making up said longest match a reference to a pre-filled data compression dictionary to be used during a decompression process.

45. A system as in claim 36, wherein said memory comprises at least one of a hard disk, a RAM, a CD ROM, a floppy disk, and an optical disk.

46. A system as in claim 36, further comprising a dictionary memory for storing a plurality of pre-filled data compression dictionaries containing different genres of text data, whereby the pre-filled data compression dictionary used to compress said text contains data from the most similar genre to said sequence of characters to be compressed.

47. A system as in claim 46, wherein said plurality of pre-filled data compression dictionaries are arranged in said dictionary memory hierarchically by genre of text data contained within the respective pre-filled data compression dictionaries.

48. A system as in claim 46, wherein said plurality of pre-filled data compression dictionaries are stored in said dictionary memory such that common entries in said plurality of pre-filled data compression dictionaries are stored in said dictionary memory only one time and are shared by said plurality of pre-filled data compression dictionaries.

49. A data compression system for compressing a text containing a sequence of characters, comprising:

a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

a data specific data compression dictionary;

a memory which stores said text after it has been compressed; and

compressing means for performing the steps of (a) initializing a pointer to a first character in said sequence of characters for compression, (b) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and said data specific data compression dictionary and determining a dictionary entry number of a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary and said data specific data compression dictionary, (c) storing said dictionary entry number and an extension character in said memory as a compressed representation of said characters making up said longest match and said extension character, said extension character being that character in said sequence of characters to be compressed which occurs after said longest match starting at said pointer, (d) selectively storing said characters making up said longest match and said extension character in said data specific data compression dictionary as a new dictionary entry, (e) moving said pointer to a character in said sequence of characters which follows said extension character, and (f) repeating steps b-e for all characters in said sequence of characters to be compressed.

50. A system as in claim 49, wherein said compressing means further comprises means for monitoring compression performance of said pre-filled data compression dictionary and said data specific data compression dictionary during compression of said sequence of characters, means for resetting the data compression dictionary determined by said monitoring means to be providing the lesser data compression performance when said data specific data compression dictionary becomes full during compression of said sequence of characters, and means for substituting the data compression dictionary determined by said monitoring means to be providing the greater data compression performance for said pre-filled data compression dictionary for compression of subsequent characters in said sequence of characters to be compressed.

51. A system as in claim 49, wherein said pre-filled data compression dictionary and said data specific data compression dictionary share a common memory, said data specific data compression dictionary being stored in said common memory with any new dictionary entries stored therein during compression of said sequence of characters as at least a portion of a pre-filled data compression dictionary for use in compression of a different sequence of characters of a different text.

52. A system as in claim 49, wherein said compressing means stores in said memory with said compressed representation of said characters making up said longest match and said extension character at least one of (1) an indication of which pre-filled data compression dictionary was used to form said compressed representation, (2) an indication of how dictionary address space is allocated between said data specific data compression dictionary and said pre-filled data compression dictionary, (3) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters, and (4) an indication of what technique to follow when said data specific data compression dictionary becomes filled.

53. A system as in claim 49, further comprising a dictionary memory for storing a plurality of pre-filled data compression dictionaries containing different genres of text data, whereby the pre-filled data compression dictionary used to compress said text contains data from the most similar genre to said sequence of characters to be compressed.

54. A system as in claim 53, wherein said compressing means repeats steps b-e for a different text from the same genre as said text using the data specific data compression dictionary entries stored during the compression of said text as the pre-filled data compression dictionary for compression of said different text.

55. A system as in claim 54, wherein said pre-filled data compression dictionary contains means for indicating whether the pre-filled data compression dictionary is formed during the compression of another text.

56. A data compression system for compressing a text containing a sequence of characters, comprising:

a dictionary memory which stores a character window which contains a predetermined number of characters and a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

a compressed data memory which stores said text after it has been compressed; and

compressing means for performing the steps of (a) initializing a pointer to a first character in said sequence of characters for compression, (b) comparing characters starting at said pointer with sequences of characters in said dictionary memory and determining a window pointer to and a length of a longest match of said characters starting at said pointer with said sequences of characters in said pre-filled data compression dictionary and said character window, (c) storing said window pointer and said length of said longest match in said compressed data memory as a compressed representation of said characters making up said longest match, (d) updating said character window to include the characters making up said longest match, (e) moving said pointer to a character in said sequence of characters which follows said longest match, and (f) repeating steps b-e for all characters in said sequence of characters to be compressed.

57. A system as in claim 56, wherein said compressing means stores in said compressed data memory in step c a literal character pointed to by said pointer when a sequence of characters pointed to by said pointer is not found in said character window or said pre-filled data compression dictionary in step b.

58. A system as in claim 56, wherein said compressed data memory is at a location remote from said compressing means, further comprising means for transmitting said window pointer and said length of said longest match as said compressed representation of said characters making up said longest match from said compressing means to said compressed data memory.

59. A data compression system for compressing a text containing a sequence of characters, comprising:

a pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters;

a character window which contains a predetermined number of characters;

a compressed data memory which stores said text after it has been compressed; and

compressing means for performing the steps of (a) initializing a pointer to a first character in said sequence of characters for compression, (b) comparing characters starting at said pointer with sequences of characters stored in said pre-filled data compression dictionary and with sequences of characters in said character window and determining longest matches of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary and with sequences of characters in said character window, (c) determining whether greater compression will be obtained by representing said characters starting at said pointer as a dictionary entry number of a longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary or by representing said characters starting at said pointer as a window pointer to and a length of a longest match of said characters starting at said pointer with said sequences of characters in said character window, (d) storing said window pointer and said length of said longest match in said compressed data memory as a compressed representation of said characters making up said longest match when it is determined in step c that greater compression will be obtained by representing said characters starting at said pointer as said window pointer to and said length of said longest match of said characters starting at said window pointer with said sequences of characters in said character window;

otherwise storing said dictionary entry number of said longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary, (e) updating said character window to include the characters making up said longest match, (f) moving said pointer to a character in said sequence of characters which follows said longest match, and (g) repeating steps b-f for all characters in said sequence of characters to be compressed.

60. A system as in claim 59, wherein said compressed data memory is at a location remote from said compressing means, further comprising means for transmitting to said compressed data memory said window pointer and said length of said longest match when it is determined by said compressing means in step c that greater compression will be obtained by representing said characters starting at said pointer as said window pointer to and said length of said longest match of said characters starting at said window pointer with said sequences of characters in said character window;

otherwise transmitting to said compressed data memory said dictionary entry number of said longest match of said characters starting at said pointer with said sequences of characters stored in said pre-filled data compression dictionary.

61. A data decompression system which decompresses a compressed representation of a sequence of characters, said compressed representation comprising dictionary pointers to respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters stored in a pre-filled data compression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said decompressing system comprising:

a compressed data memory for storing said compressed representation of said sequence of characters;

a decompressed data memory for storing said sequence of characters after decompression; and

decompressing means for performing the steps of;

(a) initializing a pointer to a first dictionary pointer in said compressed representation of said characters in said compressed data memory, (b) retrieving a dictionary entry from said pre-filled data compression dictionary using said dictionary pointer pointed to by said pointer, (c) storing said dictionary entry in said decompressed data memory as a decompressed representation of the characters making up said longest match, (d) moving said pointer to a next dictionary pointer in said compressed representation of said characters, and (e) repeating steps b-d for all dictionary pointers in said compressed representation of said characters in said compressed data memory until all compressed characters in said sequence of characters have been decompressed.

62. A system as in claim 61, wherein said decompressing means comprises means for extracting from said compressed representation of said characters in said compressed data memory at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression by said decompressing means, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters in said compressed data memory.

63. A data decompression system which decompresses a compressed representation of a sequence of characters, said compressed representation comprising extension characters and dictionary entry numbers of respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters stored in a pre-filled data compression dictionary and a data specific data compression dictionary, said extension character being that character in the sequence of characters which occurs after the longest match starting at said pointer, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said data decompression system comprising:

a compressed data memory for storing said compressed representation of said sequence of characters;

a decompressed data memory for storing said sequence of characters after decompression; and

decompressing means for performing the steps of;

(a) initializing a data specific data decompression dictionary, (b) initializing a pointer to a first dictionary entry number in said compressed representation of said characters in said compressed data memory, (c) retrieving a dictionary entry and an extension character from one of said pre-filled data compression dictionary and said data specific data decompression dictionary using a dictionary entry number pointed to by said pointer, (d) storing said dictionary entry in said decompressed data memory as a decompressed representation of the characters making up said longest match,(e) selectively storing said characters making up said longest match and said extension character into said data specific data decompression dictionary, (f) moving said pointer to a next dictionary entry number in said compressed representation of said characters in said compressed data memory, and (g) repeating steps c-f for all dictionary entry numbers and extension characters in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

64. A system as in claim 63, wherein said decompressing means further comprises means for extracting from said compressed representation of said characters in said compressed data memory at least one of:

(1) an indication of the pre-filled data compression dictionary to use during decompression, (2) an indication of how dictionary address space is allocated between said data specific data compression dictionary and said pre-filled data compression dictionary, (3) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters, and (4) an indication of what technique to follow when said data specific data compression dictionary becomes filled.

65. A data decompression system which decompresses a compressed representation of a sequence of characters, said compressed representation comprising window pointers and lengths of respective longest matches of sequences of characters in a character window having a pre-filled data compression dictionary appended thereto with a sequence of characters to be compressed, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said data decompression system comprising:

a compressed data memory for storing said compressed representation of said sequence of characters;

a decompressed data memory for storing said sequence of characters after decompression; and

decompressing means for performing the steps of;

(a) initializing a pointer to a first window pointer and length in said compressed representation of said characters in said compressed data memory, (b) retrieving a number of characters determined by said length starting at a character within a current character window pointed to by a window pointer which is pointed to by said pointer, (c) storing said retrieved characters as a decompressed representation of the characters making up said longest match in said decompressed data memory, (d) moving said pointer to a next window pointer and length in said compressed representation of said characters in said compressed data memory, and (e) repeating steps b-d for all window pointers and lengths in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

66. A system as in claim 65, wherein said decompressing means further comprises means for extracting from said compressed representation of said characters in said compressed data memory at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters.

67. A data decompression system which decompresses a compressed representation of a sequence of characters, said compressed representation comprising (1) window pointers and lengths of respective longest matches of sequences of characters starting at a pointer to particular characters within said sequence of characters with sequences of characters in a character window of a predetermined size and (2) dictionary entry numbers of respective longest matches of sequences of characters starting at said pointer to particular characters within a pre-filled data decompression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters likely to occur frequently in said sequence of characters, said data decompression system comprising:

a compressed data memory for storing said compressed representation of said sequence of characters;

a decompressed data memory for storing said sequence of characters after decompression; and

decompressing means for performing the steps of;

(a) initializing a pointer to a first entry in said compressed representation of said characters in said compressed data memory, (b) determining whether a current entry in said compressed representation of said characters pointed to by said pointer is (1) a window pointer and a length or (2) a dictionary entry number, (c) if said current entry in said compressed representation is a window pointer and a length, retrieving a number of characters determined by said length starting at a character within a current character window pointed to by said window pointer, (d) if said current entry in said compressed representation is a dictionary entry number, retrieving characters at a dictionary entry in said pre-filled data decompression dictionary identified by said dictionary entry number, (e) storing characters retrieved in steps c or d in said decompressed data memory as a decompressed representation of the characters making up the longest match for the current entry, (f) moving said pointer to a next entry in said compressed representation of said characters in said compressed data memory, and (g) repeating steps b-f for all entries in said compressed representation of said characters until all compressed characters in said sequence of characters have been decompressed.

68. A system as in claim 67, wherein said decompressing means further comprises means for extracting from said compressed representation of said characters in said compressed data memory at least one of:

(1) the identity of the pre-filled data compression dictionary to use during decompression, and (2) an indication of a Lempel-Ziv algorithm variant to be used to decompress said compressed representation of said characters.