Data compression apparatus and method using matching string searching and Huffman encoding

Claim 2

A data compression method comprising: performing a search for matching strings in a window of input bytes, said search producing a stream of tokens, said tokens representing either a raw byte or a matching string of a certain length and a certain offset back into said window; assigning said tokens to predefined bins, some of said bins containing matching strings of a predetermined length and within a certain offset range; assigning variable length codes to each bin based on the frequency of occurrence of tokens assigned to each bin; outputting for each token generated said variable length codes for said bin to which each token is assigned to the output data stream; and after each said variable length code is output, outputting extra bits, if required, to specify exactly said token within said bin.

Claim 3

The method of claim 1, further comprising: completing said matching string search of all of the input data stream before assigning said variable length codes; counting the occurrences of tokens in each bin from the entire input stream; assigning said variable length codes based on said occurrence counts; producing a coding table which indicates the variable length code assigned to each bin; and outputting said coding table to the output data stream before outputting any encoded tokens.

Claim 4

The method of claim 2, wherein said assigning said variable length codes further comprises assigning said variable length codes using Huffman's algorithm based on said occurrence counts.

Claim 5

The method of claim 3, wherein said producing a coding table further comprises producing a coding table containing only the lengths of said variable length codes.

Claim 6

The method of claim 4, further comprising: compressing said coding table using a run-length compression scheme.

Claim 7

The method of claim 4, further comprising: compressing said coding table using Huffman coding; and generating a preliminary table used to specify the Huffman codes assigned to the various lengths in said coding table.

Claim 8

The method of claim 1, further comprising: assigning a special bin to indicate the end of compressed output data; and outputting the code for said end of compressed output data bin after all other tokens have been output.

Claim 9

The method of claim 1, further comprising assigning said bins as follows: ______________________________________ Bin Number Bin Description ______________________________________ 1-255 Raw bytes 0-255 256-258 String, length 3, 4, 5, offset 1 259-261 String, length 3, 4, 5, offset 2 262-264 String, length 3, 4, 5, offset 3 265-267 String, length 3, 4, 5, offset 4-5 268-270 String, length 3, 4, 5, offset 6-7 271-273 String, length 3, 4, 5, offset 8-11 274-276 String, length 3, 4, 5, offset 12-15 277-279 String, length 3, 4, 5, offset 14-23 280-282 String, length 3, 4, 5, offset 24-31 283-285 String, length 3, 4, 5, offset 32-47 286-288 String, length 3, 4, 5, offset 48-63 289-291 String, length 3, 4, 5, offset 64-95 292-294 String, length 3, 4, 5, offset 96-127 295-297 String, length 3, 4, 5, offset 128-191 298-300 String, length 3, 4, 5, offset 192-255 301-303 String, length 3, 4, 5, offset 256-383 304-306 String, length 3, 4, 5, offset 384-511 307-309 String, length 3, 4, 5, offset 512-767 310-312 String, length 3, 4, 5, offset 768-1023 313-315 String, length 3, 4, 5, offset 1024-1535 316-318 String, length 3, 4, 5, offset 1536-2047 319-333 String, length 6-20 334 String, length 21 and above 335 End of compressed data. ______________________________________

Claim 10

The method of claim 8, further comprising: following codes for bins 256-318 by a certain number of extra bits to specify the string offset, as follows: ______________________________________ Category Number Extra offset bits ______________________________________ 256-264 0 256-270 1 271-276 2 277-282 3 283-288 4 289-294 5 295-300 6 301-306 7 307-312 8 313-318 9. ______________________________________

Claim 11

The method of claim 9, further comprising: following codes for bins 319-334 by extra bits to specify the string offset, as follows: ______________________________________ 00bbbbb Offsets 1-32 01bbbbbbb Offsets 33-160 10bbbbbbbbb Offsets 161-672 11bbbbbbbbbbb Offsets 673-2047. ______________________________________

Claim 12

The method of claim 10, further comprising: following the code and offset bits for bin 334 by extra bits to specify the string length, as follows: __________________________________________________________________________ String Length Extra Length Bits __________________________________________________________________________ 21 0000 22 0001 23 0010 24 0011 25 0100 . . . . . . 35 1110 36 1111 00000000 37 1111 00000001 38 1111 00000010 . . . . . . 290 1111 11111110 291 1111 11111111 000000000000 292 1111 11111111 000000000001 293 1111 11111111 000000000010 . . . . . . 4387 1111 11111111 111111111110 4388 1111 11111111 111111111111 0000000000000000 4389 1111 11111111 111111111111 0000000000000001 . . . . . . 69922 1111 11111111 111111111111 1111111111111110 69923 1111 11111111 111111111111 1111111111111110 0000000000000000 69924 1111 11111111 111111111111 1111111111111110 0000000000000001. __________________________________________________________________________

Claim 13

A data decompression method which decompresses a compressed input data stream, comprising: maintaining a history array of all bytes output; and repeating the following steps until the input data stream is exhausted or until a code indicating the end of said compressed input data stream is encountered: extracting a bin code from said compressed input data stream; extracting any extra bits required to determine exactly the token associated with said bin code; operative when said token corresponds to a raw byte, outputting said raw byte; and operative when said token corresponds to a matching string, outputting all bytes of said string by indexing back into said history array using the offset of said string.

Claim 14

A data decompression method which decompresses a compressed input data stream, comprising: maintaining a history array of all bytes output; and repeating the following steps until the input data stream is exhausted or until a code indicating the end of said compressed input data stream is encountered: extracting a bin code from said compressed input data stream; extracting any extra bits required to determine exactly the token associated with said bin code; operative when said token corresponds to a raw byte, outputting said raw byte; and operative when said token corresponds to a matching string, outputting all bytes of said string by indexing back into said history array using the offset of said string.

Claim 15

The method of claim 12, further comprising: extracting a coding table from the beginning of said compressed input data stream; and extracting said variable length codes for said categories from said coding table.

Claim 16

A data compression apparatus comprising: means for performing a search for matching strings in a window of input bytes, said search producing a stream of tokens, said tokens representing either a raw byte or a matching string of a certain length and a certain offset back into said window; means for assigning said tokens to predefined bins, some of said bins containing matching strings of a predetermined length and within a certain offset range; means for assigning variable length codes to each bin based on the frequency of occurrence of tokens assigned to each bin; means for outputting for each token generated said variable length codes for said bin to which each token is assigned to the output data stream; and means for outputting extra bits, if required, to specify exactly said token within said bin.

Claim 17

A data compression apparatus comprising: means for performing a search for matching strings in a window of input bytes, said search producing a stream of tokens, said tokens representing either a raw byte or a matching string of a certain length and a certain offset back into said window; means for assigning said tokens to predefined bins, some of said bins containing matching strings of a predetermined length and within a certain offset range; means for assigning variable length codes to each bin based on the frequency of occurrence of tokens assigned to each bin; means for outputting for each token generated said variable length codes for said bin to which each token is assigned to the output data stream; and means for outputting extra bits, if required, to specify exactly said token within said bin.

Claim 18

The apparatus of claim 14, further comprising: means for completing said matching string search of all of the input data stream before assigning said variable length codes; means for counting the occurrences of tokens in each bin from the entire input stream; means for assigning said variable length codes based on said occurrence counts; means for producing a coding table which indicates the variable length code assigned to each bin; and means for outputting said coding table to the output data stream before outputting any encoded tokens.

Claim 19

The apparatus of claim 15, wherein said means for assigning said variable length codes further comprises means for assigning said variable length codes using Huffman's algorithm based on said occurrence counts.

Claim 20

The apparatus of claim 16, wherein said means for producing a coding table further comprises means for producing a coding table containing only the lengths of said variable length codes.

Claim 21

The apparatus of claim 17, further comprising: means for compressing said coding table using a run-length compression scheme.

Claim 22

The apparatus of claim 17, further comprising: means for compressing said coding table using Huffman coding; and means for generating a preliminary table used to specify the Huffman codes assigned to the various lengths in said coding table.

Claim 23

The apparatus of claim 14, further comprising: means for assigning a special bin to indicate the end of compressed output data; and means for outputting the code for said end of compressed output data bin after all other tokens have been output.

Claim 24

The apparatus of claim 14, further comprising means for assigning said bins as follows: ______________________________________ Bin Number Bin Description ______________________________________ 0-255 Raw bytes 0-255 256-258 String, length 3, 4, 5, offset 1 259-261 String, length 3, 4, 5, offset 2 262-264 String, length 3, 4, 5, offset 3 265-267 String, length 3, 4, 5, offset 4-5 268-270 String, length 3, 4, 5, offset 6-7 271-273 String, length 3, 4, 5, offset 8-11 274-276 String, length 3, 4, 5, offset 12-15 277-279 String, length 3, 4, 5, offset 16-23 280-282 String, length 3, 4, 5, offset 24-31 283-285 String, length 3, 4, 5, offset 32-47 286-288 String, length 3, 4, 5, offset 48-63 289-291 String, length 3, 4, 5, offset 64-95 292-294 String, length 3, 4, 5, offset 96-127 295-297 String, length 3, 4, 5, offset 128-191 298-300 String, length 3, 4, 5, offset 192-255 301-303 String, length 3, 4, 5, offset 256-383 304-306 String, length 3, 4, 5, offset 384-511 307-309 String, length 3, 4, 5, offset 512-767 310-312 String, length 3, 4, 5, offset 768-1023 313-315 String, length 3, 4, 5, offset 1024-1535 316-318 String, length 3, 4, 5, offset 1536-2047 319-333 String, length 6-20 334 String, length 21 and above 335 End of compressed data. ______________________________________

Claim 25

The apparatus of claim 21, further comprising: means for following codes for bins 256-318 by a certain number of extra bits to specify the string offset, as follows: ______________________________________ Category Number Extra offset bits ______________________________________ 256-264 0 256-270 1 271-276 2 277-282 3 283-288 4 289-294 5 295-300 6 301-306 7 307-312 8 313-318 9. ______________________________________

Claim 26

The apparatus of claim 22, further comprising: means for following codes for bins 319-334 by extra bits to specify the string offset, as follows: ______________________________________ 00bbbbb Offsets 1-32 01bbbbbbb Offsets 33-160 10bbbbbbbbb Offsets 161-672 11bbbbbbbbbbb Offsets 673-2047. ______________________________________

Claim 27

The apparatus of claim 23, further comprising: means for following the code and offset bits for bin 334 by extra bits to specify the string length, as follows: __________________________________________________________________________ String Length Extra Length Bits __________________________________________________________________________ 21 0000 22 0001 23 0010 24 0011 25 0100 . . . . . . 35 1110 36 111 00000000 37 1111 00000001 38 1111 00000010 . . . . . . 290 1111 11111110 291 1111 11111111 000000000000 292 1111 11111111 000000000001 293 1111 11111111 000000000010 . . . . . . 4387 1111 11111111 111111111110 4388 1111 11111111 111111111111 0000000000000000 4389 1111 11111111 111111111111 0000000000000001 69922 1111 11111111 111111111111 1111111111111110 69923 1111 11111111 111111111111 1111111111111110 0000000000000000 69924 1111 11111111 111111111111 1111111111111110 0000000000000001. __________________________________________________________________________

Claim 28

A data decompression method which decompresses a compressed input data stream, comprising: means for maintaining a history array of all bytes output; and means for extracting a bin code from said compressed input data stream; means for extracting any extra bits required to determine exactly the token associated with said bin code; means for outputting a raw byte; and means for outputting all bytes of a matching string by indexing back into said history array using the offset of said string.

Claim 29

A data decompression method which decompresses a compressed input data stream, comprising: means for maintaining a history array of all bytes output; and means for extracting a bin code from said compressed input data stream; means for extracting any extra bits required to determine exactly the token associated with said bin code; means for outputting a raw byte; and means for outputting all bytes of a matching string by indexing back into said history array using the offset of said string.

Claim 30

The apparatus of claim 25, further comprising: means for extracting a coding table from the beginning of said compressed input data stream; and means for extracting said variable length codes for said categories from said coding table.