Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
1999-08-04
2001-07-31
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
C341S087000, C382S232000
Reexamination Certificate
active
06268809
ABSTRACT:
TECHNICAL FIELD
The present invention generally relates to a data compression method and, more particularly, to a data compression method of efficiently compressing particularly image data using a data compression technique based on a dictionary-based method that is represented by LZ77 and LZ78.
BACKGROUND ART
Current data compression methods of compressing data by a dictionary-based method are derived from Abraham Lempel and Jacob Ziv, “A Universal Algorithm for Sequential Data Compression”, IEEE Transaction on Information Theory (1977).
This method is generally called a Lempel-Ziv encoding slide dictionary method or LZ77 method.
The LZ77 method is introduced in, e.g., Seiji Munakata, “Ziv-Lempel Data Compression Method”, Information Processing, Vol. 26, No. 1 (1985).
The LZ77 algorithm is a method of segmenting data to be encoded into a stream having a maximum matching length from an arbitrary position of a past data stream, and encoding the segmented stream as a copy of the past stream.
More specifically, as shown in
FIG. 3
, the LZ77 algorithm uses a moving window storing encoded input data and a prefetch buffer storing data to be encoded, and collates all partial sequences of a data sequence in the moving window with those in the prefetch buffer to obtain a matching partial sequence having a maximum length in the moving window.
To designate a partial sequence having a maximum length in the moving window, a combination of “the start position of a partial sequence having a maximum length”, “a matching length”, and “a next symbol which cancels matching” are encoded.
An encoded data sequence in the prefetch buffer is moved to the moving window, and a new data sequence corresponding to the encoded data sequence is input to the prefetch buffer.
The same processing is repeated to decompose data into partial sequences and encode the partial sequences.
Many improvements of this basic data compression technique have been proposed.
For example, there is an LZSS encoding method of setting a flag for identifying whether data is an encoded code or raw data and when the encoded data is longer than the raw data, encoding the raw data (T. C. Bell, “Better OPM/L Text Compression”, IEEE Transaction Commun., Vol. COM-34, No. 12, Dec. (1986)).
Another reference is M. Nelson, “Data Compression Handbook: Second Edition”, Toppan (1996), ISBN4-8101-8605-9.
In resent years, OA systems (scanners, printers, digital copying machines, and the like) are becoming popular, and higher speeds and higher resolutions are required.
These systems must process large-amount image data at a high speed, so that they must reduce the processing data amount by compressing data at a high speed and high compression ratio.
The conventional data compression technique includes standard methods such as MMR and JBIG. However, MMR tends to decrease the compression ratio for a fine image.
JBIG, which attains almost the highest compression ratio, basically processes data in units of pixels, is limited in an increase in speed, and thus cannot be employed in high-speed systems.
The above dictionary-based compression method basically processes data in units of bytes, can attain a much higher speed than JBIG, can keep the compression ratio for a fine image in comparison with MMR, and is suitable for high-speed, high-resolution OA systems.
In encoding, however, a conventional LZ77-based data compression apparatus must compare a data sequence to be encoded with data sequences starting from all positions in the moving window in order to obtain a matching partial data sequence having a maximum length in the moving window.
More specifically, as shown in
FIG. 3
, a data sequence to be encoded is compared with a data sequence starting from the position of offset 1 in the moving window, a data sequence starting from the position of offset 2, . . . , and a data sequence starting from the position of offset n (n is the size of the moving window), thereby finding an offset having a maximum matching length.
Hardware which implements this at a high speed is disclosed in U.S. Pat. No. 5,003,307.
As shown in
FIG. 4
, this hardware implements a moving window having a moving window size of n by n shift registers SR
1
to SRn, and parallel-processes n comparisons using n comparators CMP
1
to CMPn.
This method can advantageously process one data by one clock, but requires comparators equal in number to the moving window size and becomes difficult to realize for a larger moving window size.
For example, for a moving window size of 2 kB, this conventional method requires 2 k comparators.
DISCLOSURE OF INVENTION
The present invention has been made in consideration of the above situation, and has as its object to provide an improvement of an apparatus and method for comparing dictionary data with input data to encode matching data and decoding encoded compressed data in a data processing apparatus and data processing method and, more particularly, to provide an LZ77-based data compression method with a small number of comparators based on image data periodicity.
It is another object of the present invention to provide a data compression method for performing pre-processing of rearranging data based on image data periodicity so as to allow data having high matching possibility to come close to each other.
To achieve the above objects, according to one aspect of the present invention, there is provided a data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of:
storing encoded input data in a moving window having a predetermined size,
comparing a partial sequence starting from a given position (entry) in the moving window with a data sequence to be encoded by a plurality of comparators,
finding an entry having a maximum matching length by a matching finder in comparison by the plurality of comparators, and
encoding a pair of offsets up to the entry and a matching length (offsets and matching length) by a matching code generator when matching is found by the matching finder,
wherein the number of comparators is smaller than the size of the moving window, and some of offsets near offset 0 (0 indicates including no offset), offsets near offset L, offsets near offset 2L, offsets near offsets 3L, . . . are used as entries.
To achieve the above objects, according to another aspect of the present invention, there is provided a data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of:
rearranging by a pre-processing unit a byte order of the input data stream:
0, 1, 2, 3, . . . , L, L+1, L+2, . . . , 2L, 2L+1, 2L+2, . . . into
0, L, 2L, . . . , nL, 1, l+1, 2L+1, . . . , nL+1, 2, L+2, 2L+2, . . . , nL+2, . . . (n=1, 2, . . . ), and
compressing the input data stream rearranged by the pre-processing unit and outputting the encoded stream from a compression type compression apparatus main body.
To achieve the above objects, according to still another aspect of the present invention, there is provided a data compression method for compressing an input data stream and outputting the encoded stream, comprising the steps of: rearranging by a pre-processing unit an order of m-bit bytes (m=p×q; p is an integer not less than 1 and q is an integer not less than 2) of the input data stream:
First Line: 0, 1, 2, . . . ,
Second Line: L, L+1, L+2, . . . ,
. . . . . .
qth Line: (q−1)L, (q−1)L+1, (q−1)L+2, . . . , qL−1
into
a new first byte made up of
m
bits:
0 : b(0), . . . , 0 : b(p−1),
L : b(0), . . . , L : b(p−1),
. . . . . .
(q−1)L : b(0), . . . , (q−1)L : b(p−1)
a new second byte made up of
m
bits:
0 : b(0), . . . , 0 : b(2p−1),
L : b(0), . . . , L : b(2p−1),
. . . . . .
(q−1)L : b(0), . . . , (q−1)L : b(2p−1)
. . . . . .
a new qth byte made up of
m
bits:
0 : b((q−1)p), . . . , 0 : b(qp−1),
L : b((q−1)p), . . . , L : b(q2p−1),
. . . . . .
(q&
Foley & Lardner
Kabushiki Kaisha Toshiba
Williams Howard L.
LandOfFree
Data compression method for efficiently compressing data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data compression method for efficiently compressing data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data compression method for efficiently compressing data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2488297