US 12,001,339 B2Granted

Dictionary compression device and memory system

AssigneeKioxia Corporation

InventorsDaisuke Yashima, Sho Kodama, Keiri Nakanishi, Masato Sumiyoshi, Youhei Fukazawa, Zheye Wang, Kohei Oikawa, Takashi Miura

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims17

Dependent claims

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.

5 more elements

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.

8 more elements

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.

6 more elements

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.

10 more elements

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.

13 more elements

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.

11 more elements

Dependencies are inferred from the claim text.

Facts

Application: 17/940,138Filed 8 Sep 2022
Priority: JP 2022-0361269 Mar 2022
Published: US 2023/0289293 A114 Sep 2023
Granted: 4 Jun 2024
Term ends: Not estimatedThe source records don’t support an estimate.

Classification14 codes

G06F 12/04
Addressing or allocation; Relocation: addressing variable-length words or parts of words
G06F 12/0875
Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches: with…
G06F 3/0608
Specifically adapted to achieve a particular effect: saving storage space on storage systems
G06F 3/0661
Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices: format or protocol…

Family

US 2023/0289293 A1Pre-grant publication · published 14 Sep 2023
US 12,001,339 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key