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

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.

1. A data compression method for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising the steps of:
 (a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said  a sequence of characters  bit strings to be compressed;  
 (b) initializing a pointer to a first character  bit in said sequence of characters for compression  bit strings to be compressed;  
 (c) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings stored in said pre-filled data compression dictionary and determining a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings 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  bit strings making up said longest match;  
 (e) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match; and  
 (f) repeating steps c-e for all characters  bit strings in said sequence of characters  bit strings 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  bit string sequences in at least one sample sequence of characters  bit strings which is representative of the  a sequence of characters  bit strings to be compressed to determine the frequency of occurrence of said character  bit string sequences in said at least one sample sequence of characters  bit strings; and  
 selecting as said predetermined combinations those character  bit string sequences in said at least one sample sequence of characters  bit strings which occur most frequently in said at least one sample sequence of characters  bit strings.  
 
     
     
       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  bit string sequences in said at least one sample sequence of characters  bit strings and calculating for each character  bit string sequence a product of the number of occurrences of said each character  bit string sequence with the difference in bit length of said each character  bit string 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  bit strings of said  a sequence of data characters  bit strings 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  bit strings, and selecting said one pre-filled data compression dictionary as said pre-filled data compression dictionary for use in compressing said sequence of characters  bit strings. 
     
     
       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  bit strings of said sequence of data characters  bit strings to be compressed that starting with an empty data compression dictionary would allow for the most compression of said sequence of data characters  bit strings. 
     
     
       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  bit strings 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  a sequence of characters  bit strings 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  bit strings 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 at least one of different statistical patterns and 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  bit strings 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. 
     
     
       16. A data compression method for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising the steps of:
 (a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said  a sequence of characters  bit strings to be compressed;  
 (b) initializing a data specific data compression dictionary;  
 (c) initializing a pointer to a first character  bit in said sequence of characters for compression  bit strings to be compressed;  
 (d) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings 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  bit strings starting at said pointer with said sequences of characters  bit strings 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  bit string in a memory as a compressed representation of said characters  bit strings making up said longest match and said extension character  bit string, said extension character  bit string being that character  bit string in said sequence of characters  bit strings to be compressed which occurs after said longest match starting at said pointer;  
 (f) selectively storing said characters  bit strings making up said longest match and said extension character  bit string in said data specific data compression dictionary as a new dictionary entry;  
 (g) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said extension character  bit string; and  
 (h) repeating steps d-g for all characters  bit strings in said sequence of characters  bit strings 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  bit strings and, when said data specific data compression dictionary becomes full during compression of said sequence of characters  bit strings, 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  bit strings in said sequence of characters  bit strings 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  a sequence of characters  bit strings as at least a portion of a pre-filled data compression dictionary for use in compression of a different sequence of characters  bit strings. 
     
     
       19. A method as in  claim 16 , comprising the further step of storing with said compressed representation of said characters  bit strings making up said longest match and said extension character  bit string 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  bit strings, 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 at least one of different statistical patterns and 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  bit strings to be compressed. 
     
     
       21. A method as in  claim 20 , comprising the further step of repeating steps (b)-(g) for a  different text  bit strings to be compressed from the same genre as said text  bit strings using the data specific data compression dictionary formed during the compression of said text  bit strings as the pre-filled data compression dictionary for compression of said different text  bit strings to be compressed. 
     
     
       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  said different bit strings. 
     
     
       23. A data compression method for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising the steps of:
 (a) initializing a character  bit string window which contains a predetermined number of characters  bit strings;  
 (b) appending a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said  a sequence of characters  bit strings to be compressed to said character  bit string window;  
 (c) initializing a pointer to a first character  bit in said sequence of characters  bit strings for compression;  
 (d) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings in said character  bit string 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  bit strings starting at said pointer with said sequences of characters  bit strings in said character  bit string 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  bit strings making up said longest match;  
 (f) updating said character  bit string window to include the characters  bit strings making up said longest match;  
 (g) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match; and  
 (h) repeating steps d-g for all characters  bit strings in said sequence of characters  bit strings 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  bit strings pointed to by said pointer is not found in said character  bit string 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  bit strings making up said longest match. 
     
     
       26. A data compression method for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising the steps of:
 (a) selecting a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said  a sequence of characters  bit strings to be compressed;  
 (b) initializing a character  bit string window which contains a predetermined number of characters  bit strings;  
 (c) initializing a pointer to a first character  bit in said sequence of characters for compression  bit strings to be compressed;  
 (d) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings stored in said pre-filled data compression dictionary and with sequences of characters  bit strings in said character  bit string window and determining longest matches of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary and with sequences of characters  bit strings in said character  bit string window;  
 (e) determining whether greater compression will be obtained by representing said characters  bit strings starting at said pointer as a dictionary entry number of a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary or by representing said characters  bit strings starting at said pointer as a window pointer to and a length of a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings in said character  bit string window;  
 (f) storing said window pointer and said length of said longest match in a memory as a compressed representation of said characters  bit strings making up said longest match when it is determined in step e that greater compression will be obtained by representing said characters  bit strings starting at said pointer as said window pointer to and said length of said longest match of said characters  bit strings starting at said window pointer with said sequences of characters  bit strings in said character  bit string window; otherwise storing said dictionary entry number of said longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary;  
 (g) updating said character  bit string window to include the characters  bit strings making up said longest match;  
 (h) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match; and  
 (i) repeating steps d-h for all characters  bit strings in said sequence of characters  bit strings 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  bit strings starting at said pointer as said window pointer to and said length of said longest match of said characters  bit strings starting at said window pointer with said sequences of characters  bit strings in said character  bit string window; otherwise transmitting to said recipient said dictionary entry number of said longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary. 
     
     
       28. A method of decompressing a compressed representation of a sequence of characters  bit strings of data and/or text, said bit strings containing a sequence of characters, said compressed representation comprising dictionary pointers to respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings stored in a pre-filled data compression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said decompressing method comprising the steps of:
 (a) initializing a pointer to a first dictionary pointer in said compressed representation of said characters  bit strings;  
 (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  bit strings making up said longest match;  
 (d) moving said pointer to a next dictionary pointer in said compressed representation of said characters  bit strings; and  
 (e) repeating steps b-d for all dictionary pointers in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings have been decompressed.  
 
     
     
       29. A method as in  claim 28 , comprising the further step of extracting from said compressed representation of said characters  bit strings 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  bit strings. 
     
     
       30. A method of decompressing a compressed representation of a sequence of characters  bit strings of data and/or text, said bit strings containing a sequence of characters, said compressed representation comprising extension characters  bit strings and dictionary entry numbers of respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings stored in a pre-filled data compression dictionary and a data specific data compression dictionary, said extension character  bit string being that character  bit string in the sequence of characters  bit strings which occurs after the longest match starting at said pointer, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, 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  bit strings;  
 (c) retrieving a dictionary entry and an extension character  bit string 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  bit strings making up said longest match and said extension character  bit string into said data specific data decompression dictionary;  
 (e) moving said pointer to a next dictionary entry number in said compressed representation of said characters  bit strings; and  
 (f) repeating steps c-e for all dictionary entry numbers and extension characters  bit strings in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings have been decompressed.  
 
     
     
       31. A method as in  claim 30 , comprising the further step of extracting from said compressed representation of said characters  bit strings 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  bit strings, 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  bit strings of data and/or text, said bit strings containing a sequence of characters, said compressed representation comprising window pointers and lengths of respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings in a character  bit string 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  bit strings likely to occur frequently in said sequence of characters  bit strings, 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  bit strings;  
 (b) retrieving a number of characters  bit strings determined by said length starting at a character  bit within a current character  bit string window pointed to by a window pointer which is pointed to by said pointer;  
 (c) storing said retrieved characters  bit strings as a decompressed representation of the characters  bit strings making up said longest match;  
 (d) moving said pointer to a next window pointer and length in said compressed representation of said characters  bit strings; and  
 (e) repeating steps b-d for all window pointers and lengths in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings have been decompressed.  
 
     
     
       33. A method as in  claim 32 , comprising the further step of extracting from said compressed representation of said characters  bit strings 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  bit strings. 
     
     
       34. A method of decompressing a compressed representation of a sequence of characters  bit strings of data and/or text, said bit strings containing a sequence of characters, said compressed representation comprising (1) window pointers and lengths of respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings in a character  bit string window of a predetermined size and (2) dictionary entry numbers of respective longest matches of sequences of characters  bit strings starting at said pointer to particular characters  bit strings within a pre-filled data decompression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said decompressing method comprising the steps of:
 (a) initializing a pointer to a first entry in said compressed representation of said characters  bit strings;  
 (b) determining whether a current entry in said compressed representation of said characters  bit strings 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  bit strings determined by said length starting at a character  bit within a current character  bit string window pointed to by said window pointer;  
 (d) if said current entry is a dictionary entry number, retrieving characters  bit strings at a dictionary entry in said pre-filled data decompression dictionary identified by said dictionary entry number;  
 (e) storing characters  bit strings retrieved in steps c or d as a decompressed representation of the characters  bit strings making up the longest match for the current entry;  
 (f) moving said pointer to a next entry in said compressed representation of said characters  bit strings; and  
 (g) repeating steps b-f for all entries in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings have been decompressed.  
 
     
     
       35. A method as in  claim 34 , comprising the further step of extracting from said compressed representation of said characters  bit strings 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  bit strings. 
     
     
       36. A data compression system for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising:
 a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings;  
 a memory which stores said text  sequence of bit strings after it has been compressed; and  
 compressing means for performing the steps of (a) initializing a pointer to a first character  bit in said sequence of characters  bit strings for compression, (b) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings stored in said pre-filled data compression dictionary and determining a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings 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  bit strings making up said longest match, (d) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match, and (e) repeating steps b-d for all characters  bit strings in said sequence of characters  bit strings 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  bit strings which most frequently occur in at least one sample sequence of characters  bit strings which is representative of the sequence of characters  bit strings 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  bit strings in at least one sample sequence of characters  bit strings which is representative of the sequence of characters  bit strings to be compressed which have the greatest product of (a) a number of occurrences of each of said combinations of characters  bit strings in said at least one sample sequence of characters  bit strings with (b) a difference in bit length of each said combination of characters  bit strings 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  bit strings 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  bit strings 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  bit strings which provide more compression of a subset of characters  bit strings of said sequence of data characters  bit strings to be compressed than the compression provided to said subset of characters  bit strings of said sequence of data characters  bit strings 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  bit strings 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  bit strings 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 at least one of different statistical patterns and different genres of text  data, whereby the pre-filled data compression dictionary used to compress said text  sequence of bit strings contains data from the most similar genre to said sequence of characters  bit strings 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  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising:
 a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings;  
 a data specific data compression dictionary;  
 a memory which stores said text  sequence of bit strings after it has been compressed; and  
 compressing means for performing the steps of (a) initializing a pointer to a first character  bit in said sequence of characters  bit strings for compression, (b) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings 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  bit strings starting at said pointer with said sequences of characters  bit strings 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  bit string in said memory as a compressed representation of said characters  bit strings making up said longest match and said extension character  bit string, said extension character  bit string being that character  bit string in said sequence of characters  bit strings to be compressed which occurs after said longest match starting at said pointer, (d) selectively storing said characters  bit strings making up said longest match and said extension character  bit string in said data specific data compression dictionary as a new dictionary entry, (e) moving said pointer to a character  bit string in said sequence of characters  bit strings which follows said extension character  bit string, and (f) repeating steps b-e for all characters  bit strings in said sequence of characters  bit strings 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  bit strings, 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  bit strings, 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  bit strings in said sequence of characters  bit strings 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  bit strings 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  bit strings. 
     
     
       52. A system as in  claim 49 , wherein said compressing means stores in said memory with said compressed representation of said characters  bit strings making up said longest match and said extension character  bit string 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  bit strings, 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 at least one of different statistical patterns and different genres of text  data, whereby the pre-filled data compression dictionary used to compress said text  sequence of bit strings contains data from the most similar genre to said sequence of characters  bit strings to be compressed. 
     
     
       54. A system as in  claim 53 , wherein said compressing means repeats steps b-e for a different text  sequence of bit strings from the same genre as said text  sequence of bit strings using the data specific data compression dictionary entries stored during the compression of said text  sequence of bit strings as the pre-filled data compression dictionary for compression of said different text  sequence of bit strings. 
     
     
       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  different sequence of bit strings. 
     
     
       56. A data compression system for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising:
 a dictionary memory which stores a character  bit string window which contains a predetermined number of characters  bit strings and a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings;  
 a compressed data memory which stores said text  sequence of bit strings after it has been compressed; and  
 compressing means for performing the steps of (a) initializing a pointer to a first character  bit in said sequence of characters  bit strings for compression, (b) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings in said dictionary memory and determining a window pointer to and a length of a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings in said pre-filled data compression dictionary and said character  bit string 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  bit strings making up said longest match, (d) updating said character  bit string window to include the characters  bit strings making up said longest match, (e) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match, and (f) repeating steps b-e for all characters  bit strings in said sequence of characters  bit strings 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  bit strings pointed to by said pointer is not found in said character  bit string 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  bit strings making up said longest match from said compressing means to said compressed data memory. 
     
     
       59. A data compression system for compressing a  bit strings of data and/or text, said bit strings containing a sequence of characters, comprising:
 a pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings;  
 a character  bit string window which contains a predetermined number of characters  bit strings;  
 a compressed data memory which stores said text  sequence of bit strings after it has been compressed; and  
 compressing means for performing the steps of (a) initializing a pointer to a first character  bit in said sequence of characters  bit strings for compression, (b) comparing characters  bit strings starting at said pointer with sequences of characters  bit strings stored in said pre-filled data compression dictionary and with sequences of characters  bit strings in said character  bit string window and determining longest matches of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary and with sequences of characters  bit strings in said character  bit string window, (c) determining whether greater compression will be obtained by representing said characters  bit strings starting at said pointer as a dictionary entry number of a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary or by representing said characters  bit strings starting at said pointer as a window pointer to and a length of a longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings in said character  bit string 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  bit strings making up said longest match when it is determined in step c that greater compression will be obtained by representing said characters  bit strings starting at said pointer as said window pointer to and said length of said longest match of said characters  bit strings starting at said window pointer with said sequences of characters  bit strings in said character  bit string window; otherwise storing said dictionary entry number of said longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary, (e) updating said character  bit string window to include the characters  bit strings making up said longest match, (f) moving said pointer to a character  bit in said sequence of characters  bit strings which follows said longest match, and (g) repeating steps b-f for all characters  bit strings in said sequence of characters  bit strings 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  bit strings starting at said pointer as said window pointer to and said length of said longest match of said characters  bit strings starting at said window pointer with said sequences of characters  bit strings in said character  bit string window; otherwise transmitting to said compressed data memory said dictionary entry number of said longest match of said characters  bit strings starting at said pointer with said sequences of characters  bit strings stored in said pre-filled data compression dictionary. 
     
     
       61. A data decompression system which decompresses a compressed representation of a sequence of characters  bit strings, said compressed representation comprising dictionary pointers to respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings stored in a pre-filled data compression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said decompressing system comprising:
 a compressed data memory for storing said compressed representation of said sequence of characters  bit strings;  
 a decompressed data memory for storing said sequence of characters  bit strings 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  bit strings 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  bit strings making up said longest match, (d) moving said pointer to a next dictionary pointer in said compressed representation of said characters  bit strings, and (e) repeating steps b-d for all dictionary pointers in said compressed representation of said characters  bit strings in said compressed data memory until all compressed characters  bit strings in said sequence of characters  bit strings 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  bit strings 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  bit strings in said compressed data memory. 
     
     
       63. A data decompression system which decompresses a compressed representation of a sequence of characters  bit strings, said compressed representation comprising extension characters  bit strings and dictionary entry numbers of respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings stored in a pre-filled data compression dictionary and a data specific data compression dictionary, said extension character  bit string being that character  bit string in the sequence of characters  bit strings which occurs after the longest match starting at said pointer, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said data decompression system comprising:
 a compressed data memory for storing said compressed representation of said sequence of characters  bit strings;  
 a decompressed data memory for storing said sequence of characters  bit strings 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  bit strings in said compressed data memory, (c) retrieving a dictionary entry and an extension character  bit string 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  bit strings making up said longest match,(e) selectively storing said characters  bit strings making up said longest match and said extension character  bit string into said data specific data decompression dictionary, (f) moving said pointer to a next dictionary entry number in said compressed representation of said characters  bit strings in said compressed data memory, and (g) repeating steps c-f for all dictionary entry numbers and extension characters  bit strings in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings 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  bit strings 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  bit strings, 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  bit strings, said compressed representation comprising window pointers and lengths of respective longest matches of sequences of characters  bit strings in a character  bit string window having a pre-filled data compression dictionary appended thereto with a sequence of characters  bit strings to be compressed, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said data decompression system comprising:
 a compressed data memory for storing said compressed representation of said sequence of characters  bit strings;  
 a decompressed data memory for storing said sequence of characters  bit strings 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  bit strings in said compressed data memory, (b) retrieving a number of characters  bit strings determined by said length starting at a character  bit within a current character  bit string window pointed to by a window pointer which is pointed to by said pointer, (c) storing said retrieved characters  bit strings as a decompressed representation of the characters  bit strings 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  bit strings in said compressed data memory, and (e) repeating steps b-d for all window pointers and lengths in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings 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  bit strings 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  bit strings. 
     
     
       67. A data decompression system which decompresses a compressed representation of a sequence of characters  bit strings, said compressed representation comprising (1) window pointers and lengths of respective longest matches of sequences of characters  bit strings starting at a pointer to particular characters  bit strings within said sequence of characters  bit strings with sequences of characters  bit strings in a character  bit string window of a predetermined size and (2) dictionary entry numbers of respective longest matches of sequences of characters  bit strings starting at said pointer to particular characters  bit strings within a pre-filled data decompression dictionary, said pre-filled data compression dictionary containing predetermined combinations of characters  bit strings likely to occur frequently in said sequence of characters  bit strings, said data decompression system comprising:
 a compressed data memory for storing said compressed representation of said sequence of characters  bit strings;  
 a decompressed data memory for storing said sequence of characters  bit strings 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  bit strings in said compressed data memory, (b) determining whether a current entry in said compressed representation of said characters  bit strings 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  bit strings determined by said length starting at a character  bit within a current character  bit string window pointed to by said window pointer, (d) if said current entry in said compressed representation is a dictionary entry number, retrieving characters  bit strings at a dictionary entry in said pre-filled data decompression dictionary identified by said dictionary entry number, (e) storing characters  bit strings retrieved in steps c or d in said decompressed data memory as a decompressed representation of the characters  bit strings making up the longest match for the current entry, (f) moving said pointer to a next entry in said compressed representation of said characters  bit strings in said compressed data memory, and (g) repeating steps b-f for all entries in said compressed representation of said characters  bit strings until all compressed characters  bit strings in said sequence of characters  bit strings 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  bit strings 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  bit strings. 
     
     
       69. A data compression method for compressing bit strings of data and/or text, said bit strings containing a sequence of characters, comprising the steps of:
 (a) compressing a first sequence of bit strings in a first document to be compressed so as to create a data specific data compression dictionary for said first sequence of bit strings;    (b) determining if a second sequence of bit strings in a second document to be compressed has a similar statistical pattern or belongs to the same data genre as said first sequence of bit strings; and    (c) when said first and second sequences of bit strings to be compressed have a similar statistical pattern or belong to the same data genre, compressing said second sequence of bit strings using said data specific data compression dictionary to create a compressed version of said second document for storage and/or data transmission.   
     
     
       70. A data compression method for compressing bit strings of data and/or text, comprising the steps of:
 (a) selecting a pre-filled data compression dictionary containing predetermined combinations of bit strings likely to occur frequently and have a long bit sequence length in a sequence of bit strings to be compressed;    (b) initializing a pointer to a first bit in said sequence of bit strings to be compressed;    (c) comparing bit strings starting at said pointer with bit strings stored in said pre-filled data compression dictionary and determining a match with a product of a frequency of occurrence of a bit sequence and length of the bit sequence for said bit strings starting at said pointer with said sequences of bit strings stored in said selected pre-filled data compression dictionary;    (d) storing a compressed representation of said bit strings making up said match;    (e) moving said pointer to a bit in said sequence of bit strings which follows said match; and    (f) repeating steps c-e for all bit strings in said sequence of bit strings to be compressed.   
     
     
       71. A method as in  claim 70 , comprising the further step of encoding frequently used bit strings in said pre- filled data compression dictionary into smaller bit strings.   
     
     
       72. A method as in  claim 70 , comprising the further steps of variable length-encoding said compressed representations of said bit strings making up said match and transmitting said encoded compressed representations. 
     
     
       73. A method as in  claim 70 , comprising the further steps of storing said compressed representations in a data specific data compression dictionary, determining overlap of dictionary entries between pre- filled data compression dictionaries and said data specific data compression dictionary by performing frequency analysis of a collection of documents from which said pre-filled data compression dictionaries are formed, determining whether all repeating bit strings are present in the pre-filled data compression dictionaries, and if a repeating string is not present in the pre-filled data compression dictionaries, inserting the repeating string that is not present into at least one of the pre-filled data compression dictionaries.   
     
     
       74. A method as in  claim 73 , comprising the further step of making room for the inserted repeating string in said at least one pre-filled data compression dictionary by using a least recently used method to determine which pre-filled data compression dictionary entry should be discarded. 
     
     
       75. A data compression method for compressing bit strings of data and/or text, comprising the steps of:
 (a) storing a plurality of pre-filled data compression dictionaries containing at least one of different statistical patterns and different genres of data;    (b) selecting a pre-filled data compression dictionary from said plurality of pre-filled data compression dictionaries so as to optimize compression speed of said bit strings to be compressed;    (c) initializing a pointer to a first bit in said sequence of bit strings to be compressed;    (d) comparing bit strings starting at said pointer with bit strings stored in said pre-filled data compression dictionary and determining a longest match of said bit strings starting at said pointer with said sequences of bit strings stored in said selected pre-filled data compression dictionary;    (e) storing a compressed representation of said bit strings making up said longest match;    (f) moving said pointer to a bit in said sequence of bit strings that follows said longest match; and    (g) repeating steps d-f for all bit strings in said sequence of bit strings to be compressed.   
     
     
       76. A method as in  claim 75 , wherein said selecting step comprises the step of selecting the pre-filled data compression dictionary most appropriate to a genre of the bit strings to be compressed using clustering methods. 
     
     
       77. A method as in  claim 75 , wherein said storing step comprises the step of storing pre-filled data compression dictionaries on communicating servers. 
     
     
       78. A data compression method for compressing bit strings of data and/or text, comprising the steps of:
 (a) storing a plurality of pre-filled data compression dictionaries containing at least one of different statistical patterns and different genres of data;    (b) selecting a pre-filled data compression dictionary from said plurality of pre-filled data compression dictionaries so as to optimize length of dictionary entry with respect to computing time needed to build the pre-filled data compression dictionary;    (c) initializing a pointer to a first bit in said sequence of bit strings to be compressed;    (d) comparing bit strings starting at said pointer with bit strings stored in said pre-filled data compression dictionary and determining a longest match of said bit strings starting at said pointer with said sequences of bit strings stored in said selected pre-filled data compression dictionary;    (e) storing a compressed representation of said bit strings making up said longest match;    (f) moving said pointer to a bit in said sequence of bit strings that follows said longest match; and    (g) repeating steps d-f for all bit strings in said sequence of bit strings to be compressed.   
     
     
       79. A method as in  claim 78 , wherein said data comprises at least one of computer programs, database files, images, and ASCII code. 
     
     
       80. A data compression method for compressing bit strings of data and/or text, comprising the steps of:
 (a) compressing a first sequence of bit strings in a first document to be compressed so as to create a data specific data compression dictionary for said first sequence of bit strings; and    (b) compressing a second sequence of bit strings in a second document using at least a portion of said data specific data compression dictionary to create a compressed version of said second document for storage and/or transmission, where the second sequence of bit strings represents data and/or text from a file and/or data genre that is different from the file and/or data genre of said first sequence of bit strings.   
     
     
       81. A method as in  claim 80 , comprising using a data specific data compression dictionary created during compression of said second sequence of bit strings to update said data specific data compression dictionary for said first sequence of bit strings. 
     
     
       82. A method as in  claim 81 , comprising providing said data specific data compression dictionary created during compression of said second sequence of bit strings as at least one of the following: an update to a pre-filled data compression dictionary for an old genre, an additional pre-filled data compression dictionary, and a replacement for an existing pre-filled data compression dictionary. 
     
     
       83. A method as in  claim 1 , wherein the sequence of bit strings to be compressed are stored on a device's local storage memory, loaded onto local processing hardware of said device, processed on said local processing hardware in accordance with steps (a)-(f), and re-stored on said device's local storage memory for purposes of saving memory space. 
     
     
       84. A method as in  claim 83 , wherein the sequence of bit strings to be compressed are stored on a device's local storage memory, loaded onto local processing hardware of said device, processed on said local processing hardware in accordance with steps (a)-(f), and said processed bit strings are transmitted to a receiver device for purposes of reducing a quantity of data to be transmitted via a connection between said local processing hardware and said receiver device. 
     
     
       85. A method as in  claim 84 , wherein processed bit strings received by said receiver device is loaded into a local storage memory of said receiver device as a compressed form of said sequence of bit strings for decompression by decompression hardware of said receiver device.