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

Publishing Venue

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
...