System and method for data compaction utilizing mismatch probability estimation

Patent metadata

Field	Value
Publication number	US-11687241-B2
Application number	US-202217974230-A
Country	US
Kind code	B2
Filing date	Oct 26, 2022
Priority date	Oct 30, 2017
Publication date	Jun 27, 2023
Grant date	Jun 27, 2023

Abstract

A system and method for compacting data that uses mismatch probability estimation to improve entropy encoding methods to account for, and efficiently handle, previously-unseen data in data to be compacted. Training data sets are analyzed to determine the frequency of occurrence of each sourceblock in the training data sets. A mismatch probability estimate is calculated comprising an estimated frequency at which any given data sourceblock received during encoding will not have a codeword in the codebook. Entropy encoding is used to generate codebooks comprising codewords for data sourceblocks based on the frequency of occurrence of each sourceblock. A “mismatch codeword” is inserted into the codebook based on the mismatch probability estimate to represent those cases when a block of data to be encoded does not have a codeword in the codebook. During encoding, if a mismatch occurs, a secondary encoding process is used to encode the mismatched sourceblock.

First claim

What is claimed is:

1. A system for encoding data using mismatch probability estimation, comprising:
a computing device comprising a processor, a memory, and a non-volatile data storage device;
a statistical analyzer comprising a first plurality of programming instructions stored in the memory which, when operating on the processor, causes the computing device to:
receive a training data set for encoding, the training data set comprising sourceblocks of data;
determine a frequency of occurrence of each sourceblock of the training data set;
calculate a mismatch probability estimate comprising a probability that any given sourceblock in a non-training data set to be later received for encoding will not be a sourceblock that was contained in the training data set;
generate a mismatch sourceblock representing sourceblocks that were not contained in the training data set, and assign the mismatch probability estimate to the mismatch sourceblock as the frequency of occurrence of the mismatch sourceblock; and
a codebook generator comprising a second plurality of programming instructions stored in the memory which, when operating on the processor, causes the computing device to:
generate a codebook from the sourceblocks of the training data set and the mismatch sourceblock using an entropy encoding method wherein codewords are assigned to each sourceblock based on its frequency of occurrence.

2. The system of claim 1 , further comprising an encoder comprising a third plurality of programming instructions stored in the memory which, when operating on the processor, causes the computing device to:
receive the non-training data set for encoding, the non-training data set comprising sourceblocks of data;
for each sourceblock of the non-training data set, look up and return the codeword for that sourceblock in the codebook and insert that codeword into an encoded data stream;
where the returned codeword is the codeword for the mismatch sourceblock, generate a new codeword for the looked up sourceblock using a secondary encoding method, and insert the new codeword into the encoded data stream.

3. The system of claim 1 , further comprising a decoder comprising a fourth plurality of programming instructions stored in the memory which, when operating on the processor, causes the computing device to:
receive an encoded data stream comprising codewords;
for each codeword in the encoded data stream, look up and return the sourceblock for that codeword in the codebook and insert that sourceblock into a decoded data stream; and
where the returned sourceblock is the mismatch sourceblock, determine the sourceblock for that codeword using the secondary encoding method, and insert the determined sourceblock into the decoded data stream.

4. The system of claim 1 , wherein the training data set is a low-entropy data set, either having a small subset of sourceblocks of a given size relative to the total possible number of sourceblocks of that size or having a set of sourceblocks closely matching the set of sourceblocks expected in the non-training data set.

5. The system of claim 1 , wherein the entropy encoding method is Huffman coding or a known variant thereof.

6. The system of claim 1 , wherein the mismatch probability estimate, q, is calculated as q=M/N, where:
M is the number of times a previously-unobserved sourceblock appeared in the training data set; and
N is the total number of sourceblocks observed in the training data set.

7. The system of claim 6 , wherein the mismatch probability estimate, q, is calculated as q=M/N=(Σ j=1 N X j )/N, where:

X
j

=

{

1
⁢

if
⁢

S
j

∉

{

S
i

:

1

≤
i
<
j

}

0
⁢

otherwise

;

and
N is the total number of sourceblocks observed in the training data set.

8. The system of claim 7 , wherein an exponentially-weighted moving average is applied to the calculation of q=(Σ j=1 N X j )/N.

9. The system of claim 8 , wherein the exponentially-weighted moving average is a modified form of an exponentially-weighted moving average of the form:

μ
j

=

{

1
⁢

if
⁢

j

=
0

(

1
-

β
j

)

⁢

μ

j
-
1

+

β
j

⁢

X
j

⁢

Assignees

• Atombeam Technologies Inc

Inventors

• Cooper Joshua
• Riahi Aliasghar
• Haddad Mojgan
• Riahi Ryan Kourosh
• Riahi Razmin
• Yeomans Charles

Classifications

• H03M7/6011

  Encoder aspects · CPC title

• H03M7/6005

  Decoder aspects · CPC title

• G06F3/0623

  in relation to content · CPC title

• G06F3/0608 Primary

  Saving storage space on storage systems · CPC title

• G06F3/0659

  Command handling arrangements, e.g. command buffers, queues, command scheduling · CPC title