×

Data compression apparatus and method

  • US 5,016,009 A
  • Filed: 01/13/1989
  • Issued: 05/14/1991
  • Est. Priority Date: 01/13/1989
  • Status: Expired due to Fees
First Claim
Patent Images

1. A method for converting an input data character stream into a variable length encoded data stream in a data compression system, said data compression system comprising a history array means, said history array means having a plurality of entries, said entries of said history array means for storing said input data stream, a history array pointer, said history array pointer indicating a latest entry in said history array means, a hash table means having a plurality of entries, each entry of said hash table means for storing a pointer indicating one of said entries of said history array means, and an offset array means, said offset array means having a plurality of entries, each entry of said offset array means providing a link, if any, from one of said entries in said history array means to one or more other entries of said history array means, said method comprising the steps of:

  • performing a search in said history array means for a longest matching data string which matches said input data stream, said step of performing said search including the steps of;

    performing a hashing function on said input data stream, said hashing function providing a pointer indicating one of said entries of said hash table means,obtaining said pointer stored at said hash table entry pointed to by said hashing function,calculating a difference between said history array pointer and said pointer obtained from said hash table means,storing said difference into said offset array means entry pointed to by said history array pointer, andstoring said history array pointer into said hash table entry pointed to by said hashing function,operative when said matching data string is found within said history array means, encoding said matching data string found in said history array means by assigning a tag indicating that said matching data string was found and a string substitution code including a variable length indicator of the length of said matching data string and a pointer indicating the location within said history array means of said matching data string,operative when said matching data string is not found within said history array means, encoding a first character of said input data stream by assigning a "raw" data tag indicating that no matching data string was found in said history array means and said first character of said input data stream,whereby said input data stream is converted into a variable length encoded data stream.

View all claims
  • 5 Assignments
Timeline View
Assignment View
    ×
    ×