# US 11,308,277 B2 · Memory preserving parse tree based compression with entropy coding

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

- Number: US 11,308,277 B2
- Document ID: US11308277B2
- Status: Granted
- Kind: B2
- Application number: 16/692,773
- Filed: 2019-11-22
- Published: 2020-03-19
- Granted: 2022-04-19
- Earliest claimed: 2015-12-03
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Jonathan D. Bradbury; Markus Helms; Christian Jacobi; Aditya N. Puranik; Christian Zoellin
- Web page: https://patentgrep.com/patent/US11308277B2

## CPC

- G06F 40/205: Parsing
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0626: {Reducing size or complexity of storage systems}
- G06F 3/0629: {Configuration or reconfiguration of storage systems}
- G06F 3/0638: {Organizing or formatting or addressing of data}
- G06F 3/0673: {Single storage device}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/9027: {Trees}
- H03M 7/3079: {Context modeling}
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- 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 method, computer program product, and system includes a processor obtaining data including values and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, where the value conversion dictionary includes dictionary entries that represent the values. The processor obtains a distribution of the values and estimates a likelihood for each based on the distribution. The processor generates a code word to represent each value, a size of each code word is inversely proportional to the likelihood of the word. The processor assigns a rank to each code word, the rank for each represents the likelihood of the value represented by the code word; and based on the rank associated with each code word, the processor reorders each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, the reordered value conversion dictionary comprises an architected dictionary.

## Claims

### Claim 1

A computer-implemented method, comprising:
obtaining, by a processor, data comprised of values, wherein the values are of variable size, and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, wherein the value conversion dictionary is comprised of dictionary entries that represent the values;
obtaining, by the processor, a distribution of the values and estimating a likelihood for each value based on the distribution;
generating, by the processor, a code word to represent each value, wherein a size of each code word is inversely proportional to the likelihood of the value represented by the code word;
assigning, by the processor, a rank to each code word, wherein the rank for each code word represents the likelihood of the value represented by the code word;
based on the rank associated with each code word, reordering, by the processor, each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, wherein the reordered value conversion dictionary comprises an architected dictionary; and
storing, by the processor, the architected dictionary in a memory, wherein the processor utilizes the architected dictionary to compress data subsequently obtained by the processor and to decompress code words subsequently obtained by the processor, wherein utilizing the architected dictionary to compress data subsequently obtained by the processor and decompressing code words subsequently obtained by the processor do not comprise the processor performing a memory lookup.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, further comprising:
obtaining, by the processor, the additional data; and
compressing, by the processor, the additional data utilizing the architected dictionary.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein the compressing comprises walking, by the processor, from entries in the architected dictionary to the ranks.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the dictionary entries are of a fixed size, and wherein utilizing the architected dictionary to compress the data subsequently obtained by the processor and to decompress the code words subsequently obtained by the processor comprises locating ranks relevant to the dictionary entries.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1, further comprising:
obtaining, by the processor, a given code word; and
decompressing, by the processor, the given code word utilizing the architected dictionary.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5, wherein the decompressing comprises walking, by the processor, from the ranks to the architected dictionary.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1, wherein the architected dictionary comprises references for each dictionary entry describing parent and child relationships associated with the dictionary entry.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, the reordering comprising:
associating, by the processor, each dictionary entry with a rank;
sorting, by the processor, each dictionary entry according to the rank assigned;
updating, by the processor, the references for each dictionary entry; and
discarding, by the processor, locations for each dictionary entry in the value conversion dictionary prior to the updating.

### Claim 9 (depends on 8)

The computer-implemented method of claim 8, the sorting further comprising, retaining, in a memory, the locations for each dictionary entry in the value conversion dictionary.

### Claim 10 (depends on 1)

The computer-implemented method of claim 1, wherein the parse tree based compression algorithm is a Ziv-Lempel compression algorithm.

### Claim 11 (depends on 1)

The computer-implemented method of claim 1, wherein the generating and the assigning comprise generating Canonical Huffman Code.

### Claim 12 (depends on 1)

The computer-implemented method of claim 1, wherein the values are of variable size.

### Claim 13 (depends on 1)

The computer-implemented method of claim 1, wherein the architected dictionary is stored as at least one tree structure.

### Claim 14

A computer program product comprising:
a computer readable storage medium readable by one or more processor and storing instructions for execution by the one or more processor for performing a method comprising:
obtaining, by a processor, data comprised of values, wherein the values are of variable size, and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, wherein the value conversion dictionary is comprised of dictionary entries that represent the values;
obtaining, by the processor, a distribution of the values and estimating a likelihood for each value based on the distribution;
generating, by the processor, a code word to represent each value, wherein a size of each code word is inversely proportional to the likelihood of the value represented by the code word;
assigning, by the processor, a rank to each code word, wherein the rank for each code word represents the likelihood of the value represented by the code word;
based on the rank associated with each code word, reordering, by the processor, each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, wherein the reordered value conversion dictionary comprises an architected dictionary; and
storing, by the processor, the architected dictionary in a memory, wherein the processor utilizes the architected dictionary to compress data subsequently obtained by the processor and to decompress code words subsequently obtained by the processor, wherein utilizing the architected dictionary to compress data subsequently obtained by the processor and decompressing code words subsequently obtained by the processor do not comprise the processor performing a memory lookup.

### Claim 15 (depends on 14)

The computer program product of claim 14, further comprising:
obtaining, by the processor, the additional data; and
compressing, by the processor, the additional data utilizing the architected dictionary, wherein the compressing comprises walking, by the processor, from dictionary entries to ranks.

### Claim 16 (depends on 14)

The computer program product of claim 14, further comprising:
obtaining, by the processor, a given code word; and
decompressing, by the processor, the given code word utilizing the architected dictionary, wherein the decompressing comprises walking, by the processor, from ranks to dictionary entries.

### Claim 17 (depends on 14)

The computer program product of claim 14, wherein the value conversion dictionary comprises references for each dictionary entry describing parent and child relationships associated with the dictionary entry.

### Claim 18 (depends on 17)

The computer program product of claim 17, the reordering comprising:
associating, by the processor, each dictionary entry with a rank;
sorting, by the processor, each dictionary entry according to the rank assigned;
updating, by the processor, the references for each dictionary entry; and
discarding, by the processor, locations for each dictionary entry in the value conversion dictionary prior to the updating.

### Claim 19

A system comprising:
a memory;
one or more processor in communication with the memory; and
program instructions executable by the one or more processor via the memory to perform a method, the method comprising:
obtaining, by a processor, data comprised of values, wherein the values are of variable size, and generating a value conversion dictionary by applying a parse tree based compression algorithm to the data, wherein the value conversion dictionary is comprised of dictionary entries that represent the values;
obtaining, by the processor, a distribution of the values and estimating a likelihood for each value based on the distribution;
generating, by the processor, a code word to represent each value, wherein a size of each code word is inversely proportional to the likelihood of the value represented by the code word;
assigning, by the processor, a rank to each code word, wherein the rank for each code word represents the likelihood of the value represented by the code word;
based on the rank associated with each code word, reordering, by the processor, each dictionary entry in the value conversion dictionary to associate each dictionary entry with an equivalent rank, wherein the reordered value conversion dictionary comprises an architected dictionary; and
storing, by the processor, the architected dictionary in a memory, wherein the processor utilizes the architected dictionary to compress data subsequently obtained by the processor and to decompress code words subsequently obtained by the processor, wherein utilizing the architected dictionary to compress data subsequently obtained by the processor and decompressing code words subsequently obtained by the processor do not comprise the processor performing a memory lookup.

### Claim 20 (depends on 19)

The system of claim 19, wherein the value conversion dictionary comprises references for each dictionary entry describing parent and child relationships associated with the dictionary entry.