Home > Archive > Compression > March 2006 > encoding integer
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| cerelaz 2006-03-09, 6:55 pm |
| Hi,
I need to encode an f function which:
given an index i (0<=i<k for some k) returns a tupla x,...,z.
All the values are <= n and such that if f(i)=xi,yi,...,zi and f(i+1)=
xi+1,..., zi+1 then xi<=xi+1 and ... and zi<=zi+1 and xi+...+zi <
x(i+1)+...+z(i+1) but there are relations between others values (e.g.
between xi and zi or z(i+1)).
Is there any way to compress this type of function with a O(1) access
time for all index i ?
thank u very much
| |
| Matt Mahoney 2006-03-10, 6:55 pm |
| cerelaz wrote:
> Hi,
> I need to encode an f function which:
> given an index i (0<=i<k for some k) returns a tupla x,...,z.
> All the values are <= n and such that if f(i)=xi,yi,...,zi and f(i+1)=
> xi+1,..., zi+1 then xi<=xi+1 and ... and zi<=zi+1 and xi+...+zi <
> x(i+1)+...+z(i+1) but there are relations between others values (e.g.
> between xi and zi or z(i+1)).
> Is there any way to compress this type of function with a O(1) access
> time for all index i ?
>
> thank u very much
The best compression algorithm will depend on the probability
distribution. Also, from your description this algorithm will involve
coding the differences between adjacent tuples, but you give up O(1)
access by doing so. Some compromise will be needed, such as storing
absolute values at periodic intervals (which take more space) and
decompressing from that point forward.
-- Matt Mahoney
|
|
|
|
|