§
Luxuse
Patent Intelligence
Sign In
← Back to Patent Explorer
US5621403A Expired / Lapsed US ⏱️ 0.0 years remaining

Data compression system with expanding window

Assignee: Programmed Logic Corp
•
Filing: 1995-06-20
•
Granted: 1997-04-15
•
Expires: 2015-06-20
📄 Original PDF 🌐 Google Patents 🔄 Sync Now

Abstract

Abstract A method for compressing a block of input data of predetermined length into a compressed block of output which the use of an expanding input data window. The distance, position and length parameters of each matching string found in the expanding input data window are stored as a combined value which have a one-to-one correspondence to both the distance and length of any given point in the input data block. The combined values can be further encoded by use of a Huffman technique or any other appropriate statistical encoding technique. The combining of a matching string's distance and length parameters into a single value takes advantage of the correlation between the distance and length parameters. This correlation allows the single combined value of distance and length to be more efficiently encoded when using statistical encoding techniques. The technique is especially well adapted to compressing blocks of data of relatively small length. The organization of the code in the manner described results in higher compression and a faster implementation.

Inventors

  • 👤 Yuriy Reznik

Bibliographic Details

Application Number —
Jurisdiction US
Data Source google_patents
Last Synchronized 2026-11-05 18:42
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H03; H03M; H03M7/00; H03M7/30; H03M7/3084; H03M7/3086; H03M7/40

Claims Analysis

Total Claims: 8
Claim 1
Independent Claim 159 words
A method for compressing data including N characters in an input block where p is the current position of a character in said block, d is the distance of a matching string in a window of input data, t is a threshold, and l is the length of a given string, said method comprising the steps of: a. determining the distance d of a character string in said block from a substantially identical string in said window of input data; b. performing a transformation that combines d, l, and p of said character string into a single value X; and, c. repeating steps (a) and (b) above until input data is exhausted, thereby producing a plurality of values X i to form a string of compressed data wherein the frequency distribution of the X i values are such that they can be more efficiently encoded by statistical encoding as opposed to encoding d i and l i values separately.
Claim 2
Independent Claim 159 words
A method for compressing data including N characters in an input block where p is the current position of a character in said block, d is the distance of a matching string in a window of input data, t is a threshold, and l is the length of a given string, said method comprising the steps of: a. determining the distance d of a character string in said block from a substantially identical string in said window of input data; b. performing a transformation that combines d, l, and p of said character string into a single value X; and, c. repeating steps (a) and (b) above until input data is exhausted, thereby producing a plurality of values X i to form a string of compressed data wherein the frequency distribution of the X i values are such that they can be more efficiently encoded by statistical encoding as opposed to encoding d i and l i values separately.
Claim 3
Dependent Claim 25 words
The method of claim 1 wherein the size of said window of input data is expandable in relation to the amount of previously compressed data.
Claim 4
Dependent Claim 23 words
The method of claim 2 wherein the size of said expandable window is substantially limited by the following relationships: 0≦p≦N-1 1≦d<p 1≦p≦N-t t≦1≦N-p-1.
Claim 5
Dependent Claim 71 words
The method of claim 3 wherein the value of each X i determined in step (b) above is as follows: P.sub.b =[log.sub.2 p]+1 d=2.spsp.d.sup.b +d.sub.r ; d.sub.b =[log.sub.2 d]; d.sub.r d=2.spsp.d.sup.b X=p.sub.b (l-t)+d.sub.b where: d b --is the largest integer, so that 2.spsp.d b ≦d; d r --is a complement (d r <2.spsp.d b ); p b --is an integer, so that p b >1, and p b >d b .
Claim 6
Dependent Claim 21 words
The method of claim 4 further including the step of: d. Further encoding said values X i determined in step (b).
Claim 7
Dependent Claim 20 words
The method of claim 5 wherein said further encoding step (d) comprises encoding said values X i by Huffman encoding.
Claim 8
Dependent Claim 30 words
The method of claim 6 wherein if a string of length l>t is not found in said expandable input data window then its value is recorded as a literal value.

References Cited (Backward Citations)

US4122440A Cited
US4811265A Cited
US4701745A Cited
US4890326A Cited
US5016009A Cited
US5126739A Cited
US5309526A Cited
US5363096A Cited
US5289895A Cited
US5281967A Cited
US5140321A Cited
US5339076A Cited
US5374916A Cited
US5369605A Cited

USPTO Annuity & Maintenance Windows

Annuity Stage Window Opens Payment Deadline Surcharge Period Until Estimated Fee Status
3.5 Years (Year 4) 2000-04-14 2000-10-14 2001-04-15 $2000.00 Window Closed / Lapsed
7.5 Years (Year 8) 2004-04-14 2004-10-14 2005-04-15 $3760.00 Window Closed / Lapsed
11.5 Years (Year 12) 2008-04-14 2008-10-14 2009-04-15 $7700.00 Window Closed / Lapsed

Assigned Categories & Tags

No categories assigned to this patent yet.

Assign Category Tag