# US 2019/0356330 A1 · Data compression by local entropy encoding

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

- Number: US 2019/0356330 A1
- Document ID: US20190356330A1
- Status: Published application
- Kind: A1
- Application number: 15/985,340
- Filed: 2018-05-21
- Published: 2019-11-21
- Earliest claimed: 2018-05-21
- Assignees: Google Inc.
- Applicants: Google LLC
- Inventors: David Charles Minnen; Michele Covell; Saurabh Singh; Sung Jin Hwang; George Dan Toderici
- Web page: https://patentgrep.com/patent/US20190356330A1

## CPC

- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/285: {Clustering or classification}
- G06N 3/0455: Auto-encoder networks; Encoder-decoder networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/08: Learning methods
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- H04N 19/13: Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
- H04N 19/192: the adaptation method, adaptation tool or adaptation type being iterative or recursive
- H04N 19/91: Entropy coding, e.g. variable length coding [VLC] or arithmetic coding
- G06N 3/044: Recurrent networks, e.g. Hopfield networks
- G06N 3/047: Probabilistic or stochastic networks
- G06N 3/0895: Weakly supervised learning, e.g. semi-supervised or self-supervised learning
- 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)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for compressing and decompressing data. In one aspect, an encoder neural network processes data to generate an output including a representation of the data as an ordered collection of code symbols. The ordered collection of code symbols is entropy encoded using one or more code symbol probability distributions. A compressed representation of the data is determined based on the entropy encoded representation of the collection of code symbols and data indicating the code symbol probability distributions used to entropy encode the collection of code symbols. In another aspect, a compressed representation of the data is decoded to determine the collection of code symbols representing the data. A reconstruction of the data is determined by processing the collection of code symbols by a decoder neural network.

## Claims

### Claim 1

A system for compressing data, the system comprising:
an encoder neural network configured to perform operations comprising:
receiving data to be compressed;
processing the data in accordance with current values of a set of encoder neural network parameters to generate an output including a representation of the data as an ordered collection of code symbols;
a compression subsystem configured to perform operations comprising:
receiving the output of the encoder neural network, including the representation of the data as an ordered collection of code symbols;
identifying a partition of the collection of code symbols into one or more code symbol subsets;
for each code symbol subset:
identifying, from a dictionary of multiple code symbol probability distributions, and based on the code symbol subset, a code symbol probability distribution for the code symbol subset;
generating an entropy encoded representation of the code symbol subset by entropy encoding the code symbol subset using the code symbol probability distribution identified for the code symbol subset;
determining a compressed representation of the code symbol subset, the compressed representation comprising: (i) the entropy encoded representation of the code symbol subset, and (ii) data indicating a code symbol probability distribution used to entropy encode the code symbol subset;
determining a compressed representation of the data based on the compressed representations of the code symbol subsets.

### Claim 2 (depends on 1)

The system of claim 1, wherein the data to be compressed includes an image.

### Claim 3 (depends on 1)

The system of claim 1, wherein the encoder neural network is a convolutional neural network.

### Claim 4 (depends on 1)

The system of claim 1, further comprising a learning subsystem configured to perform operations comprising:
processing data in a set of training data, by the encoder neural network and in accordance with the current values of the set of encoder neural network parameters, to generate outputs including representations of the data in the set of training data as ordered collections of code symbols;
identifying, for each ordered collection of code symbols, a partition of the ordered collection of code symbols into one or more code symbol subsets; and
determining the dictionary of multiple code symbol probability distributions based on distributions of code symbols in the code symbol subsets of the ordered collections of code symbols.

### Claim 5 (depends on 4)

The system of claim 4, wherein determining the dictionary of code symbol probability distributions comprises:
determining, for each of the code symbol subsets of the ordered collections of code symbols, a respective code symbol probability distribution reflecting a frequency of occurrence of code symbols in the code symbol subset;
clustering the determined code symbol probability distributions; and
determining the dictionary of code symbol probability distributions based on cluster centers of the clustered code symbol probability distributions.

### Claim 6 (depends on 5)

The system of claim 5, wherein clustering the code symbol probability distributions comprises determining a distance between code symbol probability distributions based on a divergence measure.

### Claim 7 (depends on 1)

The system of claim 1, wherein identifying a code symbol probability distribution for the code symbol subset comprises:
determining, for each code symbol probability distribution in the dictionary, a corresponding length of an entropy encoded representation of the code symbol subset based on the code symbol probability distribution; and
identifying the code symbol probability distribution for the code symbol subset to be a code symbol probability distribution from the dictionary with a minimal corresponding length of entropy encoded representation.

### Claim 8 (depends on 7)

The system of claim 7, wherein determining the length of an entropy encoded representation of the code symbol subset based on the code symbol probability distribution comprises determining a sum, over each code symbol in the code symbol subset, of a logarithm of a probability of the code symbol according to the code symbol probability distribution.

### Claim 9 (depends on 1)

The system of claim 1, wherein:
the operations performed by the compression subsystem further comprise:
determining one or more code symbol subsets to be candidate code symbol subsets;
determining a custom code symbol probability distribution based on the candidate code symbol subsets;
determining a savings value based on a reduction in a length of entropy encoded representations of the candidate code symbol subsets achieved by entropy encoding the candidate code symbol subsets using the custom code symbol probability distribution instead of code symbol probability distributions from the dictionary;
determining a cost value based on a length of data required to represent the custom code symbol probability distribution; and
in response to determining that the savings value is greater than the cost value, generating the entropy encoded representations of the code symbols of the candidate code symbol subsets by entropy encoding the candidate code symbol subsets using the custom code symbol probability distribution.

### Claim 10 (depends on 1)

The system of claim 1, wherein identifying a partition of the collection of code symbols into one or more code symbol subsets comprises identifying a partition of the collection of code symbols into multiple different proper subsets.

### Claim 11

A system for decompressing data, the system comprising:
a decompression subsystem configured to perform operations comprising:
receiving a compressed representation of data comprising a compressed representation of each of one or more code symbol subsets of an ordered collection of code symbols representing the data, wherein the compressed representation of a code symbol subset comprises: (i) an entropy encoded representation of the code symbol subset, and (ii) data indicating a code symbol probability distribution used to entropy encode the code symbol subset;
determining each code symbol subset by decoding the entropy encoded representation of the code symbol subset based on the code symbol probability distribution used to entropy encode the code symbol subset;
determining a representation of the data as an ordered collection of code symbols based on the code symbol subsets; and
a decoder neural network configured to perform operations comprising:
receiving the representation of the data as an ordered collection of code symbols determined by the decompression subsystem;
processing the ordered collection of code symbols in accordance with current values of a set of decoder neural network parameters to generate an output defining a reconstruction of the data.

### Claim 12 (depends on 11)

The system of claim 11, wherein the data indicating a code symbol probability distribution used to entropy encode the code symbol subset comprises data indicating a code symbol probability distribution from a dictionary of code symbol probability distributions.

### Claim 13 (depends on 11)

The system of claim 11, wherein the data indicating a code symbol probability distribution used to entropy encode the code symbol subset comprises data defining a respective numerical probability value for each code symbol in a set of possible code symbols.

### Claim 14

A computer-implemented method for compressing data, the method comprising:
receiving data to be compressed;
processing the data by an encoder neural network and in accordance with current values of a set of encoder neural network parameters to generate an output including a representation of the data as an ordered collection of code symbols;
identifying a partition of the collection of code symbols into one or more code symbol subsets;
for each code symbol subset:
identifying, from a dictionary of multiple code symbol probability distributions, and based on the code symbol subset, a code symbol probability distribution for the code symbol subset;
generating an entropy encoded representation of the code symbol subset by entropy encoding the code symbol subset using the code symbol probability distribution identified for the code symbol subset;
determining a compressed representation of the code symbol subset, the compressed representation comprising: (i) the entropy encoded representation of the code symbol subset, and (ii) data indicating a code symbol probability distribution used to entropy encode the code symbol subset;
determining a compressed representation of the data based on the compressed representations of the code symbol subsets.

### Claim 15 (depends on 14)

The method of claim 14, wherein the data to be compressed includes an image.

### Claim 16 (depends on 14)

The method of claim 14, wherein the encoder neural network is a convolutional neural network.

### Claim 17 (depends on 14)

The method of claim 14, wherein identifying a code symbol probability distribution for the code symbol subset comprises:
determining, for each code symbol probability distribution in the dictionary, a corresponding length of an entropy encoded representation of the code symbol subset based on the code symbol probability distribution; and
identifying the code symbol probability distribution for the code symbol subset to be a code symbol probability distribution from the dictionary with a minimal corresponding length of entropy encoded representation.

### Claim 18

A non-transitory computer readable storage medium storing instructions executable by a data processing apparatus and that upon such execution causes the data processing apparatus to perform operations comprising:
receiving data to be compressed;
processing the data by an encoder neural network and in accordance with current values of a set of encoder neural network parameters to generate an output including a representation of the data as an ordered collection of code symbols;
identifying a partition of the collection of code symbols into one or more code symbol subsets;
for each code symbol subset:
identifying, from a dictionary of multiple code symbol probability distributions, and based on the code symbol subset, a code symbol probability distribution for the code symbol subset;
generating an entropy encoded representation of the code symbol subset by entropy encoding the code symbol subset using the code symbol probability distribution identified for the code symbol subset;
determining a compressed representation of the code symbol subset, the compressed representation comprising: (i) the entropy encoded representation of the code symbol subset, and (ii) data indicating a code symbol probability distribution used to entropy encode the code symbol subset;
determining a compressed representation of the data based on the compressed representations of the code symbol subsets.

### Claim 19 (depends on 18)

The non-transitory medium of claim 18, wherein the data to be compressed includes an image.

### Claim 20 (depends on 18)

The non-transitory medium of claim 18, wherein the encoder neural network is a convolutional neural network.
