US 10,567,458 B2Granted

System and method for long range and short range data compression

AssigneeHughes Network Systems, LLC

InventorsUdaya Bhaskar, Chi-Jiun Su

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system and method are provided for use with streaming blocks of data, each of the streaming blocks of data including a number bits of data. The system includes a first compressor and a second compressor. The first compressor can receive and store a number n blocks of the streaming blocks of data, can receive and store a block of data to be compressed of the streaming blocks of data, can compress consecutive bits within the block of data to be compressed based on the n blocks of the streaming blocks of data, can output a match descriptor and a literal segment. The match descriptor is based on the compressed consecutive bits. The literal segment is based on a remainder of the number of bits of the data to be compressed not including the consecutive bits. The second compressor can compress the literal segment and can output a compressed data block including the match descriptor and a compressed string of data based on the compressed literal segment.

Claims20

Dependent claims

A method for compression of a communications data stream, the method comprising:

receiving a one data block of a sequence of data blocks to be compressed, wherein the one each data block comprises a sequence of data bytes;
generating a fingerprint for each data byte of the one data block;
selecting a fingerprint subset comprising a subset of the generated fingerprints;
comparing each fingerprint of the fingerprint subset to prior fingerprints, wherein each of the prior fingerprints corresponds to a respective sequence of data bytes of one or more previously received data blocks of the sequence of data blocks;
determining that a one fingerprint of the fingerprint subset matches a one of the prior fingerprints;
comparing the data bytes from which the one fingerprint was generated to the data bytes of the one or more previously received data blocks corresponding to the matching one of the prior fingerprints;
determining that the data bytes from which the one fingerprint was generated matches the data bytes corresponding to the matching one of the prior fingerprints;
and
within the one data block, replacing the data bytes from which the one fingerprint was generated with a match descriptor, wherein the match descriptor indicates a location within a byte cache that stores the matching data bytes corresponding to the matching one of the prior fingerprints was generated.

6 more elements

An apparatus for compression of a communications data stream, the apparatus comprising:

an input interface configured to receive a one data block of a sequence of data blocks to be compressed, wherein the one each data block comprises a sequence of data bytes;
one or more memory devices;
and
a long-range compression processor configured to (i) generate a fingerprint for each data byte of the one data block, (ii) select a fingerprint subset comprising a subset of the generated fingerprints, (iii) compare each fingerprint of the fingerprint subset to prior fingerprints, wherein each of the prior fingerprints corresponds to a respective sequence of data bytes of one or more previously received data blocks of the sequence of data blocks, (iv) determine that a one fingerprint of the fingerprint subset matches a one of the prior fingerprints, (v) compare the data bytes from which the one fingerprint was generated to the data bytes of the one or more previously received data blocks corresponding to the matching one of the prior fingerprints, (vi) determine that the data bytes from which the one fingerprint was generated matches the data bytes corresponding to the matching one of the prior fingerprints, and (vii) within the one data block, replace the data bytes from which the one fingerprint was generated with a match descriptor, wherein the match descriptor indicates a location within a byte cache, stored in a one of the or more memory devices, which stores the matching data bytes from corresponding to the matching one of the prior fingerprints.

1 more element

Dependencies are inferred from the claim text.

Facts

Application: 15/655,288Filed 20 Jul 2017 · continuation
Priority: 12 Jul 2011
Published: US 2017/0318066 A12 Nov 2017
Granted: 18 Feb 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

H04L 65/60
Network arrangements, protocols or services for supporting real-time applications in data packet communication: network streaming of media packets
H03M 7/30
Conversion of a code where information is represented by a given sequence or number of digits to a code where the same , similar or subset of…:…
H03M 7/3088
Using adaptive string matching, e.g. the Lempel-Ziv method: employing the use of a dictionary, e.g. LZ78
H03M 7/4006
Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code: conversion to or from arithmetic code

Family

Application13/180,969Parent of this continuation · filed 12 Jul 2011
Application14/301,295Parent of this continuation · filed 10 Jun 2014
US 9,716,734 B2Parent of this continuation · filed 25 Jul 2017
US 2017/0318066 A1Pre-grant publication · published 2 Nov 2017
US 2013/0018932 A1Published application
US 2014/0325088 A1Published application
US 10,567,458 B2This patent

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