Method and system for data compression
AssigneeSap SE
InventorAlexander Froemmgen
Life of this patent
Estimating the term…
Abstract
In one aspect, methods and systems for variable-block length encoding of data, such as an inverted index for a file are disclosed. These methods and systems provide for relatively fast encoding and decoding, while also providing for compact storage. Other aspects include a nearly 1:1 inverted index comprising a position vector and a data store, wherein values that have a unique location mapping are represented directly in the position vector, while for 1:n values (n>1), the position vector can include a pointer, and potentially some portion of information that would typically be stored in the data area, in order to fully use fixed width portions of the position vector (where a maximum pointer size is smaller than a maximum location identifier size).
Claims20
A method of data compression, comprising:
- accessing, in a computer system, a raw data set comprising a plurality of data elements;
- determining, in the computer system, a set of block sizes to be used in forming an encoded data set providing a compressed representation of the plurality of data elements in the raw data set, wherein the set of block sizes comprises differing block sizes;
- determining, in the computer system, a respective grouping of one or more blocks in which to store each data element of the raw data set, each block in the grouping being of a block size selected from the set of block sizes;
- and
- storing, in a non-transitory machine readable medium, the groupings in a sequence, in association with respective unary size codes indicative of a size of each grouping in the sequence.
A non-transitory machine readable medium storing instructions that when executed by a computer processor configure the computer processor for:
- accessing a raw data set comprising a plurality of data elements;
- determining a set of block sizes to be used in forming an encoded data set providing a compressed representation of the plurality of data elements in the raw data set, wherein the set of block sizes comprises differing block sizes;
- determining a respective grouping of one or more blocks in which to store each data element of the raw data set, each block in the grouping being of a block size selected from the set of block sizes;
- and
- storing, in a non-transitory machine readable medium, the groupings in a sequence, in association with respective unary size codes indicative of a size of each grouping in the sequence.
A system, comprising:
- a processor;
- and
- a non-transitory machine readable medium coupled with the processor, and storing machine readable data that when executed by the processor cause the processor to be configured to:
- access a raw data set comprising a plurality of data elements,
- determine a set of block sizes to be used in forming an encoded data set providing a compressed representation of the plurality of data elements in the raw data set, wherein the set of block sizes comprises differing block sizes,
- determine a respective grouping of one or more blocks in which to store each data element of the raw data set, each block in the grouping being of a block size selected from the set of block sizes, and
- store, in a non-transitory machine readable medium, the groupings in a sequence, in association with respective unary size codes indicative of a size of each grouping in the sequence.
Dependencies are inferred from the claim text.