Method for lossless data reduction of redundant patterns
View Patent ↗The present application describes methods and systems for compressing and/or decompressing data. As blocks of data are processed, the processed blocks are placed into a circular buffer at a compressor and indexed based on patterns of data present in the processed blocks. A circular buffer is maintained at the decompressor so that the decompressor circular buffer is consistent with the compressor circular buffer. When a new block of data is processed, the compressor checks the index to the circular buffer to determine whether the new block of data contains a pattern that is redundant with a pattern in one or more blocks of data that have already been processed. If a redundancy is detected, the compressor informs the decompressor of the redundancy and provides information allowing the decompressor to reconstruct the redundant pattern from the decompressor's circular buffer. In this way, redundant data need not be retransmitted or stored.
1. A method performed in an electronic device in a communication network, the method compressing a stream of data being transmitted in the communication network, the method comprising:
providing a circular buffer for holding data blocks, the circular buffer being divided into fixed equidistant boundaries defining one or more patterns in the processed data blocks;
providing an indexing table that maps a value to a location in the circular buffer corresponding to the value, each location in the circular buffer corresponding to a pattern whose length is defined by the fixed equidistant boundaries, wherein each pattern is represented in the indexing table;
receiving an original data block;
identifying one or more matching patterns that each correspond to a pattern in the original data block that matches a pattern in the circular buffer, each of the matching patterns identified at least in part by calculating a pattern hashing value on the pattern in the original data block and referencing the indexing table to locate the pattern in the circular buffer;
generating an output comprising one or more commands identifying each of the matching patterns and, if the original data block comprises further information in addition to the matching patterns, the output comprises the further information;
storing the output in a memory of the electronic device or transmitting the output to another device in the communication network; and
updating the circular buffer based on the original data block, wherein updating the circular buffer based on the original data block comprises:
maintaining a write position that serves as an index to where the original data block is written to the circular buffer, and
updating the indexing table using the pattern hashing value only if the write position is adjacent to one of the fixed equidistant boundaries of the circular buffer.
2. The method of claim 1 , wherein:
each of the equidistant boundaries is offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hashing value; and
the pattern in the original data block is of size β.
3. The method of claim 2 , wherein β is a power of 2.
4. The method of claim 1 , wherein the circular buffer has a size that is a power of 2.
5. The method of claim 2 , wherein the circular buffer comprises a number n of patterns indexed in the indexing table, and a number of hashing values mapped by the indexing table is also n.
6. The method of claim 1 , wherein identifying the one or more matching patterns comprises:
calculating the pattern hashing value over a first subset of data in the original data block;
using the pattern hashing value as an offset into the indexing table to identify a targeted circular buffer address;
looking up a first set of circular buffer data that is present in the circular buffer at the targeted circular buffer address; and
comparing the first set of circular buffer data to the first subset of data to determine whether the first set of circular buffer data matches the first subset of data.
7. The method of claim 6 , wherein the first set of circular buffer data matches the first subset of data, and further comprising:
identifying a second set of circular buffer data comprising the first set of circular buffer data, wherein the second set of circular buffer data matches a second subset of data in the original data block, the second subset of data comprising the first subset of data.
8. The method of claim 1 , wherein the output further comprises one or more commands identifying data as redundant or non-redundant.
9. The method of claim 1 , wherein the indexing table is updated to reflect the writing of the original data block to the circular buffer.
10. The method of claim 9 , wherein:
the circular buffer is divided into equidistant boundaries, each boundary offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hash value; and
updating the indexing table comprises:
calculating a new information hashing value for a subset of information between two of the equidistant boundaries;
using the new information hashing value as an index location to the indexing table; and
updating the indexing table at the index location with a value corresponding to the position in the circular buffer to which the subset of information is being written divided by β.
11. A non-transitory electronic device readable storage medium storing electronic device readable instructions that, when executed by a processor in an electronic device, perform a method for compressing data, the method comprising:
providing a circular buffer for holding data blocks, the circular buffer being divided into fixed equidistant boundaries defining one or more patterns in the data blocks;
providing an indexing table that maps a value to a location in the circular buffer corresponding to the value, each location in the circular buffer corresponding to a pattern whose length is defined by the fixed equidistant boundaries;
receiving an original data block;
identifying one or more matching patterns that each correspond to a pattern in the original data block that matches a pattern in the circular buffer, each of the matching patterns identified at least in part by calculating a pattern hashing value on the pattern in the original data block and referencing the indexing table to locate the pattern in the circular buffer;
generating an output comprising one or more commands identifying each of the matching patterns and, if the original data block comprises further information in addition to the matching patterns, comprising the further information;
storing the output in a memory of the electronic device or transmitting the output to another electronic device in a communication network; and
updating the circular buffer based on the original data block, wherein updating the circular buffer based on the original data block comprises:
maintaining a write position that serves as an index to where the original data block is written to the circular buffer, and
updating the indexing table using the pattern hashing value only if the write position is adjacent to one of the fixed equidistant boundaries of the circular buffer.
12. The electronic device readable storage medium of claim 11 , wherein:
the circular buffer is divided into equidistant boundaries, each boundary offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hash value; and
the pattern in the original data block is of size β.
13. The electronic device readable storage medium of claim 11 , wherein identifying the one or more matching patterns comprises:
calculating the pattern hashing value over a first subset of data in the original data block;
using the pattern hashing value as an offset into the indexing table to identify a targeted circular buffer address;
looking up a first set of circular buffer data that is present in the circular buffer at the targeted circular buffer address; and
comparing the first set of circular buffer data to the first subset of data to determine whether the first set of circular buffer data matches the first subset of data.
14. The electronic device readable storage medium of claim 13 , wherein the first set of circular buffer data matches the first subset of data, and further comprising:
identifying a second set of circular buffer data comprising the first set of circular buffer data, wherein the second set of circular buffer data matches a second subset of data in the original data block, the second subset of data comprising the first subset of data.
15. The electronic device readable storage medium of claim 11 , wherein:
the circular buffer is divided into equidistant boundaries, each boundary offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hash value; and
updating the indexing table comprises:
calculating a new information hashing value for a subset of information between two of the equidistant boundaries;
using the new information hashing value as an index location to the indexing table; and
updating the indexing table at the index location with a value corresponding to the position in the circular buffer to which the subset of information is being written divided by β.
16. An electronic device comprising:
a memory for storing electronic device readable instructions that, when executed by a processor in the electronic device, perform a method for compressing a stream of data being transmitted in a communication network;
a processor for:
providing a circular buffer for holding data blocks, the circular buffer being divided into fixed equidistant boundaries defining one or more patterns in the processed data blocks,
providing an indexing table that maps a value to a location in the circular buffer corresponding to the value, each location in the circular buffer corresponding to a pattern whose length is defined by the fixed equidistant boundaries, wherein each pattern is represented in the indexing table,
receiving an original data block,
identifying one or more matching patterns that each correspond to a pattern in the original data block that matches a pattern in the circular buffer, each of the matching patterns identified at least in part by calculating a pattern hashing value on the pattern in the original data block and referencing the indexing table to locate the pattern in the circular buffer, and
updating the circular buffer based on the original data block, wherein updating the circular buffer based on the original data block comprises:
maintaining a write position that serves as an index to where the original data block is written to the circular buffer, and
updating the indexing table using the pattern hashing value only if the write position is adjacent to one of the fixed equidistant boundaries of the circular buffer; and
a transmitter for transmitting an output to another device in the communication network, where the output comprises one or more commands identifying each of the matching patterns and, if the original data block comprises further information in addition to the matching patterns, the output comprises the further information.
17. The electronic device of claim 16 , wherein:
the circular buffer is divided into equidistant boundaries, each boundary offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hash value; and
the pattern in the original data block is of size β.
18. The electronic device of claim 16 , wherein identifying the one or more matching patterns comprises:
calculating the pattern hashing value over a first subset of data in the original data block;
using the pattern hashing value as an offset into the indexing table to identify a targeted circular buffer address;
looking up a first set of circular buffer data that is present in the circular buffer at the targeted circular buffer address; and
comparing the first set of circular buffer data to the first subset of data to determine whether the first set of circular buffer data matches the first subset of data.
19. The electronic device of claim 18 , wherein the first set of circular buffer data matches the first subset of data, and further comprising:
identifying a second set of circular buffer data comprising the first set of circular buffer data, wherein the second set of circular buffer data matches a second subset of data in the original data block, the second subset of data comprising the first subset of data.
20. The electronic device of claim 16 , wherein:
the circular buffer is divided into equidistant boundaries, each boundary offset from the previous boundary by an offset β;
the indexing table maps a hashing value calculated over a unit of data having a size of β to a location in the circular buffer corresponding to the hash value; and
updating the indexing table comprises:
calculating a new information hashing value for a subset of information between two of the equidistant boundaries;
using the new information hashing value as an index location to the indexing table; and
updating the indexing table at the index location with a value corresponding to the position in the circular buffer to which the subset of information is being written divided by β.
21. A method performed in an electronic device in a communication network, the method decompressing a compressed data block, the compressed data block being a compressed representation of an original data block, the method comprising:
providing a circular buffer for holding data blocks, the circular buffer being divided into fixed equidistant boundaries defining one or more patterns in the processed data blocks, each of the fixed equidistant boundaries being offset from the previous boundary by an offset β, where β is a power of 2;
receiving a compressed data block comprising one or more commands identifying one or more matching patterns that correspond to data found in the circular buffer;
identifying, based on the one or more commands, one or more matching patterns that each correspond to a pattern in the original data block that matches a pattern in the circular buffer;
retrieving the one or more matching patterns from the circular buffer;
generating an output that corresponds to the original data block;
storing the output in a memory of the electronic device or transmitting the output to another device; and
updating the circular buffer based on the original data block, wherein updating the circular buffer based on the original data block comprises writing the original data block to the circular buffer and, if any overflow information in the original data block extends beyond the end of the circular buffer, writing the overflow information to the beginning of the circular buffer.