Home > Archive > Compression > January 2006 > Re: Quantized Indexing Source Code (update & alg. history)
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]
| Author |
Re: Quantized Indexing Source Code (update & alg. history)
|
|
| nightlight 2006-01-12, 3:55 am |
| > I assume if your coder is honest that the number you
> got represents the average of 100 runs its very close
> Very interesting your coder puts out fractional bits.
The fractional bit sizes used are not averages but actual fractional
bit sizes. Their meaning is that if you tell decoder that an index will
take a value from a range 0..M-1, which is M values, then the index
itself has size log(M) bits. For example if I tell decoder: the next
index has M=3, then the size of the index is log(3)=1.58496... bits.
If you have to ship just that single index, the best you can do with it
is a tapered Huffman code, which is 0,10,11 for the 3 values of the
index. That way you will be sending either 1 or 2 bit output, based on
the value of the index itself. The average cost, over multiple and
_separate_ transmissions of such index is 5/3=1.667 bits per shipment,
which is 0.0817 bits above the fractional bit index size log(3), thus
about 5% larger.
If you are shipping several items I1, I2,... (which need not be related
to each other), that have such fractional sizes (meaning there is some
max for each, M1, M2,...known to decoder) you can combine the indexes
into a single mixed radix value V, which in turn is also a fractional
bit item, since its range size is the product of range sizes as: M =
M1*M2*... In this case you would pay a little (such as 5% on avg.
above) _only on the total_ bit fraction for V, while all the individual
item fractions have now been added exactly to obtain fractional size of
V. To compute combined package index V, you interpret I1,I2,... as
digits in mixed radix M1,M2,... and then you convert that number into
binary format using:
V = I1 + I2*M1 + I3*M1*M2 + ... (1)
You also calculate M=M(V), which is total range size of V as:
M = M1 * M2 * M3 * ... (2)
Obviosuly, (1) requires arithmetic precision which grows as much as the
size of index V. I have run into this kind of little coding task many
times, and the best one could do with it were Huffman codes, which
would not only fall short (on avg.) of the ideal size log(M) bits few
percent, but the output size would fluctuate from sequence to sequence
so it didn't package well into pre-assigned fixed size space. The ideal
way, of using (1), becomes impractical as soon as V grows beyond 64
bits.
That is one type of problems on which this new quantization scheme, QI,
does its trick: with QI you can compute combined index (1) and its size
(2), for a tiny cost in precision (which is a very small fraction of
bit), using only N-1 regular precision integer multiplies for N items.
Note that the whole array of 10^6 items in alphabet A=3 was computed by
the QI.exe test program as this packaging problem, with M1=M2=...=3.
Let me explain how QI does it for this case, with A=3 and N items being
combined. In that case (1) and (2) become:
I = D1 + D2*3 + D3*3^2 + D4*3^3 +... DN*3^(N-1) ... (3)
M = 3^N ... (4)
Above, D1,D2,D3,...,DN is the sequence of N digits in base 3, which is
our interpretation of the input sequence. The old style radix
conversion using (3) would need arithmetic precision of log(M) = N
log(3) bits. With QI you do same number of multiplies as in (3), except
in regular integer precision (the QI source is set to 32 bit
precision).
The basic tool QI uses for this is "Sliding Window Integer" (SWI),
which is a numeric type like a floating point (FP) number, except that
it is an integer (see [T3] p. 7). You can look at it as a hybrid of
regular FP numbers and unlimited precision integers. Or like an FP with
more flexibility in rounding and operations. Or like an unlimited
precsion integer with some constraints on its bit pattern.
In any case, an SWI is specified via 3 items: g=precision in bits,
m=mantissa (sliding window, an integer of max width g bits) and
s=exponent (shift, regular integer). Since we'll use fixed g=32, we
don't need to drag g around explicitly any more.
With that, some SWI variable Q is given via a pair of integers Q=(m,s),
meaning Q=m*2^s, i.e. m shifted left s times. The value Q is used in
arithmetic as if it were some long integer m*2^s, but about which we do
know that only 32 bits given in its component m are nonzero and that
there are s zeros follown it. In the source code, the header Qi.h has a
structure SWI, which
is:
typedef union _swi { // SW Integer type
struct {
dword m; // mantissa: 32 bit unsigned
int e; // exponent: signed 32 bit int
};
qword q; // 64-bit alias e.g. for 64-bit compares
} SWI;
Otherwise the arithmetic with Q is exactly the same as with a large
integer of that size. The result of such operations is generally not an
SWI, since extra significant bits may be produced. Except that
computing with Q is faster and Q takes much less memory than a large
integer of similar magnitude (which would be g+s bits wide). Note that
for large integers X < 2^32, the SWI mantissa is simply that number X
and exponent s is 0. For larger numbers, s is nonzero and we keep the
32 bit mantissa m normalized i.e. 2^31 <= m < 2^32.
There only one extra operator used for SW numbers which is lacking in
regular large integer arithmetic, and that is rounding, which is
rounding up to g precision i.e. any large integer X is converted into
SWI format number Q by copying leading g bits of X into intger m and
placing into s the count of bits remaing in the tail of X (tail: bits
we didn't copy into m), then if the tail had any nonzero bit we
increment m (on overflow we renormalize it and increment the exponent
s). Since this is important operation below, I will denote SW rounding
of X as {X}sw.
The QI source has a file Swi.c which implements the SWI arithmetic (as
needed by the rest).
The QI method applied to our problem in eq. (3) breaks into 2 phases:
a) Compute quantized power array Q[i]=A^i for i=0,1,...N
(its elements are of type SWI):
SWI Q[N+1]={1,3, 3^2, 3^3,..., 3^N};
b) Use array Q[] to compute I via radix expansion, eq. (3).
To compute power Q[i+1] for radix A we use Q[i+1]=Q[i]*A, and we
initialize Q[0]=(1,0), Q[1]=(A,0) (see also function new_radix() in
Radix.c for an actual implementation). So far this is the same as if
one were doing regular power table for radix conversions.
The key new element QI brings in here is the handling of the
multiplication Q[i]*A. If Q[i] were just a 32 bit integer, the product
would be a 64 bit integer. Denote Q[i]=(m,s), where m=mantissa of Q[i]
and s=exponent of Q[i]. The SWI arithmetic works like large integer,
hece Q[i]*A = (m*A)*2^2. The result is not SWI any more. We convert it
to SWI using rounding up operator {}sw (which yields SWI variable):
Q[i+1] = { m*A*2^s }sw ... (4)
The function implementing mutiplication with rounding up in (4) is
given as: SWI swuMul(SWI x,dword y) in the file Swi.c.
**Important note is that (4) is the only place we will use rounding up.
>From here on, _all_ operations are _exact_.
With the array Q[] computed, we apply (3) to compute index (which is a
binary value of radix 3 number) for sequence of digits
D[N]={D1,D2,...,DN}. The basic step in (3) is multiplication Di*Q[i],
i=1,2...N, and addition of the result to the sum I. The product
X=Di*Q[i]=Di*m*2^s is a large integer with up to 64 nonzero bits,
followed by s trailing zeros from Q[i]. Hence adding X to I is done by
adding the 64 bit integer Di*m into the buffer I at the bit offset s.
The source file Swi.c has a function swuMulAdd() which combines this
multiplication Di*Q[i] and addition into I at position s. (There are
also functions swuMulx() and swxAdd() which can perform the same in two
separate steps.)
The result of all this is the index I. The number of bits in I is
determined using the fact that I is always smaller than Q[N] (I can
take values from 0 to Q[N]-1). Hence the number of bits in I is
L(I)=log(Q[N]). Since Q[N]=(m,s)=m*2^s, L(I)=s+log(m). Function
radix_szf() in Radix.c computes this fractional size from given N
digits and power array Q[], while function radix_sz() returns the
rounded up integer number of bits.
Note that because of rounding up in (4), value Q[N] is little bit
larger than the exact integer A^N, therefore log(Q[N]) will be larger
than log(A^N)=N*log(A) (that's the number shown as 'exact entropy').
The difference between the two is 1.62e-4 bits for A=3 and N=10^6. In
the earlier post I used rounded up to next integer value for L(I). That
packaging wastes about 1/2 bits. Since decoder will have Q[N] table as
well, we can use mantissa m of Q[N] to package the upper 32 bits of I
(which are extracted at the position s in buffer I) via tapered Huffman
codes. In the test we had: Q[N]=(0xB521509A,1584931) and the average
tapered Huffman length for x < 0xB521509A is 31.5867
bits, hence that would get us on average to within 0.087 bits from the
exact fractional bit value for the whole index I.
> You mention in paper there are 3 parts. One part is the
> lenght of thing compressed and the other is the number
> of ones and the third which I assume the above is the index.
That's correct. The index alone is generally smaller than entropy (for
binary coder: by 1/2 log(n) bits), but the combined count of 1's, which
needs log(n+1) bits, plus index length are longer than the entropy by
approx E=1/2 log(n) bits. The entropy formula for (binary case, p=p(1),
q=p(0), p+q=1):
H(n)=n* [p*log(1/p)+q*log(1/q)] ... (5)
does not include cost of sending n and p, but does include cost of
sending count of 1's, integer k. If coder knows p, then it can encode k
in about 1/2 log(n) bits, hence you code without the earelier excess of
E=1/2 log(n).
Note than in high entropy limit, such as our test case, the exact index
(3) is same as entropy, while the quantized index is slightly larger.
But in high entropy case, coder doesn't need to send any frequency
table since all posible frequencies are enumerated into the same index,
hence the index produce d by QI already has that built in. You do need
to send A and N, which will cost you about 30 bits (the entropy formula
n*log(3) didn't count cost of sending these two either, hence adding
these two items to our size doesn't change our distance from entropy).
> So lets not be generous and round down. from the
> combination part you get 1584962 for the rest of
> needed overhead you need say 69 bits.
> Would it be far to say that you compressed the
> 1000000 sybmols to 1585031 bits,
Roughly, withing your rounding, yes. That is the figure to
match the conditions of an adaptive AC (which I ran in the test).
That is not what we need to send to decode it, though. We don't need to
send frequency table in high entropy limit coding. That frequencty
table size was 39 bits. It was added only to match the cost adaptive AC
had to pay to adapt (which is approximately same as the cost of sending
the frequency table explicitly).
Hence, rounding up sizes for A to 3 bits and for N to 27 bits, you need
30 bits. Rounding up the index, you need 1584963 bits.
Hence the total decodable output for N=10^6 symbols, A=3 is:
DECODABLE OUTPUT = 1584993 bits = 198124.125 bytes
That size is fixed, the same for all inputs. You can check the whole
code-decode-compare in the function radix_iter() in Tests.c file. To
verify the fixed size claim, you can corrupt the bits beyond the
declared size of compressed index and verify that it decodes. Or you
can check dec_radix() function in Radix.c and verify that the first
thing it does is to obtain this same index size in bits and then it
extracts the leading 32 bits of the index using the calculated end (it
decodes it from the end, the last bit is the most significant bit of
the index).
> Let's be clear about this the list is for 3 symbols the
> total bits only refers to the compressed combinations
> and file lenght it does not carry in those bits just
> exactly what those symbols are.
The coder assumes symbols 0,1,2,...A-1. If they are anything else you
need to send separately the A values as a simple array matching the
order of assumed values 0,1,2..., in the input. The array of items is
in whatever size each may be (they could be 64 bit integers, or each
item can be different size from others).
> I am just curious you say you need 2.49 bits to code
> the number 3 where did you get the formula for L(X)
> is it based on some universal number scheme where they
> give a neat way of caulating bits needed for univerasal
> coding of large numbers.
The self-delimiting length is a number log(n)+log(log(n))+...
(as calculated by function sdlen() in Qiutl.c). That's how many bits
one needs to code integers of arbitrary size about which no limit is
known to the coder. Explicit codes exist (such as Elias omega) which
approximate these fractional size with integers, averaging about same
for large enough samples. You can check [1] for a survey and list of
codes.
> Again these are bits you have
> to code them with whole number of bits don't you?
As with other fractional counts, no, you don't need to pay the full
rounding up cost. Since you have A and N (both are self-delimiting in
general case, with no upfront limits on A & N), you can enumerate the
two together and send just one self-delimiting number, so you round
just one fraction for 2 numbers. If you're really after every last
fraction, you can also enumerate the two together with the top 32 bits
of index, so you only pay a single fractional bit rounding on the total
output.
-- References ( http://www.1stworks.com/ref/RefLib.htm )
T1-T3 are on http://www.1stworks.com/ref/qi.htm
1. Peter Fenwick "Punctured Elias Codes for variable-length coding of
the integers (1996)"
http://citeseer.ist.psu.edu/fenwick96punctured.html
| |
| David A. Scott 2006-01-14, 6:55 pm |
| "nightlight" <nightlight@omegapoint.com> wrote in
news:1137259757.952613.146040@g14g2000cwa.googlegroups.com:
>
> Funny to watch you trying to soften the basic realization that QI
> compresses the set with a given parameters (such as N & A) to the
> _exactly_ the same size, down to the very last bit fraction, while AC
> can't even fix it to a single or any number of bits you're willing to
> guarantee (and can't even dream of bit fractions): 'changes very
> little', 'roughly the same', 'will compress longer', 'basically the
> same'.
>
>
Yes writting fractional bits is not a dream I dream about
since its not reality. One can seldom test software fully its
a fact of life many things are beyound the programers control
I have worked on computer systems for over 30 years. What I
have noticed is frequently working code one day is not working
code the next. When complilers change when operating systems
change things happen there are no gurantees in real life.
Except Murphy is there waiting to byte one in the ass. I have
seem even different computers that are supose to be the same
have there on quirks.
However for the contest based on your suggestion arbabc will most
likely compress every file of ABC to the exact same number of bytes.
As one tests by changing the value of Top_value to use less than
64 bits there is a point where you will start to get a variable
number of bytes for the example we have been talking about.
Maybe just what 2**64 means compared to 2**4 means is a little
beyond your scope of understanding.Here is something I was told
in school maybe this applies. In india two people decided to
play a chess game the prize was one grain of wheat for the first
square and 2 for next then 4 for next and etc. Thats 2**64 for the
last square. well 2**4 = 16 2**64= 18,446,744,073,709,551,616
which is more than the number of grains of wheat produced in a
single year. Its likely you could see a difference in such a pile
of wheat if I tried to divide 16 in 3 equal piles. I doubt any
one short of GOD could see the difference in the 3 piles of grains
of wheat if they totaled to 2**64
And for example used, even to buffers my view is the arithmetic
compressed to less than what you got for QI unless now its magically
getting better. The point you can claim you calculated your numbers
wrong or that the way I put the data in buffer is wrong. Who knows
thats why people who really want to get a point across write real
code that can use files. Why do you think Matt and Moffat used files
its so people can verify and test real results. For some reason you
don't seem to want to do this so others can really test your code.
Why is that? After you seemed to have no trouble converting moffats
code to meat your needs. Does this means its easier to take airhtmetic
code and mode it to various needs then it is to try modify the very
code you yourself designed to do a simple arithmetic compression
especially since you go on and on much better it is and the fact
it is meant to reaplace arithmetic means this shoud be an easy
task. In the time we have spent arguing I wrote 4 programs, Sure
based on one early program but it didn't take that much time.
I know better then to totally guaruntee every case. I think
you do too or you would have made it use files like Matt or
Moffat or Me. But you didn't since then it could really be
tested why do you fear that. How much time could it take
one or two hours. I could do it but then you would rightfully
claim I did not do it correct. After all I want to win and
I really can't win unless the designer is the one modifying
the code since he is the one who should truely understand what
it does.
Another picky point you claim over and over to get down
to this exact bit of fraction. For the example we are covering
I see some numer that is xx.50... You never wrote this last
part of the faction other than the .50 is that is it bit exact
you claim QI exact down to the last bit. In this particular
fraction what is the last part of the expansion that you have
so excatly. is it a 1 or 2 or do you know? I don't need to
know the whole fraction just the last nonzero part in decimal
since you seem to have it exactly.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
| |
| David A. Scott 2006-01-14, 6:55 pm |
| "David A. Scott" <daVvid_a_scott@email.com> wrote in
news:Xns974B7D17C3B1DH110W296LC45WIN3030
R@213.155.197.138:
> "nightlight" <nightlight@omegapoint.com> wrote in
> news:1137259757.952613.146040@g14g2000cwa.googlegroups.com:
>
>
> Yes writting fractional bits is not a dream I dream about
> since its not reality. One can seldom test software fully its
> a fact of life many things are beyound the programers control
> I have worked on computer systems for over 30 years. What I
> have noticed is frequently working code one day is not working
> code the next. When complilers change when operating systems
> change things happen there are no gurantees in real life.
> Except Murphy is there waiting to byte one in the ass. I have
> seem even different computers that are supose to be the same
> have there on quirks.
>
> However for the contest based on your suggestion arbabc will most
> likely compress every file of ABC to the exact same number of bytes.
> As one tests by changing the value of Top_value to use less than
> 64 bits there is a point where you will start to get a variable
> number of bytes for the example we have been talking about.
> Maybe just what 2**64 means compared to 2**4 means is a little
> beyond your scope of understanding.Here is something I was told
> in school maybe this applies. In india two people decided to
> play a chess game the prize was one grain of wheat for the first
> square and 2 for next then 4 for next and etc. Thats 2**64 for the
> last square. well 2**4 = 16 2**64= 18,446,744,073,709,551,616
> which is more than the number of grains of wheat produced in a
> single year. Its likely you could see a difference in such a pile
> of wheat if I tried to divide 16 in 3 equal piles. I doubt any
> one short of GOD could see the difference in the 3 piles of grains
> of wheat if they totaled to 2**64
>
> And for example used, even to buffers my view is the arithmetic
> compressed to less than what you got for QI unless now its magically
> getting better. The point you can claim you calculated your numbers
> wrong or that the way I put the data in buffer is wrong. Who knows
> thats why people who really want to get a point across write real
> code that can use files. Why do you think Matt and Moffat used files
> its so people can verify and test real results. For some reason you
> don't seem to want to do this so others can really test your code.
> Why is that? After you seemed to have no trouble converting moffats
> code to meat your needs. Does this means its easier to take airhtmetic
> code and mode it to various needs then it is to try modify the very
> code you yourself designed to do a simple arithmetic compression
> especially since you go on and on much better it is and the fact
> it is meant to reaplace arithmetic means this shoud be an easy
> task. In the time we have spent arguing I wrote 4 programs, Sure
> based on one early program but it didn't take that much time.
>
> I know better then to totally guaruntee every case. I think
> you do too or you would have made it use files like Matt or
> Moffat or Me. But you didn't since then it could really be
> tested why do you fear that. How much time could it take
> one or two hours. I could do it but then you would rightfully
> claim I did not do it correct. After all I want to win and
> I really can't win unless the designer is the one modifying
> the code since he is the one who should truely understand what
> it does.
>
>
> Another picky point you claim over and over to get down
> to this exact bit of fraction. For the example we are covering
> I see some numer that is xx.50... You never wrote this last
> part of the faction other than the .50 is that is it bit exact
> you claim QI exact down to the last bit. In this particular
> fraction what is the last part of the expansion that you have
> so excatly. is it a 1 or 2 or do you know? I don't need to
> know the whole fraction just the last nonzero part in decimal
> since you seem to have it exactly.
>
>
>
> David A. Scott
I just changed one line of code in my compressor and
decompressor I changed the value of "Top_value" with
the 16 F's it was using 64 bits 18446744073709551616 states
So I changed it to 8 F's 32 bits 4294967296 states
to my shock since I did have some faith in your
converting of Moffat code I expected massive number
of bits in the length difference of the 5 test files.
There was ZERO difference. This was a shock reading your
numberous rantings and quotes I truely expected
large differences. Well after getting over the shock
I changed Top_value once again to
4 F's 16 bits 65536 states
I really didn't expect much who uses 16 punny
bits with its low amount of space. I was further
shocked to see nt1.txt and nt2.txt compress to
exactlty the same size 198,121 bytes. But file
nt3.txt went to 198,117 bytes. Which is actually
4 bytes shorter. Then nt4.txt went to 198,124
whick is 3 bytes longer. And the last file nt5.txt
went to 198,123 which is 2 bytes longer. I had
expected massive bit differences since my code
not based on moffat which you state is the best
arithmetic compressor what could be wrong?
Then it dawned on me. Maybe the moffat code
wasn't desinged for the problem. Then there is
still the question of why nt1.txt and nt2.txt
compressed to the same size as the optimal
compression where I used 64 bits. Well I woke
up out of my stupor and realized I made the
file of all A's and the other one of all B's
and the last one of all C's to stress the tests.
Which one must do since any file of A B C could
have been used and if one used a purely random one
with a large number of A's B's and C's though
slightly different numbers of each it would not
be sressing the arithmetic compressor which could
lead to a false conclusion.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
|
|
|
|
|