Data compression/decompression method and apparatus
First Claim
1. A system for compressing digital input data, said input data being divisible into symbols, comprising:
- a memory for holding at least first and second sequences of symbols from said input data, said first sequence having a prefix substring including fewer symbols than said first sequence;
means for receiving said first and second sequences of symbols from said memory and comparing said first and second sequences;
means for receiving said prefix substring from said memory and computing a hash value therefrom;
a hash table for receiving said hash value and providing a pointer to said second sequence of symbols, said hash table including a plurality of first in, first-out (FIFO) collision chains, having identical numbers of pointers to locations in said memory; and
means for generating compressed output data responsive to said means for receiving said first and second sequences of symbols from said memory.
8 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for compressing digital data uses data which has been previously compressed as a dictionary of substrings which may be replaced in an input data stream. The method and apparatus uses a hash table to take advantage of principles of locality and probability to solve the maximal matching substring problem inherent in this type of compressing apparatus, most of the time. The hash table consists of first-in, first-out (FIFO) collision chains of fixed, uniform numbers of pointers to substrings of data already compressed which potentially match an input substring. A companion decompressing method and apparatus receives compressed data from the compressing apparatus and expand that data back to its original form.
88 Citations
14 Claims
-
1. A system for compressing digital input data, said input data being divisible into symbols, comprising:
-
a memory for holding at least first and second sequences of symbols from said input data, said first sequence having a prefix substring including fewer symbols than said first sequence; means for receiving said first and second sequences of symbols from said memory and comparing said first and second sequences; means for receiving said prefix substring from said memory and computing a hash value therefrom; a hash table for receiving said hash value and providing a pointer to said second sequence of symbols, said hash table including a plurality of first in, first-out (FIFO) collision chains, having identical numbers of pointers to locations in said memory; and means for generating compressed output data responsive to said means for receiving said first and second sequences of symbols from said memory. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A system for processing digital input data, said input data being divisible into sequences of bits representing symbols, comprising:
-
a memory for holding at least first and second sequences of symbols from said input data, said first sequence having a prefix substring of symbols of a fixed length; means for receiving said first and second sequences of symbols from said memory and determining a length over which said first and second sequences match; means for receiving said prefix substring and computing a hash value therefrom; a hash table for receiving said hash value and providing a pointer to said second sequence of symbol signals, said hash table including a plurality of first in, first-out (FIFO) collision chains, having identical numbers of pointers to locations in said memory; means for generating compressed data responsive to said means for receiving said first and second sequences of symbols from said memory; means for receiving said compressed data; means for decompressing said compressed data received. - View Dependent Claims (7, 8, 9, 10, 11)
-
-
12. A method for processing digital input data, said input data being divisible into symbols, comprising the steps of:
-
receiving input data, including a first sequence of symbols having a prefix substring including fewer symbols than said first sequence; computing a hash value of said prefix substring; obtaining a pointer to a second sequence of symbols in said input data, from a hash table including a plurality of first in, first-out collision chains, having identical numbers of pointers to sequences of symbols; comparing said first and second sequences; and generating compressed data output based on said comparison of said first and second sequences. - View Dependent Claims (13, 14)
-
Specification