IP Library › Granted Patent US 11,804,853
Granted Patent B2
US 11,804,853 · App. 17/614,853 · Granted Oct 31, 2023

Real-time history-based byte stream compression

Inventor: Muhammad Dawood (High Wycombe, GB)
H03M7/42H03M7/3084
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 11,804,853
App. No.
17/614,853
Filed
Nov 29, 2021
Granted
Oct 31, 2023
Kind
B2
Art Unit
2845
USPC
341/51
Abstract

Systems and methods for stream-based compression are described. One example is an encoder of a first device that receives an input stream of bytes including a first byte preceded by one or more second bytes. The encoder may determine to identify a prefix code for the first byte. The encoder may select a prefix code table using the one or more second bytes. The encoder may identify, from the selected prefix code table, the prefix code of the first byte. The encoder may generate an output stream of bytes by replacing the first byte in the input stream with the prefix code of the first byte. The encoder may transmit the output stream from the encoder of the first device to a decoder of a second device. The output stream may have a fewer number of bits than the input stream.

Claims (49)

1. A computer-implemented method, comprising:

determining that a first data unit in a first data set is to be encoded with a prefix code to generate a portion of a second data set, the first data set including at least a second data unit in addition to the first data unit;

selecting, based at least in part on the first data unit having a first relationship with at least the second data unit within the first data set, a first prefix code table from among a first plurality of prefix code tables, the first plurality of prefix code tables including at least the first prefix code table and a second prefix code table, wherein the first prefix code table includes a first prefix code for the first data unit and the second prefix code table includes a second prefix code for the first data unit, the first prefix code including a different number of bits than the second prefix code; and

generating the portion of the second data set by encoding the first data unit using the first prefix code from the first prefix code table.

2. The computer-implemented method of claim 1 , wherein generating the portion of the second data set further comprises:

replacing the first data unit in the first data set with the first prefix code.

3. The computer-implemented method of claim 1 , wherein selecting the first prefix code table from among the first plurality of prefix code tables further comprises:

determining that the first prefix code table is indexed by the second data unit.

4. The computer-implemented method of claim 1 , further comprising:

determining that the first data unit has the first relationship with the second data unit at least in part by determining that the second data unit occupies a particular position relative to the first data unit within the first data set.

5. The computer-implemented method of claim 4 , wherein:

the first prefix code includes a first number of bits corresponding to a first likelihood of the first data unit occupying the particular position relative to the second data unit; and

the second prefix code includes a second number of bits corresponding to a second likelihood of the first data unit occupying the particular position relative to a different data unit in the first data set.

6. The computer-implemented method of claim 1 , further comprising:

decompressing the second data set using a second plurality of prefix code tables to yield the first data set.

7. The computer-implemented method of claim 1 , wherein the first prefix code includes fewer bits than the second prefix code.

8. A computing system, comprising:

at least one processor; and

at least one computer readable medium encoded with instructions which, when executed by the at least one processor, cause the computing system to:

determine that a first data unit in a first data set is to be encoded with a prefix code to generate a portion of a second data set, the first data set including at least a second data unit in addition to the first data unit,

select, based at least in part on the first data unit having a first relationship with at least the second data unit within the first data set, a first prefix code table from among a first plurality of prefix code tables, the first plurality of prefix code tables including at least the first prefix code table and a second prefix code table, wherein the first prefix code table includes a first prefix code for the first data unit and the second prefix code table includes a second prefix code for the first data unit, the first prefix code including a different number of bits than the second prefix code, and

generate the portion of the second data set by encoding the first data unit using the first prefix code from the first prefix code table.

9. The computing system of claim 8 , wherein the at least one computer readable medium is further encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

replace the first data unit in the first data set with the first prefix code.

10. The computing system of claim 8 , wherein the at least one computer readable medium is further encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

select the first prefix code table from among the first plurality of prefix code tables at least in part by determining that the first prefix code table is indexed by the second data unit.

11. The computing system of claim 8 , wherein the at least one computer readable medium is further encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

determine that the first data unit has the first relationship with the second data unit at least in part by determining that the second data unit occupies a particular position relative to the first data unit within the first data set.

12. The computing system of claim 11 , wherein:

the first prefix code includes a first number of bits corresponding to a first likelihood of the first data unit occupying the particular position relative to the second data unit; and

the second prefix code includes a second number of bits corresponding to a second likelihood of the first data unit occupying the particular position relative to a different data unit in the first data set.

13. The computing system of claim 8 , wherein the at least one computer readable medium is further encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

decompress the second data set using a second plurality of prefix code tables to yield the first data set.

14. The computing system of claim 8 , wherein the first prefix code includes fewer bits than the second prefix code.

15. At least one non-transitory computer readable medium encoded with instructions which, when executed by at least one processor of a computing system, cause the computing system to:

determine that a first data unit in a first data set is to be encoded with a prefix code to generate a portion of a second data set, the first data set including at least a second data unit in addition to the first data unit;

select, based at least in part on the first data unit having a first relationship with at least the second data unit within the first data set, a first prefix code table from among a first plurality of prefix code tables, the first plurality of prefix code tables including at least the first prefix code table and a second prefix code table, wherein the first prefix code table includes a first prefix code for the first data unit and the second prefix code table includes a second prefix code for the first data unit, the first prefix code including a different number of bits than the second prefix code; and

generate the portion of the second data set by encoding the first data unit using the first prefix code from the first prefix code table.

16. The at least one non-transitory computer readable medium of claim 15 , encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

replace the first data unit in the first data set with the first prefix code.

17. The at least one non-transitory computer readable medium of claim 15 , encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

select the first prefix code table from among the first plurality of prefix code tables at least in part by determining that the first prefix code table is indexed by the second data unit.

18. The at least one non-transitory computer readable medium of claim 15 , encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

determine that the first data unit has the first relationship with the second data unit at least in part by determining that the second data unit occupies a particular position relative to the first data unit within the first data set.

19. The at least one non-transitory computer readable medium of claim 18 , wherein:

the first prefix code includes a first number of bits corresponding to a first likelihood of the first data unit occupying the particular position relative to the second data unit; and

the second prefix code includes a second number of bits corresponding to a second likelihood of the first data unit occupying the particular position relative to a different data unit in the first data set.

20. The at least one non-transitory computer readable medium of claim 15 , encoded with additional instructions which, when executed by the at least one processor, further cause the computing system to:

decompress the second data set using a second plurality of prefix code tables to yield the first data set.