Re: Encoding/decoding ranges of unsigned integers...

d|dq wrote:
> There could be millions of ranges. Sorting them would take too long.
> (too long = longer than acceptable in a soft real-time system)
>
> The minimum value would be 0.
> The maximum value would be the greatest value you can store in an
> unsigned 64-bit integer. (as stated by C99)

> The distribution of the ranges is undetermined [but] At time t1,
> if you were to sort the ranges from left to right ([2,9] < [10,11] < etc.),
> you would find the density of ranges is higher on the left side of the sorted sequence.

Choose a batch size of (say) 100 ranges, or the ranges that arrive
in the next fixed-in-advance interval of time (say, 0.1 second.)
Sort the batch. Encode the minimum left endpoint, the differences
(in order) between consecutive left endpoints, and the lengths (in
order) of the ranges. Take advantage of anything else that might
be discovered about the distribution of the two sequences of deltas
(distance between consecutive left endpoints; consecutive lengths.)
The statement of the problem promises very little, so it may be
unlikely to improve upon an ordinary entropy encoder.

--
.