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

Groups > comp.compression > #1195

Re: how to combine the probability of disjoint symbol models?

Show all headers | View raw

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.

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web