Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1189 > unrolled thread

how to combine the probability of disjoint symbol models?

Back to article view | Back to comp.compression

Contents

  how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 05:35 -0700
    Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 05:36 -0700
    Re: how to combine the probability of disjoint symbol models? biject <biject.bwts@gmail.com> - 2012-03-22 07:36 -0700
      Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 17:48 -0700
    Re: how to combine the probability of disjoint symbol models? Thomas Richter <thor@math.tu-berlin.de> - 2012-03-22 17:04 +0100
      Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 20:02 -0700
        Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 21:02 -0700
          Re: how to combine the probability of disjoint symbol models? biject <biject.bwts@gmail.com> - 2012-03-22 21:29 -0700
            Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-22 22:38 -0700
    Re: how to combine the probability of disjoint symbol models? moogie <budgetanime@mystarship.com> - 2012-03-23 05:42 -0700

#1189 — how to combine the probability of disjoint symbol models?

As a thought exercise I am attempting to see whether there is some gains to be made via a statistical compression of an already compressed file (as output from another compression method, e.g. LZMA )

My current thought process is as follows:

1. The output of the other compression method produces a file attempting to minimise the entropy, probably at the 8 bit symbol size.

2. As the compressed file is of finite size, there exists a symbol length size (lets call it Smin) (in bits) where there is no duplicate symbols that exist in the compressed file.

3. If we read in this compressed file symbol by symbol (Smin size) then the number of bits necessary to encode each symbol can be derived by the log of the number of unseen symbols in the alphabet divided by log of 2.

4. Arithmetically encode the symbol using the derived probabilities.

5. if we reach the end of file before reading the next symbol fully then we just record those bits as-is

Compression can occur when the symbol size (Smin) is less than the number of bits in the original compressed file.

Before I go too far into my investigation of this idea, are the points above valid? Have I made a logical fallacy?

[toc] | [next] | [standalone]

#1190

sorry for the title of this thread, it was for another post I was going to make.

[toc] | [prev] | [next] | [standalone]

#1191

On Mar 22, 6:35 am, moogie <budgetan...@mystarship.com> wrote:
> As a thought exercise I am attempting to see whether there is some gains to be made via a statistical compression of an already compressed file (as output from another compression method, e.g. LZMA )
>
> My current thought process is as follows:
>
> 1. The output of the other compression method produces a file attempting to minimise the entropy, probably at the 8 bit symbol size.
>
> 2. As the compressed file is of finite size, there exists a symbol length size (lets call it Smin) (in bits) where there is no duplicate symbols that exist in the compressed file.
>
> 3. If we read in this compressed file symbol by symbol (Smin size) then the number of bits necessary to encode each symbol can be derived by the log of the number of unseen symbols in the alphabet divided by log of 2.
>
> 4. Arithmetically encode the symbol using the derived probabilities.
>
> 5. if we reach the end of file before reading the next symbol fully then we just record those bits as-is
>
> Compression can occur when the symbol size (Smin) is less than the number of bits in the original compressed file.
>
> Before I go too far into my investigation of this idea, are the points above valid? Have I made a logical fallacy?

 The fact is you don't get something from nothing.  And Yes many of
the files
will compress smaller. However in general the length of the second
compressed
file will be longer. Here are the problems. You have to have data in
the output
file that tells what the length of Smin is.  Then you have to have
information
on decompression to tell where you switched from your full arithmetic
to the
adding of the trailing of the extra bits.
 Actually with care you can do all the above bijectively but in the
end for
general files you gain nothing.  But if the first compression weak for
the
limited subset of files your using you might gain something for the
limited
subset.


 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"

[toc] | [prev] | [next] | [standalone]

#1194

On Friday, March 23, 2012 1:06:40 AM UTC+10:30, biject wrote:
> On Mar 22, 6:35 am, moogie <budgetan...@mystarship.com> wrote:
> 
>  The fact is you don't get something from nothing.  And Yes many of
> the files
> will compress smaller. However in general the length of the second
> compressed
> file will be longer. Here are the problems. You have to have data in
> the output
> file that tells what the length of Smin is.  Then you have to have
> information
> on decompression to tell where you switched from your full arithmetic
> to the
> adding of the trailing of the extra bits.
>  Actually with care you can do all the above bijectively but in the
> end for
> general files you gain nothing.  But if the first compression weak for
> the
> limited subset of files your using you might gain something for the
> limited
> subset.

Yes i agree, it is necessary to record the number of bits for the size of a Symbol. And I also agree that either a symbol is necessary to inform the decompressor to switch to the extra bits ( or record the file length)

I also agree that there is a limited subset of all posible files where the scheme will work: the set of files where the minimum number of bits necessary to create an alphabet of symbols (in which sequential "reading" of symbols from the file is such that no symbol is repeated) and that minimum number is less than half the file size bits (to allow at least two symbols to be written)

The set of Compressed Files of a given size should be highly represented within this limited set as the symbol size will should be  lower than uncompressed files that contain repeating patterns and thus need more bits in the symbol size.

I guess it depends on the source (i.e. the compressed file) whether the gains will out weigh this extra information necessary.

[toc] | [prev] | [next] | [standalone]

#1193

Am 22.03.2012 13:35, schrieb moogie:
> As a thought exercise I am attempting to see whether there is some gains to be made via a statistical compression of an already compressed file (as output from another compression method, e.g. LZMA )
>
> My current thought process is as follows:
>
> 1. The output of the other compression method produces a file attempting to minimise the entropy, probably at the 8 bit symbol size.
>
> 2. As the compressed file is of finite size, there exists a symbol length size (lets call it Smin) (in bits) where there is no duplicate symbols that exist in the compressed file.

Sorry, I don't understand. What is a symbol length size? The number of 
bits required to encode a symbol? However, you should be aware that the 
"symbols" the encoder is actually encoding are not necessarily the 
"obvious symbols" seen in the source. A symbol - as seen by LZW for 
example - might be an entry in a dictionary that encodes several bytes 
of the source. In such a case, the LZW for example rarely creates a 
symbol more than once. Instead, new symbols are extensions of old 
symbols already seen, and the average number of bits per symbol grows as 
compression proceeds.

>
> 3. If we read in this compressed file symbol by symbol (Smin size)

I don't understand. The size of all symbols is not constant - it depends 
(and must depend) on the symbol. If you read the compressed data in 
chunks each Smin bits size, you get garbadge.

> then the number of bits necessary to encode each symbol can be derived by the log of the number of unseen symbols in the alphabet divided by log of 2.

No, why? That really depends on your model. That the number of symbols 
is proportional to the log of their size is only correct and/or optimal 
for zero-order models. Why should the encoder be that stupid?

> 4. Arithmetically encode the symbol using the derived probabilities.
>
> 5. if we reach the end of file before reading the next symbol fully then we just record those bits as-is
>
> Compression can occur when the symbol size (Smin) is less than the number of bits in the original compressed file.
>
> Before I go too far into my investigation of this idea, are the points above valid? Have I made a logical fallacy?

I afraid the whole idea isn't clear enough to allow me to make a 
judgement on its validity.

Greetings,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1195

On Friday, March 23, 2012 2:34:26 AM UTC+10:30, Thomas Richter wrote:
> Am 22.03.2012 13:35, schrieb moogie:
> Sorry, I don't understand. What is a symbol length size? The number of 
> bits required to encode a symbol? However, you should be aware that the 
> "symbols" the encoder is actually encoding are not necessarily the 
> "obvious symbols" seen in the source. A symbol - as seen by LZW for 
> example - might be an entry in a dictionary that encodes several bytes 
> of the source. In such a case, the LZW for example rarely creates a 
> symbol more than once. Instead, new symbols are extensions of old 
> symbols already seen, and the average number of bits per symbol grows as 
> compression proceeds.

That is correct, a symbol length size is the number of bits to encode a symbol. 

What I am proposing is agnostic to the actual compression method used to create the compressed file, rather it is using the fact that the compressed file has recuded entropy as compared to an uncompressed file of same length. This reduced entropy correlates to a smaller symbol size that ensures that all symbols in the compressed file are unique.
> 
> I don't understand. The size of all symbols is not constant - it depends 
> (and must depend) on the symbol. If you read the compressed data in 
> chunks each Smin bits size, you get garbadge.

I think the confusion arises in that the symbols (input symbols) of the alphabet of which the file is a string of these symbols are not the symbols that are written to the output. The output symbols that represent the input symbols will be from a reduced alphabet that is reducing eachtime a input symbol is read.

> 
> > then the number of bits necessary to encode each symbol can be derived by the log of the number of unseen symbols in the alphabet divided by log of 2.
> 
> No, why? That really depends on your model. That the number of symbols 
> is proportional to the log of their size is only correct and/or optimal 
> for zero-order models. Why should the encoder be that stupid?

Effectively this is a zero order model....

the idea is that there are no correlations between input symbols and so all input symbols are assumed to have the same probability of occuring. the compression occurs due the fact that the input symbols only occur once within the input meaning that the bits necessary to uniquely store an input symbol reduces slightly each time an input symbol is read from the input file.

> 
> I afraid the whole idea isn't clear enough to allow me to make a 
> judgement on its validity.

I hope this helps. I will try to knock up an example to illustrate the method soon.

[toc] | [prev] | [next] | [standalone]

#1196

Input stream: 10011010100010

It is 14 bits long.
The minimum symbol size for an alphabet in which no symbol is used more than once with in the input stream is 3 bits.

Thus the starting alphabet consits of 8 symbols:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

so for each "symbol" in the input:

** Step 1 **

Remaining input 10011010100010
input Symbol: 100

Symbol Table:

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Bits needed per symbol: 3

output symbol index: 4

output stream: 4


** Step 2 **

Remaining input 11010100010
input Symbol: 110

Symbol Table:

0 000
1 001
2 010
3 011
4 101
5 110
6 111

Bits needed per symbol: 2.81

output symbol index: 5

output stream: 4 5


** Step 3 **

Remaining input 10100010
input Symbol: 101

Symbol Table:

0 000
1 001
2 010
3 011
4 101
5 111

Bits needed per symbol: 2.58

output symbol index: 4

output stream: 4 5 4



** Step 4 **

Remaining input 00010
input Symbol: 000

Symbol Table:

0 000
1 001
2 010
3 011
4 111

Bits needed per symbol: 2.32

output symbol index: 0

output stream: 4 5 4 0




This totals 10.71 bits to encode the output + the remaining 2 bits = 12.71 bits

This example does of course not include the overhead of storing the size of the input symbols. But for larger input stream sizes I expect that the cost of storing the symbol size will be overcome by the saving.

On reflection, there is no need to indicate when the remainder bits are to be copied as this is readily determined when we reach EOF without reading in a complete input symbol.

This should give the idea of what i am proposing.

[toc] | [prev] | [next] | [standalone]

#1197

On Mar 22, 10:02 pm, moogie <budgetan...@mystarship.com> wrote:
> Input stream: 10011010100010
>
> It is 14 bits long.
> The minimum symbol size for an alphabet in which no symbol is used more than once with in the input stream is 3 bits.
>
> Thus the starting alphabet consits of 8 symbols:
>
> 0 000
> 1 001
> 2 010
> 3 011
> 4 100
> 5 101
> 6 110
> 7 111
>
> so for each "symbol" in the input:
>
> ** Step 1 **
>
> Remaining input 10011010100010
> input Symbol: 100
>
> Symbol Table:
>
> 0 000
> 1 001
> 2 010
> 3 011
> 4 100
> 5 101
> 6 110
> 7 111
>
> Bits needed per symbol: 3
>
> output symbol index: 4
>
> output stream: 4
>
> ** Step 2 **
>
> Remaining input 11010100010
> input Symbol: 110
>
> Symbol Table:
>
> 0 000
> 1 001
> 2 010
> 3 011
> 4 101
> 5 110
> 6 111
>
> Bits needed per symbol: 2.81
>
> output symbol index: 5
>
> output stream: 4 5
>
> ** Step 3 **
>
> Remaining input 10100010
> input Symbol: 101
>
> Symbol Table:
>
> 0 000
> 1 001
> 2 010
> 3 011
> 4 101
> 5 111
>
> Bits needed per symbol: 2.58
>
> output symbol index: 4
>
> output stream: 4 5 4
>
> ** Step 4 **
>
> Remaining input 00010
> input Symbol: 000
>
> Symbol Table:
>
> 0 000
> 1 001
> 2 010
> 3 011
> 4 111
>
> Bits needed per symbol: 2.32
>
> output symbol index: 0
>
> output stream: 4 5 4 0
>
> This totals 10.71 bits to encode the output + the remaining 2 bits = 12.71 bits
>
> This example does of course not include the overhead of storing the size of the input symbols. But for larger input stream sizes I expect that the cost of storing the symbol size will be overcome by the saving.
>
> On reflection, there is no need to indicate when the remainder bits are to be copied as this is readily determined when we reach EOF without reading in a complete input symbol.
>
> This should give the idea of what i am proposing.


 It would easy to write code so that the symbols are in a header and
for a long
file you could make it completely bijective if you use a fixed length
for symbols like say 8 bits for ascii.  If you require the header to
have the possibility of more than one length then as part of the
information in the file then I don't see how to do it.

 I know it can be done by simple changes to my code for a bijective
Distance Coder all one has to do is finish the stream with the order
of arithmetic you want instead of the using the length of runs. The
bijective DC is written for 8 bit length symbols from the input file.


 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"

[toc] | [prev] | [next] | [standalone]

#1198

>  It would easy to write code so that the symbols are in a header and
> for a long
> file you could make it completely bijective if you use a fixed length
> for symbols like say 8 bits for ascii.  If you require the header to
> have the possibility of more than one length then as part of the
> information in the file then I don't see how to do it.
>
>  I know it can be done by simple changes to my code for a bijective
> Distance Coder all one has to do is finish the stream with the order
> of arithmetic you want instead of the using the length of runs. The
> bijective DC is written for 8 bit length symbols from the input file.
>
>  David A. Scott

What benefit would storing the symbols in a header be? the encoded
symbols can be generated at runtime for both the encdoer and decoder...

[toc] | [prev] | [next] | [standalone]

#1199

Well have run some compressed files though the algorithm and it seems that very little gains are achievable when the file size gets larger. It makes sense in retrospect... as a file gets larger, the symbol size necessary gets larger, however the total number of possible symbols for a given symbol size increases by a power of 2 for each size increment. This means that for every symbol read and removed from the set of possible symbols, the bits necessary to encode a symbol reduces by a minuscule amount. The total saving at the end is less than one bit.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web