System, method and computer readable medium for compressing...

Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C341S051000

Reexamination Certificate

active

06819272

ABSTRACT:

BACKGROUND
This invention relates to data compression, and more particularly, to a system and a method for compressing a data sequence to produce an output codestream that allows partial decompressing to obtain an intermediate segment of the data sequence.
Data compression techniques are used to reduce the amount of data to be stored or transmitted in order to reduce the storage capacity and transmission time respectively. In either case it is necessary to provide a corresponding decompression technique to enable the original data to be reconstructed.
Many data compression and decompression techniques are known, with the Lempel-Ziv (LZ) technique and its variants proving to be very popular. U.S. Pat. No. 4,558,302, Welch, entitled “High Speed Data Compression and Decompression Apparatus and Method;” U.S. Pat. No. 4,701,745, Waterworth, entitled “Data Compression System;” and U.S. Pat. No. 4,814,746, Miller et al., entitled “Data Compression Method” are patents that disclose some of these LZ techniques. One of the LZ variants is known as the LZ Opperhumer (LZO) technique.
FIG. 1
shows an output codestream obtained by compressing an input character sequence using the LZO technique. The output codestream includes codewords interspersed with non-matchable sequences of characters from the input character sequence. The codewords reference sequences of characters which have previously appeared when decompressing the output codestream to allow the original input character sequence to be rebuilt from the codestream.
The LZ techniques are known as a dictionary-based technique. In this technique, a running dictionary is generated during both compression and decompression. To obtain an intermediate segment of an input character sequence from an output codestream, it is necessary to begin decompression from the start of the output codestream until the desired intermediate segment is obtained. Partial decompression of the output codestream is not possible with the prior art LZ techniques.
SUMMARY
According to an aspect of the present invention, there is provided a method for compressing an input sequence of data portions to produce an output codestream and for partially decompressing the output codestream to obtain a selected segment of the input sequence. The method includes compressing the input sequence to produce the output codestream of non-matchable sequences and codewords. The codewords include a first codeword and subsequent codewords. Each of the codewords includes at least a length of a non-matchable sequence preceding a matchable first sequence. Each of the subsequent codewords further includes a first offset for indicating a start of the matchable first sequence in the preceding non-matchable sequence, a length of the matchable first sequence and a second offset for indicating a location of a preceding codeword in the output codestream.
According to another aspect of the present invention, there is provided a compressing/decompressing system having means for compressing an input sequence of data portions as described above.
According to another aspect of the present invention, there is provided a program storage device readable by a computing device. The program storage device tangibly embodies a program of instructions that is executable by the computing device to perform the above method for compressing/decompressing an input sequence of data portions.


REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 4701745 (1987-10-01), Waterworth
patent: 4814746 (1989-03-01), Miller et al.
patent: 5760716 (1998-06-01), Mathews et al.
patent: 5813011 (1998-09-01), Yoshida et al.
patent: 6195741 (2001-02-01), Asato
patent: 6236960 (2001-05-01), Peng et al.
patent: 6271776 (2001-08-01), Turk et al.
patent: 6279092 (2001-08-01), Franaszek et al.
patent: 6396420 (2002-05-01), Augustine
patent: 6501395 (2002-12-01), Ghildiyal
patent: WO 02/08956 (2002-01-01), None

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

System, method and computer readable medium for compressing... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System, method and computer readable medium for compressing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System, method and computer readable medium for compressing... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3284357

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.