Method and system for selecting grammar symbols for variable length data compressors
AssigneeMicrosoft Corporation
InventorsStephen Robert Adams, Thomas Dee McGuire
Life of this patent
Estimating the term…
Abstract
A data compression method and system replaces pairs of symbols in a string of symbols by a single new symbol. A method for selecting the pairs of symbols to be replaced employs a modified greedy algorithm. The method selects a next best pair of symbols for replacement by considering pairs that have a potential for usurping a current best candidate pair of symbols, due to their frequency of occurrence. A minimum savings threshold is evaluated to further avoid exhaustive searches of all possible pairs of symbols.
Claims28
A computer-readable medium having computer executable instructions for compressing symbols in a string of symbols, comprising:
- generating sequences of symbols from the string of symbols, wherein the sequences of symbols are ordered according to an associated frequency of occurrence of each sequence of symbols in the string of symbols;
- selecting a current candidate replacement sequence from the ordered sequences of symbols;
- determining a target cost savings and a minimum frequency of occurrence associated with the current candidate replacement sequence, the target cost savings being associated with a reduction in an encoded length in the string of symbols resulting from replacing the candidate replacement sequence with another symbol;
- and
- for other sequences of symbols in the ordered sequence of symbols having an associated frequency of occurrence that is greater than the minimum frequency of occurrence, performing actions including:
- identifying an alternative candidate replacement sequence, wherein the identified alternative candidate sequence has an associated cost savings that is greater than the target cost savings;
- and
- replacing the identified alternative candidate replacement sequence in the string of symbols by the other symbol.
A computer-readable medium having computer executable components for compressing symbols in a string of symbols, comprising:
- a symbol sequence picker configured to:
- generate sequences of symbols from the string of symbols, wherein the sequences of symbols are ordered according to an associated frequency of occurrence in the string of symbols;
- select a current candidate replacement sequence from the ordered sequences of symbols as;
- determine a target cost savings and a minimum frequency of occurrence associated with the current candidate replacement sequence, the target cost savings being associated with a reduction in an encoded length of the string of symbols resulting from replacing the candidate replacement sequence with another symbol;
- and
- for other sequences of symbols in the ordered sequence of symbols having an associated frequency of occurrence that is greater than the minimum frequency of occurrence:
- identify an alternative candidate replacement sequence, wherein the identified alternative candidate sequence has an associated cost savings that is greater than the target cost savings;
- and
- replace the identified alternative candidate replacement sequence in the string of symbols by the other symbol.
A computer-implemented method for transmitting a compressed data file, comprising:
- building a list of decompression information that has relevance to each of a plurality of strings of symbols;
- and
- transmitting the list of decompression information in conjunction with a request for at least one of the plurality of strings of symbols.
A computer-readable medium encoded with a data structure for use in communicating a compressed file, the data structure comprising:
- a plurality of compressed files, wherein at least two files in the plurality of compressed files include a symbol representing a sequence of symbols;
- and
- a shared information header including a grammar rule for use in decompressing each of the plurality of compressed files, wherein the grammar rule comprises a mapping of the symbol to the sequence of symbols.
An apparatus for transmitting a compressed data file, comprising:
- a means for building a list of decompression information that has relevance to each of a plurality of strings of symbols;
- and
- a means for transmitting the list of decompression information in conjunction with a request for at least one of the plurality of strings of symbols.
Dependencies are inferred from the claim text.