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

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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.

Claim 21

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.

Claim 22

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.

Claim 23

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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.

Claim 29

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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 35

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.

Claim 38

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.

Claim 41

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.

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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.

Claim 48

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.

Claim 49

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.

Claim 50

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.

Claim 51

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.

Claim 52

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.

Claim 53

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.

Claim 54

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.

Claim 55

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.

Claim 56

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.

Claim 57

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.

Claim 58

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.

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

Claim 60

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.

Claim 61

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.

Claim 62

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.

Claim 63

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.

Claim 64

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.

Claim 65

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.

Claim 66

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.

Claim 67

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.

Claim 68

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.

Claim 69

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.

Claim 70

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.

Claim 71

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.

Claim 72

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.

Claim 73

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.

Claim 74

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.

Claim 75

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.

Claim 76

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.

Claim 77

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.

Claim 78

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.

Claim 79

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.

Claim 80

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.

Claim 81

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.

Claim 82

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.

Claim 83

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.

Claim 84

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.

Claim 85

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.