Back to results
US 7,126,500 B2Granted
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.
Claims25
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.
5 more elements
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.
6 more elements
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;
- wherein building the list of decompression information comprises evaluating the plurality of strings of symbols to identify a candidate replacement sequence of symbols common to the plurality of strings of symbols;
- generating sequences of symbols from the plurality of strings of symbols;
- selecting an initial candidate replacement sequence of symbols from the sequences of symbols;
- determining a target cost savings and a minimum frequency of occurrence associated with the initial candidate replacement sequence of symbols;
- and analyzing the other sequences of symbols in the sequence of symbols that have a frequency of occurrence that is greater than the minimum frequency of occurrence;
- and
- transmitting the list of decompression information in conjunction with a request for at least one of the plurality of strings of symbols.
5 more elements
An apparatus for transmitting a compressed data file, comprising:
- a means for building a list of decompression information, wherein the means for building the list of decompression information comprises:
- a means for generating sequences of symbols from a string of symbols;
- a means selecting a current candidate replacement sequence from the sequences of symbols;
- a means 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
- a means attempting to identify an alternative candidate replacement sequence when other sequences of symbols in the ordered sequence of symbols have an associated frequency of occurrence that is greater than the minimum frequency of occurrence;
- 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.
5 more elements
Dependencies are inferred from the claim text.