# US 8,279,096 B2 · Parallel compression for dictionary-based sequential coders

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

- Number: US 8,279,096 B2
- Document ID: US8279096B2
- Status: Granted
- Kind: B2
- Application number: 12/782,892
- Filed: 2010-05-19
- Published: 2011-11-24
- Granted: 2012-10-02
- Earliest claimed: 2010-05-19
- Assignees: Red Hat, Inc.
- Inventors: Jind{hacek over (r)}ich Nový
- Web page: https://patentgrep.com/patent/US8279096B2

## CPC

- H03M 7/30: Compression (speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N); Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- 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

Dictionary-based sequential compression is performed in parallel on input data using multiple cores of a computer system. The compression can be performed by first determining a dictionary size for data compression, followed by determining a block size for partitioning the input data. The block size is greater than the dictionary size. The multiple cores of the computer system then execute multiple threads in parallel, with each thread compressing one block of the input data according to a dictionary-based sequential compression scheme.

## Claims

### Claim 1

A method, implemented by a computer system programmed to perform the following, comprising:
determining, by the computer system, a dictionary size for data compression based on a received compression level;
determining, by the computer system, a block size greater than the dictionary size for partitioning input data; and
executing multiple threads in parallel using multiple cores of the computer system, each thread compressing one block of the input data according to a dictionary-based sequential compression scheme.

### Claim 2 (depends on 1)

The method of claim 1, wherein the dictionary-based sequential compression scheme is based on a Lempel-Ziv compression algorithm or a variant thereof.

### Claim 3 (depends on 1)

The method of claim 1, wherein the block size is an integer multiple of the dictionary size.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
receiving an input from a user that indicates the compression level.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
providing a plurality of compression levels for user selection, each compression level associated with a penalty of increased compressed data size.

### Claim 6

A system comprising:
data storage to store input data; and
a computer system coupled to the data storage, the computer system comprising:
a compression manager to determine a dictionary size based on a received compression level and to determine a block size that is greater than the dictionary size for partitioning input data; and
a plurality of cores to execute multiple threads in parallel, each thread to compress one block of the input data according to a dictionary-based sequential compression scheme to generate the compressed data.

### Claim 7 (depends on 6)

The system of claim 6, wherein the dictionary-based sequential compression scheme is based on a Lempel-Ziv compression algorithm or a variant thereof.

### Claim 8 (depends on 6)

The system of claim 6, wherein the block size is an integer multiple of the dictionary size.

### Claim 9 (depends on 6)

The system of claim 6, further comprising:
a user interface to receive, from a user, the compression level, based on which the dictionary size is determined.

### Claim 10 (depends on 6)

The system of claim 6, wherein the computer system provides a plurality of compression levels for user selection, each compression level associated with a penalty of increased compressed data size.

### Claim 11

A non-transitory computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:
determining a dictionary size for data compression based on a received compression level;
determining a block size greater than the dictionary size for partitioning input data; and
executing multiple threads in parallel using multiple cores of a computer system, each thread compressing one block of the input data according to a dictionary-based sequential compression scheme.

### Claim 12 (depends on 11)

The computer readable storage medium of claim 11, wherein the dictionary-based sequential compression scheme is based on a Lempel-Ziv compression algorithm or a variant thereof.

### Claim 13 (depends on 11)

The computer readable storage medium of claim 11, wherein the block size is an integer multiple of the dictionary size.

### Claim 14 (depends on 11)

The computer readable storage medium of claim 11, wherein the method further comprises:
receiving an input from a user that indicates the compression level.

### Claim 15 (depends on 11)

The computer readable storage medium of claim 11, wherein the method further comprises:
providing a plurality of compression levels for user selection, each compression level associated with a penalty of increased compressed data size.

### Claim 16

A method, implemented by a client machine programmed to perform the following, the method comprising:
partitioning, by the client machine, compressed data into a plurality of data blocks;
determining whether to decompress the plurality of data blocks sequentially or in parallel; and
decompressing the data blocks accordingly by the client machine using a dictionary-based sequential decompression scheme.

### Claim 17 (depends on 16)

The method of claim 16, wherein determining whether to decompress the data blocks of interest sequentially or in parallel is based on the number of available cores in the client machine.

### Claim 18

A non-transitory computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:
partitioning compressed data into a plurality of data blocks;
determining whether to decompress the data blocks of interest sequentially or in parallel;
and decompressing the data blocks accordingly by the client machine using a dictionary-based sequential decompression scheme.

### Claim 19 (depends on 18)

The computer readable storage medium of claim 18, wherein determining whether to decompress the data blocks of interest sequentially or in parallel is based on the number of available cores in the client machine.
