Semi-sorting compression with encoding and decoding tables

1. A data processing platform comprising:

a memory;

a processor coupled to the memory and operable to:

receive a set of data items;

identify a group of bits and remaining data for each respective data item in the set of data items based on data content of the respective data item;

sort the set of data items based on the groups of bits;

encode the groups of bits by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all groups of bits for the set of data items;

store the remaining data for each of the data items and the code word in the memory;

decompress the code word to recover the groups of bits; and

pair the recovered groups of bits with their respective remaining data.

2. The data processing platform of claim 1 , wherein:

the multiple encoding tables each include a number of indexes; and

querying the multiple encoding tables provides the plurality of integers representing respective indexes for the groups of bits.

3. The data processing platform of claim 2 , wherein:

the multiple encoding tables are provided such that, for each group of bits, the respective index provides a count based on a plurality of ordered collections of values for the groups of bits ordered by an ordering property; and

the counts are based on the respective value's relative position in the ordered collections.

4. The data processing platform of claim 3 , wherein the count for each respective index indicates a number of ordered collections of values of the groups of bits where each ordered collection's size is an output of a function applied to the values relative position in the ordered collections, and all values in the ordered collections are less than the value of the respective group of bits as computed by the ordering property.

5. The data processing platform of claim 1 , wherein the processor is further operable to at least partially compute the multiple encoding tables in response to a requirement to decompress the code word.

6. The data processing platform of claim 1 , wherein the multiple encoding tables include a number k of encoding tables l 0 to l k-1 , the encoding tables partially encoding respective ones of k groups of bits.

7. The data processing platform of claim 6 , wherein the processor is further operable to:

when creating the code word, access the multiple encoding tables to obtain respective partial values for the expression:

σ

=

∑

i

=

0

k

-

1

(

p

i

+

i

i

+

1

)

where σ is the code word and p i is the value of the ith group of bits in the order provided by the sorting.

8. The data processing platform of claim 7 , wherein multiple encoding tables contain group of bits values and indexes that are not arranged in order of the group of bits values.

9. The data processing platform of claim 7 , wherein decompressing the code word a comprises performing a number of iterations including:

for a first iteration, initializing a search value to be equal to the code word, setting a recovered group of bits p i equal to a table index to a largest value in an initial table less than or equal to the search value; and

for subsequent iterations:

updating the search value equal to the prior search value minus the largest value found in the prior iteration; and

setting the recovered group of bits p i equal to a table index of a largest value in a subsequent table less than or equal to the updated search value.

10. The data processing platform of claim 1 , wherein the processor sorts the data items using only the groups of bits.

11. A method of compressing and storing data comprising:

receiving a set of data items;

identifying a group of bits and remaining data for each respective data item in the set of data items based on data content of the respective data item;

sorting the set of data items based on the groups of bits;

encoding the groups of bits by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all groups of bits for the set of data items;

storing the remaining data for each of the data items and the code word;

decompressing the code word to recover the groups of bits; and

pairing the recovered groups of bits with their respective remaining data.

12. The method of claim 11 , wherein:

the multiple encoding tables each include a number of positions for the groups of bits, and

wherein querying the multiple encoding tables provides the plurality of integers representing respective positions for the groups of bits.

13. The method of claim 12 , wherein the multiple encoding tables are provided such that, for each group of bits, the respective index provides a count based on a plurality of ordered collections of values for the groups of bits ordered by an ordering property, wherein the counts are based on the respective values' relative position in the ordered collections.

14. The method of claim 13 , wherein the count for each respective index indicates a number of ordered collections of values for the groups of bits where each ordered collection's size is an output of a function applied to the values' relative position in the ordered collections, and all values in the ordered collections are less than the value of the respective group of bits as computed by the ordering property.

15. The method of claim 11 , wherein the multiple encoding tables include a number k of encoding tables l 0 to l k-i , the encoding tables partially encoding respective ones of k groups of bits, the method further comprising:

when creating the code word, access the multiple encoding tables to obtain respective partial values for the expression:

σ

=

∑

i

=

0

k

-

1

(

p

i

+

i

i

+

1

)

where a is the code word and p i is the value of the ith group of bits in the order provided by the group of bits sorting.

16. The method of claim 15 , wherein decompressing the code word a comprises performing a number of iterations including:

for a first iteration, initializing a search value to be equal to the code word, setting a recovered group of bits p i equal to a table index to a largest value in an initial one of the encoding tables less than or equal to the search value; and

for subsequent iterations:

updating the search value equal to the prior search value minus the largest value found in the prior iteration; and

setting the recovered group of bits p i equal to a table index of a largest value in a subsequent one of the encoding table less than or equal to the updated search value.

17. The method of claim 11 , wherein sorting the data items based on the groups of bits comprises sort the data items using only the groups of bits.

18. A data processing platform comprising:

a memory; and

a processor coupled to the memory and operable to receive a compressed set of data items including a compressed code word and a remaining data for each data item, and decompress the set of data items using a number k of encoding tables, the encoding tables partially encoding respective ones of k groups of bits, wherein the decompression includes performing a number of iterations including:

for a first iteration, initializing a search value to be equal to the code word, setting a recovered group of bits p i equal to a table index to a largest value in an initial one of the encoding tables less than or equal to the search value; and

for subsequent iterations:

updating the search value equal to the prior search value minus the largest value found in the prior iteration; and

setting the recovered group of bits p i equal to a table index of a largest value in a subsequent one of the encoding table less than or equal to the updated search value.

19. The data processing platform of claim 18 , wherein:

the process further operable to compress the data items by:

identifying the group of bits and remaining data for each respective data item in the set of data items based on data content of the respective data item;

sorting the set of data items based on the groups of bits;

encoding the groups of bits by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all groups of bits for the set of data items; and

storing the remaining data for each of the data items and the code word in the memory.

20. The data processing platform of claim 19 , wherein:

the multiple encoding tables each include a number of indexes; and

querying the multiple encoding tables provides the plurality of integers representing respective indexes for the groups of bits.