Method of decoding compressed data

Claim 1

A method of parsing a free-form bit stream into a sequence of literal references, history references, and lexicon references, which comprises the steps of: a) reading the first bit of said bit stream; b) emitting a literal reference if said first bit is a zero; c) reading the second bit of said bit stream if said first bit is a one; d) emitting a history reference if said second bit is a zero and said first bit is a one; and e) emitting a lexicon reference if said second bit is a one and said first bit is a one.

Claim 2

A method of parsing a free-form bit stream into a sequence of literal references, history references, and lexicon references, which comprises the steps of: a) reading the first bit of said bit stream; b) emitting a literal reference if said first bit is a zero; c) reading the second bit of said bit stream if said first bit is a one; d) emitting a history reference if said second bit is a zero and said first bit is a one; and e) emitting a lexicon reference if said second bit is a one and said first bit is a one.

Claim 3

A method of decoding a compressed free-form data stream made up of a sequence of literal references, lexicon references and history references, which comprises the steps of: a) reading the first bit of said sequence; b) reading the next eight bits of said sequence and emitting the symbol represented by said eight bits if said first bit is a zero; c) inserting the symbol emitted in step b) in a history buffer; d) noting the current size of said history buffer; e) reading the second bit of said sequence if said first bit is a one; f) if said second bit is a zero, reading the next number of bits of said sequence equal to the base two logarithm, rounded up to the nearest integer, of said current size of said history buffer, said number of bits identifying an offset into said history buffer, then reading the next number of bits of said sequence equal to the base two logarithm, rounded up to the nearest integer, of a preselected maximum history reference length, said number of bits identifying a length of a symbol string in said history buffer, and then emitting the string of symbols from said history buffer identified by said offset and length values; g) inserting the string emitted in step f) in said history buffer; h) noting the current size of said history buffer; i) inserting the string emitted in step f) in a lexicon; j) noting the current size of said lexicon; k) if said second bit is a one, reading the next number of bits from said sequence equal to the base two logarithm, rounded up to the nearest integer, of said current size of said lexicon, said number of bits representing an index into said lexicon, and emitting the string of symbols from said lexicon identified by said index; l) inserting the string emitted in step k) in said history buffer; m) noting the current size of said history buffer; and n) repeating steps a) through m) until said sequence is exhausted.

Claim 4

A method of decoding a compressed free-form data stream made up of a sequence of literal references, lexicon references and history references, which comprises the steps of: a) reading the first bit of said sequence; b) reading the next eight bits of said sequence and emitting the symbol represented by said eight bits if said first bit is a zero; c) inserting the symbol emitted in step b) in a history buffer; d) noting the current size of said history buffer; e) reading the second bit of said sequence if said first bit is a one; f) if said second bit is a zero, reading the next number of bits of said sequence equal to the base two logarithm, rounded up to the nearest integer, of said current size of said history buffer, said number of bits identifying an offset into said history buffer, then reading the next number of bits of said sequence equal to the base two logarithm, rounded up to the nearest integer, of a preselected maximum history reference length, said number of bits identifying a length of a symbol string in said history buffer, and then emitting the string of symbols from said history buffer identified by said offset and length values; g) inserting the string emitted in step f) in said history buffer; h) noting the current size of said history buffer; i) inserting the string emitted in step f) in a lexicon; j) noting the current size of said lexicon; k) if said second bit is a one, reading the next number of bits from said sequence equal to the base two logarithm, rounded up to the nearest integer, of said current size of said lexicon, said number of bits representing an index into said lexicon, and emitting the string of symbols from said lexicon identified by said index; l) inserting the string emitted in step k) in said history buffer; m) noting the current size of said history buffer; and n) repeating steps a) through m) until said sequence is exhausted.