# US 12,001,339 B2 · Dictionary compression device and memory system

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

- Number: US 12,001,339 B2
- Document ID: US12001339B2
- Status: Granted
- Kind: B2
- Application number: 17/940,138
- Filed: 2022-09-08
- Published: 2023-09-14
- Granted: 2024-06-04
- Earliest claimed: 2022-03-09
- Assignees: Kioxia Corporation
- Applicants: Kioxia Corporation
- Inventors: Daisuke Yashima; Sho Kodama; Keiri Nakanishi; Masato Sumiyoshi; Youhei Fukazawa; Zheye Wang; Kohei Oikawa; Takashi Miura
- Web page: https://patentgrep.com/patent/US12001339B2

## CPC

- G06F 12/04: Addressing variable-length words or parts of words
- G06F 12/0875: with dedicated cache, e.g. instruction or stack
- G06F 3/0608: {Saving storage space on storage systems}
- G06F 3/0661: {Format or protocol conversion arrangements}
- G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]}
- G06F 12/0246: {in block erasable memory, e.g. flash memory}
- H03M 7/3084: {using adaptive string matching, e.g. the Lempel-Ziv method}
- H03M 7/6058: {Saving memory space in the encoder or decoder}
- G06F 2212/1016: Performance improvement
- G06F 2212/1044: Space efficiency improvement
- G06F 2212/401: Compressed data
- G06F 2212/7202: Allocation control and policies
- 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

According to one embodiment, a dictionary buffer stores dictionary data including a first substring and data before the first substring. A substring generator generates, from second input data, second substrings. A transformer transforms each of the second substrings into a hash value. A read processor reads the dictionary data, using a hash value transformed from a third substring among the second substrings. An acquisition unit compares a data string including the third substring and data before the third substring with the read dictionary data, and acquire first and second match lengths of the third and fourth substrings. A coded data generator generates coded data based on the acquired first and second match lengths.

## Claims

### Claim 1

A dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, the dictionary compression device comprising:
a dictionary buffer including a plurality of storage areas and configured to store dictionary data in a dictionary address of a storage area of the plurality of storage areas, each of the plurality of storage areas corresponding to each of a plurality of first substrings, each of the plurality of first substrings including consecutive data, each of the plurality of first substrings including each of a plurality of pieces of data included in the first input data as a head, the dictionary data including a first substring and data before the first substring included in the first input data, the storage area corresponding to the first substring, the dictionary address corresponding to a hash value transformed from the first substrings;
a substring generator configured to generate, from the second input data, a plurality of second substrings, each of the plurality of second substrings including consecutive data, each of the plurality of second substrings including each of a plurality of pieces of data included in the second input data as a head;
a transformer configured to transform each of the second substrings into a hash value;
a read processor configured to read the dictionary data from a plurality of storage areas included in the dictionary buffer, using a hash value transformed from a third substring among the second substrings as a dictionary address;
an acquisition unit configured to compare a data string including the third substring and data before the third substring included in the second input data with the read dictionary data, and acquire at least one first match length indicating a match length between the third substring and the read dictionary data and at least one second match length indicating a match length between a fourth substring including consecutive data having data before data at a head of the third substring as a head and the read dictionary data; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
dictionary data including the second substring and data before the second substring included in the second input data is written in a storage area corresponding to the second substring, with a hash value that is transformed from the second substring as a dictionary address.

### Claim 2 (depends on 1)

The dictionary compression device according to claim 1, wherein
data having a length of a shortest match length−1 from a head of each of the first substrings and the second substrings is transformed into a hash value, and
the shortest match length is a minimum value of a first match length and a second match length acquired by the acquisition unit.

### Claim 3 (depends on 1)

The dictionary compression device according to claim 1, further comprising
a selector configured to select a first match length indicating a longest match length from a plurality of first match lengths when the first match lengths indicating a match length between the third substring and the read dictionary data are acquired, and select a second match length indicating a longest match length from a plurality of second match lengths when the second match lengths indicating a match length between the fourth substring and the read dictionary data are acquired, wherein
the coded data generator is configured to generate the coded data based on the selected first and second match lengths.

### Claim 4 (depends on 1)

The dictionary compression device according to claim 1, wherein the acquisition unit is configured to acquire a second match length indicating a predetermined longest match length when a match length between the data string and the read dictionary data exceeds the predetermined longest match length.

### Claim 5

A dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, the dictionary compression device comprising:
a dictionary buffer configured to store the first input data;
a hash table configured to store a dictionary address in which the first substring is stored, using, as a table address, a hash value transformed from each of a plurality of first substrings including consecutive data, each of the plurality of first substrings including each of a plurality of pieces of data included in the first input data as a head;
a substring generator configured to generate, from the second input data, a plurality of second substrings including consecutive data, each of the plurality of second substrings including each of a plurality of pieces of data included in the second input data as a head;
a transformer configured to transform each of the second substrings into a hash value;
a first read processor configured to read the dictionary address from the hash table using a hash value transformed from a third substring among the second substrings as a table address;
a second read processor configured to read, from the dictionary buffer, dictionary data including a first substring stored in the dictionary address and data before the first substring included in the first input data based on the read dictionary address;
an acquisition unit configured to compare a data string including the third substring and data before the third substring included in the second input data with the read dictionary data, and acquire at least one first match length indicating a match length between the third substring and the read dictionary data and at least one second match length indicating a match length between a fourth substring including consecutive data having data before data at a head of the third substring as a head and the read dictionary data; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
the second input data is written to the dictionary buffer, and
the dictionary address in which the second substring is written is written in the hash table using a hash value transformed from the second substring as a table address.

### Claim 6 (depends on 5)

The dictionary compression device according to claim 5, wherein
a part of the first substring and the second substring corresponding to a shortest match length −1 from head data of each of the first substrings and the second substrings is transformed into a hash value, and
the shortest match length is a minimum value of a first match length and a second match length acquired by the acquisition unit.

### Claim 7 (depends on 5)

The dictionary compression device according to claim 5, further comprising
a selector configured to select a first match length indicating a longest match length from a plurality of first match lengths when the first match lengths indicating a match length between the third substring and the read dictionary data are acquired, and select a second match length indicating a longest match length from a plurality of second match lengths when the second match lengths indicating a match length between the fourth substring and the read dictionary data are acquired, wherein
the coded data generator is configured to generate the coded data based on the selected first and second match lengths.

### Claim 8 (depends on 5)

The dictionary compression device according to claim 5, wherein the acquisition unit is configured to acquire a second match length indicating a predetermined longest match length when a match length between the data string and the read dictionary data exceeds the predetermined longest match length.

### Claim 9 (depends on 5)

The dictionary compression device according to claim 5, wherein the hash table is configured to store a plurality of dictionary addresses in a same table address.

### Claim 10

A dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, the dictionary compression device comprising:
a dictionary buffer configured to store, for each piece of data, first transformed data including a first hash value transformed from each of a plurality of pieces of data included in the first input data and first complementary data used to inversely transform the first hash value into the data;
a transformer configured to transform each of a plurality of pieces of data included in the second input data into second transformed data including a second hash value and second complementary data used to inversely transform the second hash value into the data;
a substring generator configured to generate a plurality of first substrings from a plurality of consecutive pieces of second transformed data transformed from each of a plurality of pieces of data included in the second input data, the first substrings including the consecutive pieces of second transformed data having each of the pieces of second transformed data as a head;
a search unit configured to search for a second hash value included in consecutive second transformed data included in a second substring among the first substrings from first hash values included in the first transformed data stored in the dictionary buffer, and output a pointer indicating a position of the first transformed data including the first hash value in the dictionary buffer when there is a first hash value matching the consecutive second hash value;
a selector configured to select, from the dictionary buffer, dictionary data including consecutive first transformed data starting from first transformed data stored at a position in the dictionary buffer indicated by the output pointer and first transformed data before the first transformed data stored at the position in the dictionary buffer;
an acquisition unit configured to compare a data string including the second substring and second transformed data before the second substring with the selected dictionary data, and acquire at least one first match length indicating a match length between the second substring and the selected dictionary data and at least one second match length indicating a match length between a third substring including continuous second transformed data and the selected dictionary data, the third substring including the second transformed data before the second transformed data at a head of the second substring as a head; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
the second transformed data is written to the dictionary buffer.

### Claim 11 (depends on 10)

The dictionary compression device according to claim 10, wherein
the search unit is configured to output a pointer indicating a position of the first transformed data including the first hash value in the dictionary buffer when the number of the first hash values matching the consecutive second hash values is at least a shortest match length −1, and
the shortest match length is a minimum value of a first match length and a second match length acquired by the acquisition unit.

### Claim 12 (depends on 10)

The dictionary compression device according to claim 10, further comprising
a match length selector configured to select a first match length indicating a longest match length from a plurality of first match lengths when the first match lengths indicating a match length between the second substring and the selected dictionary data are acquired, and select a second match length indicating a longest match length from a plurality of second match lengths when the second match lengths indicating a match length between the third substring and the selected dictionary data are acquired, wherein
the coded data generator is configured to generate the coded data based on the selected first and second match lengths.

### Claim 13 (depends on 10)

The dictionary compression device according to claim 10, wherein the acquisition unit is configured to acquire a second match length indicating a predetermined longest match length when a match length between the data string and the selected dictionary data exceeds the predetermined longest match length.

### Claim 14 (depends on 10)

The dictionary compression device according to claim 10, further comprising
an inverse transformer configured to transform a hash value included in the second transformed data into the data using second complementary data included in the second transformed data stored in the dictionary buffer, wherein
the coded data generator is configured to generate the coded data based on the transformed data.

### Claim 15

A memory system comprising:
a nonvolatile memory; and
a controller configured to control the nonvolatile memory, the controller including a dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, wherein
the dictionary compression device includes:
a dictionary buffer including a plurality of storage areas and configured to store dictionary data in a dictionary address of a storage area of the plurality of storage areas, each of the plurality of storage areas corresponding to each of a plurality of first substrings, each of the plurality of first substrings including consecutive data, each of the plurality of first substrings including each of a plurality of pieces of data included in the first input data as a head, the dictionary data including a first substring and data before the first substring included in the first input data, the storage area corresponding to the first substring, the dictionary address corresponding to a hash value transformed from the first substrings;
a substring generator configured to generate, from the second input data, a plurality of second substrings, each of the plurality of second substrings including consecutive data, each of the plurality of second substrings including each of a plurality of pieces of data included in the second input data as a head;
a transformer configured to transform each of the second substrings into a hash value;
a read processor configured to read the dictionary data from a plurality of storage areas included in the dictionary buffer, using a hash value transformed from a third substring among the second substrings as a dictionary address;
an acquisition unit configured to compare a data string including the third substring and data before the third substring included in the second input data with the read dictionary data, and acquire at least one first match length indicating a match length between the third substring and the read dictionary data and at least one second match length indicating a match length between a fourth substring including consecutive data having data before data at a head of the third substring as a head and the read dictionary data; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
dictionary data including the second substring and data before the second substring included in the second input data is written in a storage area corresponding to the second substring, with a hash value that is transformed from the second substring as a dictionary address, and
the controller is configured to write data based on the coded data to the nonvolatile memory.

### Claim 16

A memory system comprising:
a nonvolatile memory; and
a controller configured to control the nonvolatile memory, the controller including a dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, wherein
the dictionary compression device includes:
a dictionary buffer configured to store the first input data;
a hash table configured to store a dictionary address in which the first substring is stored, using, as a table address, a hash value transformed from each of a plurality of first substrings including consecutive data, each of the plurality of first substrings including each of a plurality of pieces of data included in the first input data as a head;
a substring generator configured to generate, from the second input data, a plurality of second substrings including consecutive data, each of the plurality of second substrings including each of a plurality of pieces of data included in the second input data as a head;
a transformer configured to transform each of the second substrings into a hash value;
a first read processor configured to read the dictionary address from the hash table using a hash value transformed from a third substring among the second substrings as a table address;
a second read processor configured to read, from the dictionary buffer, dictionary data including a first substring stored in the dictionary address and data before the first substring included in the first input data based on the read dictionary address;
an acquisition unit configured to compare a data string including the third substring and data before the third substring included in the second input data with the read dictionary data, and acquire at least one first match length indicating a match length between the third substring and the read dictionary data and at least one second match length indicating a match length between a fourth substring including consecutive data having data before data at a head of the third substring as a head and the read dictionary data; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
the second input data is written to the dictionary buffer,
a dictionary address in which the second substring is written is written in the hash table using a hash value transformed from the second substring as a table address, and
the controller is configured to write data based on the coded data to the nonvolatile memory.

### Claim 17

A memory system comprising:
a nonvolatile memory; and
a controller configured to control the nonvolatile memory, the controller including a dictionary compression device configured to compress uncompressed data including first input data and second input data by performing dictionary coding on the second input data subsequent to the first input data after performing dictionary coding on the first input data including a plurality of pieces of consecutive data, wherein
the dictionary compression device includes:
a dictionary buffer configured to store, for each piece of data, first transformed data including a first hash value transformed from each of a plurality of pieces of data included in the first input data and first complementary data used to inversely transform the first hash value into the data;
a transformer configured to transform each of a plurality of pieces of data included in the second input data into second transformed data including a second hash value and second complementary data used to inversely transform the second hash value into the data;
a substring generator configured to generate a plurality of first substrings from a plurality of consecutive pieces of second transformed data transformed from each of a plurality of pieces of data included in the second input data, the first substrings including the consecutive pieces of second transformed data having each of the pieces of second transformed data as a head;
a search unit configured to search for a second hash value included in consecutive second transformed data included in a second substring among the first substrings from first hash values included in the first transformed data stored in the dictionary buffer, and output a pointer indicating a position of the first transformed data including the first hash value in the dictionary buffer when there is a first hash value matching the consecutive second hash value;
a selector configured to select, from the dictionary buffer, dictionary data including consecutive first transformed data starting from first transformed data stored at a position in the dictionary buffer indicated by the output pointer and first transformed data before the first transformed data stored at the position in the dictionary buffer;
an acquisition unit configured to compare a data string including the second substring and second transformed data before the second substring with the selected dictionary data, and acquire at least one first match length indicating a match length between the second substring and the selected dictionary data and at least one second match length indicating a match length between a third substring including continuous second transformed data and the selected dictionary data, the third substring including the second transformed data before the second transformed data at a head of the second substring as a head; and
a coded data generator configured to generate coded data for the second input data based on the acquired first and second match lengths, wherein
the second transformed data is written to the dictionary buffer, and
the controller is configured to write data based on the coded data to the nonvolatile memory.