Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
1998-09-25
2001-10-09
Boudreau, Leo (Department: 2721)
Image analysis
Image compression or coding
Lossless compression
C382S245000, C341S051000, C341S087000
Reexamination Certificate
active
06301394
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of data compression. More specifically, the invention provides a system for reordering data prior to compressing the data and an improved method of storing self relative references to the previous data stream (lean index method).
BACKGROUND
Various data compression procedures have been developed to reduce the size of a particular collection of data. By reducing the size of a collection of data, the storage requirements for the data are reduced. Similarly, compressing data allows data to be transmitted more efficiently in situations where transmission bandwidth is restricted. Some data compression procedures are “lossless” while others are “lossy”. A lossless compression procedure ensures that, when the compressed data is uncompressed, the uncompressed data is identical to the original data. Lossless compression procedures are often used with text streams and other data streams that cannot suffer a loss of data. A lossy compression procedure may sacrifice a portion of the original data in exchange for a better rate of compression. Lossy compression procedures are useful in situations where a slight degradation of the data will not significantly change the usefulness of the data. Lossy compression procedures are often used to compress pictures and sound.
An existing data compression procedure is referred to as run-length encoding. Run-length encoding converts a string of identical characters into a single code element. Using the run-length encoding procedure, the string “A B C C C C C C C A C B A” would be compressed to “A B !
7
C A C B A”, where “!
7
C” represents the code for a string of seven “C” characters.
Another existing data compression procedure is commonly referred to as the Lempel-Ziv (LZ) technique. The basic LZ technique replaces an occurrence of a particular phrase or sequence of bytes in a set of data with a reference to a previous instance of the phrase or sequence. Thus, a phrase or sequence is replaced by a reference to an earlier part of the data stream. The basic LZ technique is illustrated with the following example. The phrase: The Yabba Dabba Show is replaced with: T, h, e, <space>, Y, a, b, b, a, <space>, D, <
6
,
5
>, S, h, o, w Where <space>indicates a single space and <
6
,
5
>represents the code for position
6
, length
5
(i.e., the 5-character string beginning at position
6
(the first “a” in “Yabba”)).
Existing data compression procedures analyze a data stream or other collection of data without reordering or rearranging the original data. Additionally, existing data compression procedures do not generally analyze the data stream or other collection of data to identify data elements that change infrequently or that change incrementally.
It is therefore desirable to provide a data compression system that takes advantage of relationships between multiple data elements in a collection of data and reorders the data based on those relationships prior to compressing the data.
SUMMARY OF THE INVENTION
An apparatus and method for compressing data is disclosed. The apparatus and method comprise: 1) analysis of the data to identify a relationship between a plurality of data elements in the data, 2) reordering the data based on the identified relationship between the plurality of data elements, and 3) identifying common sequences in the reordered data and storing these references using a lean index. The apparatus and method of the present invention further includes reordering the data to arrange related data elements adjacent to one another, and compressing the reordered data to generate a compressed data set.
REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 4971407 (1990-11-01), Hoffman
patent: 5254990 (1993-10-01), Yoshida et al.
patent: 5488364 (1996-01-01), Cole
patent: 5608396 (1997-03-01), Cheng et al.
patent: 5627534 (1997-05-01), Craft
patent: 5635932 (1997-06-01), Shinagawa et al.
patent: 5673042 (1997-09-01), Yoshida et al.
patent: 5841376 (1998-11-01), Hayashi
patent: 5936560 (1999-10-01), Higuchi
patent: 6075470 (2000-06-01), Little et al.
Bell, Timothy; Cleary, John; Witten, Ian, “Text Compresion” (1990), Chapter 8, pp. 206-243.
Anzus, Inc.
Blakely , Sokoloff, Taylor & Zafman LLP
Boudreau Leo
Sherali Ishrat
LandOfFree
Method and apparatus for 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 Method and apparatus for compressing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compressing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579902