# US 11,122,095 B2 · Methods for dictionary-based compression and devices thereof > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,122,095 B2 - Document ID: US11122095B2 - Status: Granted - Kind: B2 - Application number: 16/821,328 - Filed: 2020-03-17 - Published: 2021-03-25 - Granted: 2021-09-14 - Earliest claimed: 2019-09-23 - Assignees: NetApp, Inc. - Applicants: NetApp, Inc. - Inventors: Xing Lin - Web page: https://patentgrep.com/patent/US11122095B2 ## CPC - G06F 3/061: {Improving I/O performance} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/0641: {De-duplication techniques} - G06F 3/067: {Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]} - H04L 41/16: using machine learning or artificial intelligence - H04L 65/61: for supporting one-way streaming services, e.g. Internet radio - H04L 65/65: Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP] - H04L 67/565: Conversion or adaptation of application format or content (adding application control or application functional data H04L67/561) - H04L 67/5651: Reducing the amount or size of exchanged application data - H04L 69/04: Protocols for data compression, e.g. ROHC - H04N 1/32277: {Compression} - H04N 1/64: Systems for the transmission or the storage of the colour picture signal; Details therefor, e.g. coding or decoding means therefor {(H04N19/00 takes precedence)} - H04N 1/648: {Transmitting or storing the primary (additive or subtractive) colour signals; Compression thereof (H04N1/642 - H04N1/646 take precedence)} - H04N 19/00: Methods or arrangements for coding, decoding, compressing or decompressing digital video signals - H04N 19/103: Selection of coding mode or of prediction mode - H04N 19/42: characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation (H04N19/635 takes precedence) - H04N 19/70: characterised by syntax aspects related to video coding, e.g. related to compression standards - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION ## Abstract Methods, non-transitory machine readable media, and computing devices that provide improved dictionary-based compression are disclosed. With this technology, a first portion of an input data stream is compressed using a first dictionary. A second dictionary is trained when the first dictionary is determined to be stale. The dictionary can be determined to be stale based on a size of the input data stream compressed using the first dictionary or a compression ratio decreasing by a threshold, for example. The first dictionary can be stored with metadata associated with the compressed first portion of the input data stream. Accordingly, this technology improves compression ratios, eliminates the need for reference counting, and facilitates improved reclamation of orphan dictionaries, among other advantages. ## Claims ### Claim 1 A method, comprising: compressing, by a computing device, a first portion of an input data stream using a first dictionary; storing, by the computing device, the first dictionary in a first container with first metadata associated with the compressed first portion; compressing, by the computing device, a second portion of the input data stream using the first dictionary when, after the compression of the first portion using the first dictionary, a compression ratio of the first portion is determined to exceed a compression threshold; and storing, by the computing device, the first dictionary in a second container with second metadata associated with the compressed second portion. ### Claim 2 (depends on 1) The method of claim 1, further comprising determining, by the computing device, that the first dictionary is ineffective when the compression ratio is less than another compression ratio of a compressed third portion of the input data stream by another compression threshold, wherein the third portion is compressed using the first dictionary before the first portion is compressed using the first dictionary. ### Claim 3 (depends on 1) The method of claim 1, further comprising training, by the computing device, a second dictionary, when the first dictionary is determined to be ineffective after the compression of the second portion. ### Claim 4 (depends on 3) The method of claim 3, further comprising training, by the computing device, the second dictionary using a third portion of the input data stream that occurs later in the input data stream than the second portion. ### Claim 5 (depends on 1) The method of claim 1, further comprising training, by the computing device, the first dictionary using a third portion of the input data stream that occurs before the first portion in the input data stream. ### Claim 6 (depends on 1) The method of claim 1, further comprising determining, by the computing device, that the first dictionary is ineffective based on a size of the input data stream that has been compressed subsequent to the first dictionary being trained. ### Claim 7 A non-transitory machine readable medium having stored thereon instructions for dictionary-based compression comprising machine executable code that, when executed by at least one machine, causes the machine to: compress a first portion of an input data stream using a first dictionary; determine when a compression ratio of the compressed first portion is below a compression threshold based on a comparison of the compression ratio with another compression ratio of a compressed second portion of the input data stream, wherein the second portion is compressed using the first dictionary; and train a second dictionary, when the determination indicates the compression ratio is below the compression threshold. ### Claim 8 (depends on 7) The non-transitory machine readable medium of claim 7, wherein the machine executable code, when executed by the machine, further causes the machine to train the first dictionary using a third portion of the input data stream that occurs before the first and second portions in the input data stream. ### Claim 9 (depends on 8) The non-transitory machine readable medium of claim 8, wherein the third portion comprises an initial portion of the input data stream. ### Claim 10 (depends on 7) The non-transitory machine readable medium of claim 7, wherein the machine executable code, when executed by the machine, further causes the machine to store the first dictionary in a container with metadata associated with the compressed first portion, when the determination indicates the compression ratio is below the compression threshold. ### Claim 11 (depends on 7) The non-transitory machine readable medium of claim 7, wherein the second portion occurs before the first portion in the input data stream. ### Claim 12 (depends on 11) The non-transitory machine readable medium of claim 11, wherein the second portion occurs immediately prior in the input data stream to the first portion. ### Claim 13 (depends on 7) The non-transitory machine readable medium of claim 7, wherein the machine executable code, when executed by the machine, further causes the machine to train the second dictionary using a third portion of the input data stream that occurs later in the input data stream than the first and second portions. ### Claim 14 A computing device, comprising: a memory containing machine readable medium comprising machine executable code having stored thereon instructions for dictionary-based compression; and a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to: compress a first portion of an input data stream using a first dictionary; determine when the first dictionary is stale based on a size of the input data stream that has been compressed using the first dictionary exceeding a threshold size; and train a second dictionary, when the determination indicates the first dictionary is stale. ### Claim 15 (depends on 14) The computing device of claim 14, wherein the processor is further configured to execute the machine executable code to further cause the processor to train the first dictionary using a second portion of the input data stream that occurs before the first portion in the input data stream. ### Claim 16 (depends on 15) The computing device of claim 15, wherein the second portion comprises an initial portion of the input data stream. ### Claim 17 (depends on 14) The computing device of claim 14, wherein the processor is further configured to execute the machine executable code to further cause the processor to store the first dictionary in a container with metadata associated with the compressed first portion, when the determination indicates the first dictionary is stale. ### Claim 18 (depends on 14) The computing device of claim 14, wherein the processor is further configured to execute the machine executable code to further cause the processor to train the second dictionary using a second portion of the input data stream that occurs later in the input data stream than the first portion. ### Claim 19 (depends on 14) The computing device of claim 14, wherein the processor is further configured to execute the machine executable code to further cause the processor to store the first dictionary with metadata associated with the compressed first portion, when an end of a container that includes the first portion has been reached. ### Claim 20 (depends on 14) The computing device of claim 14, wherein the processor is further configured to execute the machine executable code to further cause the processor to train the first dictionary with a sample data stream until the first dictionary reaches a threshold size.