Method and apparatus for compressing a data set
AssigneeMicrosoft Corporation
InventorArtem Livshits
Life of this patent
Estimating the term…
Abstract
A configuration management system that uses a data compression method to compress entries in a data set. An entry is selected as a prefix value and prefix compression of the data set is performed. The entry to serve as the prefix value is quickly selected using an iterative approach. In each iteration, subgroups of entries are formed from groups formed in prior iterations based on the values of characters at successive positions in the entries. The approach is readily implemented using data structures represented as lists.
Claims20
A method of compressing a data set comprising a plurality of entries, each of the plurality of entries having a string, the string formed from characters, each character having a value and an ordered position in the string, with one character being the beginning of the string, such that each string has one or more prefix portions, each prefix portion containing a portion of the string having one or more characters at consecutively ordered positions in the string including the character at the beginning of the string, the method comprising:
- a) determining a plurality of indicators, for each of the plurality of entries, representing the number of entries in the data set with a string having the same prefix portion as the sting of the entry, with each of the plurality of indicators for each of the plurality of entries determined for a prefix portion of the entry having a different number of characters;
- b) producing a plurality of aggregated indicators, each aggregated indicator representing a combination of the plurality of indicators determined for one of the plurality of entries;
- c) selecting an entry of the plurality of entries based on the aggregated indicators;
- and
- d) compressing the data set using the selected entry.
A method of compressing a data set comprising a plurality of entries, each of the plurality of entries having a string of characters associated therewith, with each character having a value and a position in the string, the method comprising:
- a) forming a list of a plurality of list elements, with each list element having the string of one of the plurality of entries associated therewith;
- b) forming a first plurality of sublists from the plurality of list elements with all the list elements in each sublist of the first plurality of sublists having a string associated therewith having a character with the same value in a first position in the string;
- c) forming, for each sublist in at least a portion of the first plurality of sublists, a second plurality of sublists from the list elements in the sublist in the first plurality of sublists, with all the list elements in each sublist of the second plurality of sublists having a string associated therewith having a character with the same value in a second position in the string;
- and
- d) for each of the plurality of entries, computing an indicator based at least in part on the number of list elements in the sublist of the first plurality of sublists and the number of list elements in the sublist of the second plurality of sublists in which the entry is associated.
A configuration management system comprising:
- a) a database storing a plurality of artifacts;
- b) an index comprising a plurality of entries, each of the plurality of entries having a string of characters associated therewith, with each character having a value and a position in the string, and each entry identifying an artifact in the database;
- and
- c) a computer-readable medium storing computer executable instructions for performing the method comprising:
- i) forming subgroups containing entries from the plurality of entries in the index based on the value of a character at a first position of the string associated with each entry;
- ii) forming further subgroups containing entries from the entries in the subgroups based on the value of a character at a second position in the string associated with each entry;
- iii) for each of a plurality of entries, computing an indicator based on the number of entries in each subgroup containing the entry;
- iv) selecting an entry from the plurality of entries based on the indicators;
- and
- v) compressing the index using the selected entry.
Dependencies are inferred from the claim text.