# US 11,309,911 B2 · Semi-sorting compression with encoding and decoding tables

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,309,911 B2
- Document ID: US11309911B2
- Status: Granted
- Kind: B2
- Application number: 16/542,872
- Filed: 2019-08-16
- Published: 2021-02-18
- Granted: 2022-04-19
- Earliest claimed: 2019-08-16
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: Alexander D. Breslow; Nuwan Jayasena; John Kalamatianos
- Web page: https://patentgrep.com/patent/US11309911B2

## CPC

- G06F 7/74: Selecting or encoding within a word the position of one or more bits having a specified value, e.g. most or least significant one or zero detection, priority encoders {(with shifting G06F5/01)}
- H03M 7/4037: {Prefix coding}
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0661: {Format or protocol conversion arrangements}
- G06F 3/0673: {Single storage device}
- G06F 7/08: Sorting, i.e. grouping record carriers in numerical or other ordered sequence according to the classification of at least some of the information they carry (by merging two or more sets of carriers in ordered sequence G06F7/16)
- H03M 7/4056: {Coding table selection}
- H03M 7/4062: {Coding table adaptation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A data processing platform, method, and program product perform compression and decompression of a set of data items. Suffix data and a prefix are selected for each respective data item in the set of data items based on data content of the respective data item. The set of data items is sorted based on the prefixes. The prefixes are encoded by querying multiple encoding tables to create a code word containing compressed information representing values of all prefixes for the set of data items. The code word and suffix data for each of the data items are stored in memory. The code word is decompressed to recover the prefixes. The recovered prefixes are paired with their respective suffix data.

## Claims

### Claim 1

A data processing platform comprising:
a memory;
a processor coupled to the memory and operable to:
receive a set of data items;
identify suffix data and a prefix 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 prefixes;
encode the prefixes by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all prefixes for the set of data items;
store the suffix data for each of the data items and the code word in the memory;
decompress the code word to recover the prefixes; and
pair the recovered prefixes with their respective suffix data.

### Claim 2 (depends on 1)

The data processing platform of claim 1, wherein:
the multiple encoding tables each include a number of prefix indexes; and
querying the multiple encoding tables provides the plurality of integers representing respective prefix indexes for the prefixes.

### Claim 3 (depends on 2)

The data processing platform of claim 2, wherein:
the encoding tables are provided such that, for each prefix, the respective prefix index provides a count based on a plurality of ordered collections of prefix values ordered by an ordering property; and
the counts are based on the prefix's relative position in the ordered collections.

### Claim 4 (depends on 3)

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

### Claim 5 (depends on 1)

The data processing platform of claim 1, wherein the processor is further operable to:
before creating the code word, compute the multiple encoding tables.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

The data processing platform of claim 1, wherein the multiple encoding tables are computed such that if two entries within an encoding table store the same value, the two entries are merged into a single entry.

### Claim 8 (depends on 1)

The data processing platform of claim 1, wherein the multiple encoding tables include a number k of encoding tables to l0 to lk−1, the encoding tables partially encoding respective ones of k prefixes.

### Claim 9 (depends on 8)

The data processing platform of claim 8, 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 pi is the value of the ith prefix in the order provided by the prefix sorting.

### Claim 10 (depends on 9)

The data processing platform of claim 9, wherein multiple encoding tables contain prefix values and indexes that are not arranged in order of the prefix values.

### Claim 11 (depends on 9)

The data processing platform of claim 9, wherein decompressing the code word σ comprises performing a number of iterations including:
for a first iteration, initializing i to be k−1 and a search value σ′ to be equal to the code word σ;
searching encoding table li, for a largest value that is less than or equal to the search value σ′;
setting the recovered prefix pi equal to a table index of the largest value found in the search;
for subsequent iterations, decrementing i and setting the search value σ′ equal to the prior search value σ′ minus the largest value found in the prior search iteration;
searching encoding table li, for the largest value that is less than or equal to the search value σ′; and
setting the recovered prefix pi equal to a table index of the largest value found in the search.

### Claim 12 (depends on 1)

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

### Claim 13

A method of compressing and storing data comprising:
receiving a set of data items;
identifying suffix data and a prefix 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 prefixes;
encoding the prefixes by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all prefixes for the set of data items;
storing the suffix data for each of the data items and the code word;
decompressing the code word to recover the prefixes; and
pairing the recovered prefixes with their respective suffix data.

### Claim 14 (depends on 13)

The method of claim 13, wherein:
the multiple encoding tables each include a number of prefix positions, and
wherein querying the multiple encoding tables provides the plurality of integers representing respective prefix positions for the prefixes.

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 13)

The method of claim 13, further comprising, before creating the code word, computing the multiple encoding tables.

### Claim 18 (depends on 13)

The method of claim 13, further comprising at least partially computing the multiple encoding tables in response to a requirement to decompress the code word.

### Claim 19 (depends on 13)

The method of claim 13, wherein the multiple encoding tables are computed such that if two entries within an encoding table store the same value, the two entries are merged into a single entry.

### Claim 20 (depends on 13)

The method of claim 13, wherein the multiple encoding tables include a number k of encoding tables to l0to lk−1, the encoding tables partially encoding respective ones of k prefixes.

### Claim 21 (depends on 20)

The method of claim 20, 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 σ is the code word and pi is the value of the ith prefix in the order provided by the prefix sorting.

### Claim 22 (depends on 21)

The method of claim 21, wherein multiple encoding tables contain prefix values and indexes that are not arranged in order of the prefix values.

### Claim 23 (depends on 21)

The method of claim 21, wherein decompressing the code word a comprises performing a number of iterations including:
for a first iteration, initializing i to be k−1 and a search value σ′ to be equal to the code word σ;
searching encoding table li for a largest value that is less than or equal to the search value σ′;
setting the recovered prefix pi equal to a table index of the largest value found in the search;
for subsequent iterations, decrementing i and setting the search value σ′ equal to the prior search value σ′ minus the largest value found in the prior search iteration;
searching encoding table li for the largest value that is less than or equal to the search value σ′; and
setting the recovered prefix pi equal to a table index of the largest value found in the search.

### Claim 24 (depends on 13)

The method of claim 13, wherein sorting the data items based on the prefixes comprises sort the data items using only the prefixes.

### Claim 25

A tangible nontransitory computer readable medium holding a program product executable by at least one processor to:
receive a set of data items;
identify suffix data and a prefix 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 prefixes;
encode the prefixes by querying multiple encoding tables and summing a plurality of integers therefrom to create a code word containing compressed information representing values of all prefixes for the set of data items;
store the suffix data for each of the data items and the code word in memory;
decompress the code word to recover the prefixes; and
pair the recovered prefixes with their respective suffix data.

### Claim 26 (depends on 25)

The tangible nontransitory computer readable medium of claim 25, wherein:
the multiple encoding tables each include a number of prefix indexes, and querying the multiple encoding tables provides the plurality of integers representing respective prefix indexes for the prefixes.

### Claim 27 (depends on 26)

The tangible nontransitory computer readable medium of claim 26, wherein the encoding tables are provided such that, for each prefix, the respective prefix index provides a count based on a plurality of ordered collections of prefix values ordered by an ordering property, wherein the counts are based on the prefix's relative position in the ordered collections.

### Claim 28 (depends on 27)

The tangible nontransitory computer readable medium of claim 27, wherein the count for each respective prefix index indicates a number of ordered collections of prefix values where each ordered collection's size is the output of a function applied to the prefix values' relative position in the ordered collections, and all prefix values in the ordered collections are less than the value of the respective prefix as computed by the ordering property.

### Claim 29 (depends on 25)

The tangible nontransitory computer readable medium of claim 25, wherein the program product is further executable to:
before creating the code word, compute the multiple encoding tables.

### Claim 30 (depends on 25)

The tangible nontransitory computer readable medium of claim 25, wherein the multiple encoding tables include a number k of encoding tables to l0to lk−1, the encoding tables partially encoding respective ones of k prefixes.

### Claim 31 (depends on 30)

The tangible nontransitory computer readable medium of claim 30, wherein the program product is further executable 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 pi is the value of the ith prefix in the order provided by the prefix sorting.

### Claim 32 (depends on 31)

The tangible nontransitory computer readable medium of claim 31, wherein multiple encoding tables contain prefix values and indexes that are not arranged in order of the prefix values.

### Claim 33 (depends on 31)

The tangible nontransitory computer readable medium of claim 31, wherein decompressing the code word 6 comprises performing a number of iterations using the plurality of encoding tables in an order produced by the sorting, from table lk−1 to table l0, the iterations including:
for a first iteration, initializing i to be k−1 and a search value σ′ to be equal to the code word σ;
searching encoding table li for a largest value that is less than or equal to the search value σ′;
setting the recovered prefix pi equal to a table index of the largest value found in the search;
for subsequent iterations, decrementing i and setting the search value σ′ equal to the prior search value σ′ minus the largest value found in the prior search iteration;
searching encoding table li for the largest value that is less than or equal to the search value σ′; and
setting the recovered prefix pi equal to a table index of the largest value found in the search.

### Claim 34 (depends on 31)

The tangible nontransitory computer readable medium of claim 31, wherein providing a plurality of encoding tables to l0 to lk−1 includes, if two entries within an encoding table store the same value, merging the two entries into a single entry.

### Claim 35 (depends on 25)

The tangible nontransitory computer readable medium of claim 25, wherein sorting the data items based on the prefixes comprises sort the data items using only the prefixes.