US5473326A — High speed lossless data compression method and a…

Claim 1

Independent Claim 116 words

A method for compressing a byte stream of input data, comprising: establishing a multiple-byte buffer and sequentially transferring bytes from said byte stream into said buffer; establishing a multiple-byte first comparison window and sequentially transferring bytes from said byte stream into said first comparison window; establishing a multiple-byte second comparison window to receive some but not all of the bytes from said byte stream; comparing a byte in the buffer against the bytes in the first comparison window and the second comparison window; substituting a pointer for the compared byte in the buffer if the compared byte matches a byte in the first or second comparison window; and outputting said substituted pointer into an output stream.

Claim 2

Independent Claim 116 words

A method for compressing a byte stream of input data, comprising: establishing a multiple-byte buffer and sequentially transferring bytes from said byte stream into said buffer; establishing a multiple-byte first comparison window and sequentially transferring bytes from said byte stream into said first comparison window; establishing a multiple-byte second comparison window to receive some but not all of the bytes from said byte stream; comparing a byte in the buffer against the bytes in the first comparison window and the second comparison window; substituting a pointer for the compared byte in the buffer if the compared byte matches a byte in the first or second comparison window; and outputting said substituted pointer into an output stream.

Claim 3

Dependent Claim 32 words

The method of claim 1, wherein said second comparison window receives bytes from said byte stream, only if said byte is not part of a multiple-byte match against the first comparison window.

Claim 4

Dependent Claim 28 words

The method of claim 2, wherein the second comparison window receives bytes from said byte stream, only if said byte is not then in the second comparison window.

Claim 5

Dependent Claim 78 words

The method of claim 3, wherein the second comparison window includes bytes transferred from the byte stream and received by the second comparison window, arranged in a linear array of byte positions from an oldest received byte to a newest received byte, and when a new byte is received the oldest byte is deleted and the other bytes are shifted one byte position toward the oldest byte position to open the newest byte position for the new byte.

Claim 6

Dependent Claim 68 words

The method of claim 2, wherein the buffer includes bytes transferred from the byte stream and received by the buffer, arranged in a linear array of byte positions from an oldest received byte to a newest received byte; wherein the byte in the buffer that is compared against the bytes in the first comparison window and the second comparison window is the byte in the oldest byte position.

Claim 7

Dependent Claim 128 words

The method of claim 5, further comprising the steps of: deleting said compared byte from the buffer and shifting the buffer bytes one position toward the oldest position to establish another oldest received byte and to open the newest byte position, and adding a new byte from said byte stream to the newest position upon completion of said comparison; comparing said another oldest byte against the bytes in the first comparison window and the second comparison window; substituting a pointer for the compared byte in the buffer if the compared byte matches a byte in a comparison window; outputting said substituted pointer into an output stream; and repeating said steps until all the bytes in the byte stream have been compared with the bytes in the comparison windows.

Claim 8

Dependent Claim 84 words

The method of claim 6, wherein the first comparison window includes bytes transferred from the byte stream and received by the first comparison window, arranged in a linear array of byte positions from an oldest received byte to a newest received byte; and wherein when a new byte is received by the first comparison window the oldest byte is deleted and the other first comparison window bytes are shifted toward the oldest byte position to open the newest byte for the newest byte position.

Claim 9

Dependent Claim 44 words

The method of claim 7, wherein the bytes in the buffer and the first comparison window are arranged such that the bytes in the buffer array together with the bytes in the first comparison window array constitute a continuous segment of the byte stream.

Claim 10

Dependent Claim 35 words

The method of claim 6, further comprising substituting for a series of more than one consecutive buffer bytes, a symbol indicating the number of consecutive buffer bytes that were matched with first comparison window bytes.

Claim 11

Dependent Claim 31 words

The method of claim 1, further comprising uncompressing the output stream by utilizing said pointers to locate a byte in a comparison window, and substituting said located byte for the pointer.

Claim 12

Dependent Claim 14 words

The method of claim 1, wherein the first comparison window contains approximately 256 bytes.

Claim 13

Dependent Claim 14 words

The method of claim 1, wherein the second comparison window contains approximately 32 bytes.

Claim 14

Dependent Claim 36 words

The method of claim 1, wherein the substituted pointer includes a symbol to indicate which of the comparison windows contains said match and a symbol to indicate a location of said match in said comparison window.

Claim 15

Dependent Claim 28 words

The method of claim 13, wherein a substituted pointer to indicate a match in the first comparison window includes a symbol to indicate a length of the match.

Claim 16

Dependent Claim 62 words

The method of claim 14, wherein said symbol to indicate the length of the match is a binary symbol in which a two-byte length is indicated by 01, a three-byte length is indicated by 10, a four-byte length is indicated by 11, and a length of more than four-bytes is indicated by 00 together with a string of at least five bits.

Claim 17

Dependent Claim 37 words

The method of claim 1, wherein the comparison of a byte against the bytes in the first comparison window is done simultaneously with the comparison of the same byte against the bytes in the second comparison window.

Claim 18

Dependent Claim 43 words

The method of claim 16, wherein a result of the comparison of a byte against the bytes in the first comparison window is encoded to establish said pointer simultaneously with the comparison of said byte against the bytes in the second comparison window.

Claim 19

Dependent Claim 27 words

The method of claim 17, wherein each byte of said byte stream is replaced with a substituted pointer indicating a match in one of said comparison windows.

Claim 20

Independent Claim 143 words

A system for compressing a byte stream of input data, comprising a buffer having at least one byte position; a first comparison window having at least one byte position; a second comparison window having at least one byte position; means for comparing a byte in the buffer against bytes in the comparison windows to determine a matching byte in the first comparison window or the second comparison window; means operatively connected to the comparison windows for generating a pointer indicating the location in a comparison window of the matched byte in the comparison window; means for substituting the pointer for the matched byte in the buffer; and means for updating the comparison windows whereby the first comparison window receives each byte in the byte stream sequentially and the second comparison window receives only those bytes in the byte stream that satisfy pre-established conditions.

Claim 21

Independent Claim 143 words

A system for compressing a byte stream of input data, comprising a buffer having at least one byte position; a first comparison window having at least one byte position; a second comparison window having at least one byte position; means for comparing a byte in the buffer against bytes in the comparison windows to determine a matching byte in the first comparison window or the second comparison window; means operatively connected to the comparison windows for generating a pointer indicating the location in a comparison window of the matched byte in the comparison window; means for substituting the pointer for the matched byte in the buffer; and means for updating the comparison windows whereby the first comparison window receives each byte in the byte stream sequentially and the second comparison window receives only those bytes in the byte stream that satisfy pre-established conditions.

Claim 22

Dependent Claim 104 words

The system of claim 19, wherein the buffer includes a plurality of buffer byte positions for bytes transferred sequentially from the byte stream and received by the buffer, the buffer byte positions being arranged in a linear array from an oldest received buffer byte position to a newest received buffer byte position, and further comprising means for updating the buffer by deleting the buffer byte in the oldest buffer byte position and shifting the other buffer bytes toward the oldest buffer byte position to open the newest buffer byte position and transferring a byte from the byte stream into the newest buffer byte position.

Claim 23

Dependent Claim 102 words

The system of claim 20, wherein the first comparison window includes a plurality of first comparison window byte positions arranged in a linear array from an oldest received first comparison window byte position to a newest received first comparison window byte position, and wherein said comparison window updating means includes means for deleting a first comparison window byte in the oldest position and shifting the other first comparison window bytes toward the oldest first comparison window byte position to open the newest first comparison window byte position, and transferring a deleted buffer byte into said open newest first comparison window byte position.

Claim 24

Dependent Claim 45 words

The system of claim 21, further comprising means for generating a length of match symbol if a plurality of consecutive buffer bytes match first comparison window bytes, whereby the length of match symbol indicates the number of bytes in said plurality of consecutive buffer bytes.

Claim 25

Dependent Claim 60 words

The system of claim 22, wherein said preestablished conditions include at least one of the conditions that the bytes to be received by the second comparison window do not match any plurality of consecutive bytes in the first comparison window and that the byte to be received by the second comparison window is not already in the second comparison window.

Claim 26

Dependent Claim 103 words

The system of claim 23, wherein the second comparison window includes a plurality of second comparison window byte positions arranged in a linear array from an oldest received second comparison window byte position to a newest received second comparison window byte position, and wherein said comparison window updating means includes means for deleting the byte in the oldest second comparison window byte position and shifting the other second comparison window bytes toward the oldest second comparison window byte position to open the newest second comparison window byte position, and transferring into said newest second comparison window byte positioned a byte satisfying said condition.

Claim 27

Dependent Claim 19 words

The system of claim 24, further comprising means for establishing a compressed data output including said pointer and symbol.

Claim 28

Dependent Claim 31 words

The system of claim 25, further comprising data uncompressing means for uncompressing the compressed data output whereby the uncompressed output is substantially the same as the byte stream of input data.

Claim 29

Dependent Claim 31 words

The system of claim 26, wherein said uncompressing means includes means for utilizing said pointer to locate a byte in a comparison window, and for substituting said byte for said pointer.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1998-12-04	1999-06-05	1999-12-05	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2002-12-04	2003-06-05	2003-12-05	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2006-12-04	2007-06-05	2007-12-05	$7700.00	Window Closed / Lapsed

High speed lossless data compression method and apparatus using side-by-side sliding window dictionary and byte-matching adaptive dictionary

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag