Dismiss
InnovationQ will be updated on Sunday, April 29, from 10am - noon ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

# Efficient Run Length Encoding of Integers

IP.com Disclosure Number: IPCOM000109479D
Original Publication Date: 1992-Aug-01
Included in the Prior Art Database: 2005-Mar-24
Document File: 1 page(s) / 58K

IBM

## Related People

Linzer, EA: AUTHOR

## Abstract

An algorithm for the efficient run-length encoding of a string of integers is given. The algorithm is based on a two-stage lookup technique.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 53% of the total text.

Efficient Run Length Encoding of Integers

An algorithm for the efficient run-length encoding of a string
of integers is given.  The algorithm is based on a two-stage lookup
technique.

The algorithm consists of two stages.

In the first stage, the array is segmented into blocks of N
elements, and each of these blocks is mapped into an N bit integer.
We will call the ith block of integers A(i,j) (0&j< N), and the N bit
integer to which it is mapped B(i).  The mapping is defined as
follows.  If A(i,j) is zero then the jth bit of B(i) is zero.
Otherwise, the jth bit of B(i) is 1.  Below are two methods for
accomplishing the mapping.  Neither method requires any conditional
branching.
1.   Pre-compute a look-up table, L(k), of size 2 N.  The 0th element
of L(k) is a 0 and all other elements are a one.  Initialize B(i) to
zero.  Then, for 0&j<N, compute B(i) = B(i) + L(A(i,j)) << (N-j-1),
where "<< m" means shift left logical m places.  When this
computation is finished, the mapping is accomplished.
2.   Create a two-dimensional table of size N x 2 N, LL(m,k).  Each
element of LL(m,k) is an integer of size at least N bits.  The m,k
element of LL is 0 if k is zero and 1 << (N-m-1) otherwise.
Initialize B(i) to zero, and then, for 0 & j < N compute B(i) =
B(i) + LL(j,k).  This method uses more memory than the first method,
but saves one shift per element of A(i,j).

The entire run-length structure of A(i,j) is represented in
...