Data compression method

Abstract

Disclosed is a method of compressing a sequence of data symbols. The method includes the steps of sequentially appending symbols to a working substring to find the longest string that is duplicated in a history buffer or a lexicon. If the string is duplicated in the history buffer, then a history reference is emitted. If the string is duplicated in the lexicon, then a lexicon reference is emitted. If the string is not duplicated in either the history buffer or the lexicon, then a literal reference is emitted. The history buffer is a record of uncompressed data that has most recently been processed. The lexicon is a record of strings that has been emitted by means of history references.

What is claimed is: 
     
       1. A method of compressing data made up of a sequence of symbols, which comprises the steps of: recording in a fixed length history buffer symbols of said sequence;   emitting a history reference whenever a string of symbols from said sequence is duplicated in said history buffer;   recording in a lexicon strings of symbols that have been emitted by means of history references; and,   emitting a lexicon reference whenever a string of symbols from said sequence is duplicated in said lexicon.   
     
     
       2. The method as claimed in claim 1, wherein the length of said history buffer is less than the length of said sequence. 
     
     
       3. The method as claimed in claim 1, wherein said lexicon has a fixed size. 
     
     
       4. The method as claimed in claim 1, including the step of emitting a literal reference whenever a symbol of said sequence is duplicated in neither said history buffer nor lexicon. 
     
     
       5. The method as claimed in claim 1, including the step of: forming the longest string of symbols that is duplicated in either said lexicon or said history buffer.   
     
     
       6. The method as claimed in claim 5, wherein said longest string is equal to or less than a preselected maximum history reference length value. 
     
     
       7. The method as claimed in claim 5, wherein said forming step includes the steps of: forming a token;   sequentially appending to said token symbols from said sequence until said token is duplicated in neither said lexicon nor said history buffer.   
     
     
       8. The method as claimed in claim 7, wherein said step of sequentially appending symbols to said token includes the steps of: (a) appending a symbol to said token;   (b) comparing said token to the contents of said lexicon;   (c) appending another symbol to said token if said token is duplicated in said lexicon;   (d) repeating steps b and c until said token is not duplicated in said lexicon;   (e) comparing said token to the contents of said history buffer;   (f) appending another symbol to said token if said token is duplicated in said history buffer and,   (g) repeating steps b through f until said token is not duplicated in said history buffer.   
     
     
       9. The method as claimed in claim 8, including the step of repeating steps b through f as long as said token is equal to or less than a preselected maximum history reference length value. 
     
     
       10. The method as claimed in claim 1, wherein said lexicon is initially empty. 
     
     
       11. A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) sequentially appending symbols to a token until said token is duplicated in neither a lexicon or a history buffer, thereby forming a longest referenced string of symbols that can be duplicated in either the lexicon or the history buffer;   (b) emitting a lexicon reference representing said referenced string when said referenced string duplicated in said lexicon;   (c) emitting a history reference representing said referenced string when said referenced string is duplicated in said history buffer;   (d) emitting a literal reference when said referenced string is not duplicated in either the history buffer or the lexicon;   (e) adding the referenced string represented by the history reference emitted in step d to the lexicon;   (f) appending the referenced string represented by the reference emitted in step c, d, or e to the history buffer;   (g) deleting the referenced string represented by the emitted reference from the token and,   (h) repeating steps a through g until said sequence of characters is exhausted.   
     
     
       12. The method as claimed in claim 11, wherein said history buffer is of a fixed size. 
     
     
       13. The method as claimed in claim 11, wherein said step of sequentially appending characters to said working substring includes the steps of: (a) appending a symbol to said token;   (b) comparing the token to the contents of the lexicon;   (c) appending another symbol to the token if the token is duplicated in the lexicon;   (d) repeating steps b and c until the token is not duplicated in the lexicon;   (e) comparing the contents of the token to the contents of the history buffer;   (f) adding another symbol to the token if the token is found in the history buffer and,   (g) repeating steps b through f until the token is not found in the history buffer.   
     
     
       14. The method as claimed in claim 13, including the step of repeating steps b through f as long as said token is equal to or less than a preselected maximum history reference length. 
     
     
       15. A method of compressing data made up of a sequence of symbols, which comprises the steps of: (a) forming a token, a history buffer having a fixed depth, and a lexicon having a fixed number of available entries;   (b) clearing the token, history buffer, and lexicon;   (c) appending a symbol to the token;   (d) comparing the token to the contents of the lexicon;   (e) appending another symbol to the token if the token is duplicated in the lexicon;   (f) repeating steps d and e as long as the token is not greater than a preselected maximum history reference length and until the token is not duplicated in the lexicon;   (g) comparing the token to the contents of the history buffer;   (h) appending another symbol to the token if the token is duplicated in the history buffer;   (i) repeating steps d through h as long as the token is not greater than said preselected maximum history reference length and until the token is not duplicated in the history buffer, thereby finding a match in the history buffer or the lexicon;   (j) emitting a lexicon reference if the match is found in the lexicon;   (k) emitting a history reference if the match is found in the history buffer;   (l) emitting a literal reference if no match is found in either the history buffer or the lexicon;   (m) appending the history reference string emitted in step k to the lexicon;   (n) adding the reference string emitted in step j, k, or l to the history buffer;   (o) deleting the transmitted reference from the token and;   (p) repeating steps c through o until the sequence of characters is exhausted.