# US 2019/0377804 A1 · Data compression algorithm

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

- Number: US 2019/0377804 A1
- Document ID: US20190377804A1
- Status: Published application
- Kind: A1
- Application number: 16/160,699
- Filed: 2018-10-15
- Published: 2019-12-12
- Earliest claimed: 2018-06-06
- Inventors: Yingquan Wu
- Web page: https://patentgrep.com/patent/US20190377804A1

## CPC

- G06F 16/1744: {using compression, e.g. sparse files}
- G06F 16/90344: {by using string matching techniques}
- G06F 16/90335: {Query processing}
- H03M 7/3086: {employing a sliding window, e.g. LZ77}
- H03M 7/3088: {employing the use of a dictionary, e.g. LZ78}
- H03M 7/6058: {Saving memory space in the encoder or decoder}
- 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 for augmenting a dictionary of a data compression scheme. For each input string, the result of a sliding window search is compared to the result of a dictionary search. The dictionary is augmented with the sliding window search result if the sliding window search result is longer than the dictionary search result. An embodiment of the disclosure implements multiple sliding windows, each sliding window having an associated size, the size of sliding window dependent on a corresponding match length. For one embodiment, each sliding window has a corresponding hash function based upon the match length.

## Claims

### Claim 1

A method for creating entries for a dynamic dictionary of a dictionary-based data compression system, the method comprising:
receiving input data comprising an input data string;
performing a string match search over a sliding window of previous data to determine a longest string of input data matching data contained in the sliding window:
performing a dictionary search over the dynamic dictionary to determine a longest string of input data contained as a reference in the dynamic dictionary:
comparing the length of the longest string of input data matching data contained in the sliding window with the length of the longest string of input data contained as a reference in the dynamic dictionary; and
creating an entry referencing the input data string in the dynamic dictionary only if the longest string of input data matching data contained in the sliding window is greater than the longest string of input data contained as a reference in the dynamic dictionary.

### Claim 2 (depends on 1)

The method of claim 1 wherein the sliding window is one of a plurality of sliding windows, each of the plurality of sliding windows having a corresponding match length.

### Claim 3 (depends on 1)

The method of claim 1 wherein a smallest data string match length is two bytes.

### Claim 4 (depends on 1)

The method of claim 1 wherein each of the corresponding match length has hash function based upon the match length.

### Claim 5

A sliding window data compressing compression method comprising:
determining a plurality of data string match lengths
implementing a corresponding sliding window for each of the data string match lengths, a size of each of the corresponding sliding windows based upon the corresponding match length.

### Claim 6 (depends on 5)

The sliding window data compressing compression method of claim 5 wherein a smallest data string match length is two bytes.

### Claim 7 (depends on 6)

The sliding window data compressing compression method of claim 6 wherein each of the sliding windows has a corresponding hash chain.

### Claim 8 (depends on 5)

The sliding window data compressing compression method of claim 5 wherein a search of each of the plurality of sliding windows is conducted concurrently.

### Claim 9 (depends on 5)

The sliding window data compressing compression method of claim 5 wherein the sliding window method is a dictionary-based method, the method further comprising:
receiving input data comprising an input data string:
performing a string match search over each sliding window of previous data to determine a longest string of input data matching data contained in each sliding window:
performing a dictionary search over the dynamic dictionary to determine a longest string of input data contained as a reference in the dynamic dictionary:
comparing the length of the longest string of input data matching data contained in each sliding window with the length of the longest string of input data contained as a reference in the dynamic dictionary; and
creating an entry referencing the input data string in the dynamic dictionary only if the longest string of input data matching data contained in each sliding window is greater than the longest string of input data contained as a reference in the dynamic dictionary.

### Claim 10

A computer program stored on a computer readable medium controlling a processing system to perform a method for a sliding window data compression process, the method comprising:
receiving input data comprising an input data string:
searching each of a plurality of sliding windows to locate a longest input data string match, each of the plurality of sliding windows having a sliding window size corresponding to one of a plurality of data string match lengths.

### Claim 11 (depends on 10)

The computer program of claim 10 wherein the processing system comprises a plurality of processors, each processor concurrently performing a search of a corresponding sliding window.

### Claim 12 (depends on 10)

The computer program of claim 10 wherein a smallest data string match length is two bytes.

### Claim 13 (depends on 10)

The computer program of claim 10 wherein each of the sliding windows has a corresponding hash chain.

### Claim 14 (depends on 10)

The computer program of claim 10 wherein the sliding window data compression process is a dictionary-based data compression process, the method further comprising:
performing a dictionary search over the dynamic dictionary to determine a longest input data string contained as a reference in the dynamic dictionary:
comparing the length of the longest input data string matching data contained in each sliding window with the length of the longest input data string contained as a reference in the dynamic dictionary; and
creating an entry referencing the input data string in the dynamic dictionary only if the longest input data string matching data contained in each sliding window is greater than the longest input data string contained as a reference in the dynamic dictionary.