# US 7,609,000 B1 · Variable-length compression technique for encoding or decoding a sequence of integers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,609,000 B1
- Document ID: US7609000B1
- Status: Granted
- Kind: B1
- Application number: 12/042,981
- Filed: 2008-03-05
- Granted: 2009-10-27
- Earliest claimed: 2007-10-22
- Assignees: Google Inc.
- Inventors: Arun Sharma
- Web page: https://patentgrep.com/patent/US7609000B1

## CPC

- H03M 7/40: Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C)

## Abstract

A system that encodes a sequence of integers using a variable-length compression technique is described. During operation, the system scans the sequence of integers and observes the sizes of the integers to determine a threshold value K from the observed sizes. For a given integer which is N bits in length, if N−K is greater than or equal to zero, the system generates a tag for the encoded integer which comprises a sequence of N−K zeros followed by a one, and generates a set of remaining bits for the encoded integer as a sequence of the N bits which make up the integer. Otherwise, if N−K is less than zero, the system generates a tag for the encoded integer as a single one, and generates a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.

## Claims

### Claim 1

A method for compressing a sequence of integers, comprising:
scanning through the sequence of integers and observing the sizes of the integers;
determining a threshold value K from the observed sizes; and
for a given integer which is N bits in length,
if N−K is greater than or equal to zero,
generating a tag for the encoded integer as a sequence of N−K zeros followed by a one, and
generating a set of remaining bits for the encoded integer as a sequence of the N bits which make up the integer.

### Claim 2 (depends on 1)

The method of claim 1, wherein if N−K is less than zero, for the given integer the method further comprises:
generating a tag for the encoded integer as a single one, and
generating a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.

### Claim 3 (depends on 1)

The method of claim 1, further comprising for a given integer to be encoded, prepending the tag to the remaining bits to produce the encoded integer.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
storing all tags generated for the sequence of integers in a first stream; and
storing all remaining bits generated for the sequence of integers in a corresponding second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
combining the tags and the remaining bits generated for the sequence of integers into a single data stream;
wherein a tag generated for a given integer is prepended to the corresponding remaining bits for the given integer.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the threshold value K from the observed sizes involves determining the average size in bits of the integers being encoded and using this average size as the value K.

### Claim 7

A method for decoding a sequence of integers, comprising:
receiving a sequence of integers to be decoded, wherein the sequence of integers was encoded using the threshold value K;
for a given integer in the sequence to be decoded,
scanning through an initial string of zeros for the given integer until a first one is encountered and counting the number of zeros encountered to produce a number L;
discarding the first one; and
using N=K+L remaining bits to form a decoded integer.

### Claim 8 (depends on 7)

The method of claim 7, wherein all tags for the sequence of encoded integers are retrieved from a first stream, and wherein all remaining bits for the sequence of integers are retrieved from a second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 9 (depends on 8)

The method of claim 8, wherein scanning through the initial string of zeros involves executing a first instruction which:
scans through a tag in the first stream until a first one is encountered and counts the number of zeros in the tag to produce a number L; and
generates a corresponding binary tag with the value L.

### Claim 10 (depends on 9)

The method of claim 9, wherein using the remaining N bits to form the decoded integer involves executing a second instruction which decodes integers from the second stream in parallel by:
obtaining a binary tag value L from the sequence of binary tag values;
extracting N=K+L remaining bits from the second stream; and
prepending 32−N zeros to the sequence of N remaining bits to form the decoded integer.

### Claim 11

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for compressing a sequence of integers, comprising:
scanning through the sequence of integers and observing the sizes of the integers;
determining a threshold value K from the observed sizes; and
for a given integer which is N bits in length,
if N−K is greater than or equal to zero,
generating a tag for the encoded integer as a sequence of N−K zeros followed by a one, and
generating a set of remaining bits for the encoded integer as a sequence of the Nbits which make up the integer.

### Claim 12 (depends on 11)

The computer-readable storage medium storing of claim 11, wherein if N−K is less than zero, the method further comprises:
generating a tag for the encoded integer as a single one, and
generating a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.

### Claim 13 (depends on 11)

The computer-readable storage medium of claim 11, further comprising for a given integer to be encoded, prepending the tag to the remaining bits to produce the encoded integer.

### Claim 14 (depends on 13)

The computer-readable storage medium of claim 13, further comprising:
storing all tags generated for the sequence of integers in a first stream; and
storing all remaining bits generated for the sequence of integers in a corresponding second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 15 (depends on 11)

The computer-readable storage medium of claim 11, further comprising:
combining the tags and the remaining bits generated for the sequence of integers into a single data stream;
wherein a tag generated for a given integer is prepended to the corresponding remaining bits for the given integer.

### Claim 16 (depends on 11)

The computer-readable storage medium of claim 11, wherein determining the threshold value K from the observed sizes involves determining the average size in bits of the integers being encoded and using this average size as the value K.

### Claim 17

A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for decoding a sequence of integers, comprising:
receiving a sequence of integers to be decoded, wherein the sequence of integers was encoded using the threshold value K;
for a given integer in the sequence to be decoded,
scanning through an initial string of zeros for the given integer until a first one is encountered and counting the number of zeros encountered to produce a number L;
discarding the first one; and
using N=K+L remaining bits to form a decoded integer.

### Claim 18 (depends on 17)

The computer-readable storage medium of claim 17, wherein all tags for the sequence of encoded integers are retrieved from a first stream, and wherein all remaining bits for the sequence of integers are retrieved from a second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 19 (depends on 18)

The computer-readable storage medium of claim 18, wherein scanning through the initial string of zeros involves executing a first instruction which:
scans through a tag in the first stream until a first one is encountered and counts the number of zeros in the tag to produce a number L; and
generates a corresponding binary tag with the value L.

### Claim 20 (depends on 19)

The computer-readable storage medium of claim 19, wherein using the remaining N bits to form the decoded integer involves executing a second instruction which decodes integers from the second stream in parallel by:
obtaining a binary tag value L from the sequence of binary tag values;
extracting N=K+L remaining bits from the second stream; and
prepending 32−N zeros to the sequence of N remaining bits to form the decoded integer.

### Claim 21

An apparatus for encoding a sequence of integers, comprising:
a scanning mechanism configured to:
scan through the sequence of integers and observe the sizes of the integers, and
determine a threshold value K from the observed sizes; and
an encoding mechanism configured to encode a given integer which is N bits in length by:
if N−K is greater than or equal to zero,
generating a tag for the encoded integer as a sequence of N−K zeros followed by a one, and
generating a set of remaining bits for the encoded integer as a sequence of the Nbits which make up the integer.

### Claim 22 (depends on 21)

The apparatus of claim 21, wherein if N−K is less than zero, the encoding mechanism is configured to encode the given integer by:
generating a tag for the encoded integer as a single one; and
generating a set of remaining bits for the encoded integer by padding the N bits which make up the integer with zeros so that the set of remaining bits is K bits in length.

### Claim 23 (depends on 21)

The apparatus of claim 21, wherein for a given integer to be encoded, the encoding mechanism prepends the tag to the remaining bits to produce the encoded integer.

### Claim 24 (depends on 21)

The apparatus of claim 21, wherein the encoding mechanism is further configured to:
store all tags generated for the sequence of integers in a first stream; and
store all remaining bits generated for the sequence of integers in a corresponding second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 25 (depends on 22)

The apparatus of claim 22, wherein the configuration mechanism is further configured to:
combine the tags and the remaining bits generated for the sequence of integers into a single data stream;
wherein a tag generated for a given integer is prepended to the corresponding remaining bits for the given integer.

### Claim 26 (depends on 21)

The apparatus of claim 21, wherein determining the threshold value K from the observed sizes involves determining the average size in bits of the integers being encoded and using this average size as the value K.

### Claim 27

An apparatus for decoding a sequence of integers, comprising:
a receiving mechanism configured to receive a sequence of integers to be decoded, wherein the sequence of integers was encoded using the threshold value K; and
a decoding mechanism, configured to decode a given integer by:
scanning through an initial string of zeros for the given integer until a first one is encountered and counting the number of zeros encountered to produce a number L;
discarding the first one; and
using N=K+L remaining bits to form a decoded integer.

### Claim 28 (depends on 27)

The apparatus of claim 27, wherein the receiving mechanism is further configured to receive all tags for the sequence of encoded integers from a first stream, and receive all remaining bits for the sequence of integers from a second stream;
wherein the ordering of the tags in the first stream is the same as the ordering of the corresponding remaining bits in the second stream.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein scanning through the initial string of zeros involves executing a first instruction which:
scans through a tag in the first stream until a first one is encountered and counts the number of zeros in the tag to produce a number L; and
generates a corresponding binary tag with the value L.

### Claim 30 (depends on 29)

The apparatus of claim 29, wherein using the remaining N bits to form the decoded integer involves executing a second instruction which decodes integers from the second stream in parallel by:
obtaining a binary tag value L from the sequence of binary tag values;
extracting N=K+L remaining bits from the second stream; and
prepending 32−N zeros to the sequence of N remaining bits to form the decoded integer.