[Israel.pm] binary vectors representation

Shlomi Fish shlomif at iglu.org.il
Sun Jun 13 07:14:15 PDT 2004


On Sunday 13 June 2004 16:23, Shlomo Yona wrote:
> On Sun, 13 Jun 2004, semuel wrote:
> > Hello There.
> >
> > What about RLE? (Run-Length-Encoding)
> > Can be a good cast for this.
>
> What is it?

Run Length Encoding (or RLE for short) is a method of encoding that replaces 
every sequence of 1 or more identical values with the a pair that contains 
the value and the number of items it was repeated. For example:

1,1,1,1,2,2,3,3,3,3,3,1,1

===>

(1*4),(2*2),(3*5),(1*2)

This will work well if you have many (especially long) sequences of identical 
values, and will perform quite poorly otherwise.

The problem with RLE as far as your problem is concerned, is that with an RLE 
representation it would be difficult to determine if bit No. $i is 1 or zero. 
(it would actually be an O(n) operation). 

What I suggest instead is to simply store the indices of the bits marked as 1 
in a Set of some sort (say the keys of a hash, or a balanced binary tree), 
and lookup, add or remove elements from it in accordance with the operations 
on the bit sequence.

Regards,

	Shlomi Fish
-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Quidquid latine dictum sit, altum viditur.
        [Whatever is said in Latin sounds profound.]



More information about the Perl mailing list