×

Method and apparatus for data compression having an improved matching algorithm which utilizes a parallel hashing technique

  • US 5,406,278 A
  • Filed: 02/28/1992
  • Issued: 04/11/1995
  • Est. Priority Date: 02/28/1992
  • Status: Expired due to Fees
First Claim
Patent Images

1. A matching method useful for digital data compression operations which compresses an input data stream into a compressed output data stream based on a predetermined minimum matching length, where the input data stream comprises a plurality of input data subblocks including subblocks of N bytes and N+1 bytes, and the compressed output data stream comprises a plurality of compressed and uncompressed output data subblocks, the matching method comprising the following steps:

  • a. initializing a first hash table and a second hash table each having a plurality of entries;

    b. obtaining a current source pointer for a current input data subblock;

    c. computing an address for said first hash table on an input data subblock of N bytes, where N is an integer;

    d. exchanging said current source pointer with an entry of said first hash table at said address computed in step (c);

    e. saving said entry of said first hash table;

    f. computing an address for said second hash table on an input data subblock of N+1 bytes;

    g. exchanging said current source pointer with an entry of said second hash table at said address computed in step (f);

    h. determining a matching length for said entry of said second hash table obtained in step (g);

    i. if said matching length determined in step (h) is not less than said predetermined minimum matching length, then encoding said current input data subblock as an compressed output data subblock;

    j. if said matching length determined in step (h) is less than said predetermined minimum matching length, then determining a matching length for said entry of said first hash table saved in step (e);

    k. if said matching length determined in step (j) is not less than said predetermined minimum matching length, then encoding said current input data subblock as a compressed output data subblock;

    l. if said matching length determined in step (j) is less than said predetermined minimum matching length, then encoding said current input data subblock as an incompressible output data subblock; and

    m. repeating the steps (b) through (l) until all of said plurality of input data subblocks have been processed.

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