 |
|
| Science Forum Index » Compression Forum » compression bit by bit... |
|
Page 1 of 1 |
|
| Author |
Message |
| daydreamer... |
 Posted: Wed Sep 16, 2009 2:45 am |
|
|
|
Guest
|
This is for coding a binary sequence. Let n be the length of the
sequence and r the number of 1's in it. The sequence is called X and
the bits are numbered from 0-n-1, from right to left, so the individual
bits from right to left are X[0], X[1],.....
In regular binary encoding, the individual bit positions are assigned
fixed weights. Since compression is desired therefore
1) The weights assigned must be variable , and
2) The weight of any position must only be dependent on the number of
one's so far or r.
Clearly if there are r 1's in a sequence of length n, the weight of
the n+1'th position will be
w = (2^r)(n - r), where ^ is exponentiation.
Below are the simple compression, decompression algorithms,
Here g, is the actual length of the sequence,
n is the current length,
r is the number of 1's so far.
compression
-----------
c = 0;
w = 0;
n = 1;
while(n <= g) {
if(X[n-1] == 1) {
r = r + 1;
if(r == 1) w = n;
c = w + c;
w = 2 * w;
}
else {
w = w + (2 ^ r);
}
n = n + 1;
}
decompression
-------------
r' is the initial value of r, which is the number of 1's in the
original code.
r = r';
n = g;
w = (2^r)(n - r - 1);
while(c > 0 && n > 0) {
if(c >= w) {
X[n - 1] = 1;
r = r - 1;
c = c - w;
w = w / 2;
}
else
w = w - (2^r);
n = n - 1;
}
This algorithm though offers compression, does not generate the
absolute minimal code. For instance, it might be possible to
replace w = w + (2^r), with w = w + 1 (I am not sure since w
will have to be initialized during decompression). But even if it could
the gain may not be significant. Here r <= n /2 can always be
assured, since the complement of the sequence can be encoded.
I believe I do have another method for coding any natural number
x , which gives variable gain for different ratios. I have only
tried two ratios, and the gain is about 1/4 and 2/3, which is still
less than for this binary encoding, and the method is not as simple
as this binary coding, but the ratios I have considered are only
the bare minimum, so for larger ratio's the method might be
comparable if not better than this binary scheme.
Posted using www.webuse.net |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Mon Nov 30, 2009 12:13 pm
|
|