Systems and methods for compressing packet data by predicting subsequent data

Patent metadata

Field	Value
Publication number	US-8929402-B1
Application number	US-201213657733-A
Country	US
Kind code	B1
Filing date	Oct 22, 2012
Priority date	Sep 29, 2005
Publication date	Jan 6, 2015
Grant date	Jan 6, 2015

Abstract

A system, method, and computer program for compressing packet data is provided. In exemplary embodiments, one or more prefix arrays may be generated for retrieved data, and used as the basis for predicting subsequent data. The packet data may be compressed based, at least partially, on the predicted subsequent data. Accordingly, the compressed packet data may be transferred over a communication network.

First claim

What is claimed is:

1. A method for compressing data using predicted subsequent characters, comprising:
retrieving a character;
locating a position for a prefix of the retrieved character in a prefix array, the prefix array comprising characters received to that point in a process;
generating at least one prediction of a subsequent character based on a neighborhood of retrieved characters of the prefix of the received character in the prefix array;
ranking the at least one predicted subsequent characters;
determining if the retrieved character is one of the at least one predicted subsequent characters; and
outputting a rank value if the subsequent character is one of the at least one predicted subsequent characters, and transmitting an escape value and the retrieved character if the retrieved character is not one of the at least one predicted subsequent characters.

2. The method of claim 1 , further comprising encoding the escape value and the retrieved character, or the rank value, using an arithmetic encoder.

3. The method of claim 1 , wherein an arithmetic encoder uses neighborhood characters as a context.

4. The method of claim 1 , further comprising inserting the prefix of the retrieved character into the prefix array along with the retrieved character.

5. The method of claim 1 , wherein the rank value is based at least in part on the frequency of occurrence of the predicted subsequent character in the neighborhood of the prefix array.

6. The method of claim 1 , wherein the rank value is based at least in part on the length of prefix of the retrieved character in the prefix array.

7. The method of claim 1 , further comprising priming the prefix array with prefixes from one or more network memory pages.

8. The method of claim 7 , wherein the one or more network memory pages are selected by a scan module.

9. The method of claim 1 , further comprising:
receiving the rank value or the escape value and the retrieved character;
locating the predicted subsequent character based on the rank value in the prefix array; and
outputting the predicted subsequent character based on the rank value, or outputting the retrieved character if the escape value is received.

10. A non-transitory machine readable medium having embodied thereon a program, the program providing instructions for a method for compressing packets, the method comprising:
retrieving a character;
locating a position for a prefix of the retrieved character in a prefix array, the prefix array comprising characters received to that point in a process;
generating at least one prediction of a subsequent character based on a neighborhood of retrieved characters of the prefix of the received character in the prefix array;
ranking the at least one predicted subsequent characters;
determining if the retrieved character is one of the at least one predicted subsequent characters; and
outputting a rank value if the subsequent character is one of the at least one predicted subsequent characters, and transmitting an escape value and the retrieved character if the retrieved character is not one of the at least one predicted subsequent characters.

Assignees

• Hughes David Anthony
• Silver Peak Systems Inc

Inventors

• Hughes David Anthony

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• H04L69/04 Primary

  Protocols for data compression, e.g. ROHC · CPC title

• H03M7/3084

  using adaptive string matching, e.g. the Lempel-Ziv method · CPC title

• H04W28/06

  Optimizing {the usage of the radio link}, e.g. header compression, information sizing {, discarding information (system modifying transmission characteristic according to link quality by modifying frame length H04L1/0007; dynamic adaptation of the packet size for flow control or congestion control H04L47/365)} · CPC title

• H03M7/3086

  employing a sliding window, e.g. LZ77 · CPC title