Coded data generation or conversion – Digital code to digital code converters – Unnecessary data suppression
Reexamination Certificate
2002-11-06
2004-11-16
Wamsley, Patrick (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Unnecessary data suppression
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
Hewlett--Packard Development Company, L.P.
Wamsley Patrick
LandOfFree
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.
Profile ID: LFUS-PAI-O-3284357