Talk:Elias omega coding

Who is Elias and why isn't that question addressed on this page? Michael Hardy 03:40, 23 Jan 2005 (UTC)

He's the guy that came up with these codes and it isn't addressed because no one has done it yet. -- Antaeus Feldspar 04:54, 23 Jan 2005 (UTC)

Maybe it's the mysterios P. Elias? see http://ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=1055349 . --Abdull 16:11, 9 March 2006 (UTC)

It's Peter Elias according to David Salomon's book "Variable-length Codes for Data Compression". I've added a link to Peter Elias for his delta, omega, and gamma codes. SteveJothen (talk) 19:44, 16 February 2009 (UTC)

Implied probability

Classicalecon (talk · contribs) added "Implied probability" values to some of the entries of the table. I removed them because the article did not explain what "implied probability" was supposed to mean, and also because "implied probability" is not really accurate.

Ideally one picks a universal code to use so that a symbol which takes n bits to encode has a probability as close to 1/(n^2) as possible. This is not limited to this particular code; it's a basic fact of compression. If a symbol occurs 1/2 of the time, its optimal encoding is in 1 bit. If a symbol occurs 1/4 of the time, its optimal encoding is in 2 bits; if 1/8 of the time, in 3 bits; so on and so forth.

However, it's quite rare that one's probabilities would work out to exact powers of 2 like that. It's even rarer that all one's probabilities would work out to the exact powers of 2 that correspond to the specific powers of 2 that are optimal for a particular universal code. To say, therefore, that using a symbol of a particular bit length "implies" a particular probability is ... just grossly wrong.

If the above doesn't make any sense to you, try this analogy: You are given the task of sorting a large number of colored beads, utilizing four clay jars and the services of a large number of assistants. You know that the most effective method will be to go through a series of sorting stages, dividing the beads as evenly as you can in each stage. To get an idea of the specifics of doing that, you scoop up a handful of beads and count how many of each color you get in that (hopefully-representative) handful. "Okay," you say. "We're going to devote the first jar just to black beads." "Oh," pipes up one of your assistants, "that must mean that the probability of a black bead is 1/4, because you're devoting 1/4 of our jars to storing them!" However, your assistant is wrong. Your sampling actually indicated the probability of a black bead as 1/3, but with only four jars, the closest you could get to 1/3 is 1/4. Your choice would be optimal if the probability was 1/4, but your choice does not "imply" that the probability is 1/4. -- 65.78.13.238 (talk) 16:40, 30 November 2008 (UTC)

As far as I can tell, the term was poorly chosen, for lack of a better one, but the probabilities are certainly useful to have - I've seen these probabilities discussed in connection with coding functions in textbooks. The question is, well, what to call them. The way I would phrase it is "the distribution of values for which this coding yields a minimum-size code." I'll try to edit this in somehow. Note that universal code (data compression) needs updating too. Dcoetzee 10:43, 3 December 2008 (UTC)

On further review I've established that the term "implied distribution" is widespread in the literature. Here are some examples:

"The implied distribution is the one for which the code is best suited" [1]

"The implied distribution of a code is the distribution for which the code is optimal." [2]

"Being non-redundant, the code is efficient for some prior probability distribution over the set of possible trees, but the implied distribution is unrealistic except for uniformly binary trees." [3]

Whether it's a good or bad one, we should stick to standard terminology. That doesn't mean some additional explanation isn't helpful though, and I added some. Dcoetzee 10:59, 3 December 2008 (UTC)

I've also just found a legitimate reference to the full phrase "implied probability distribution":

"That is, C is chosen to make the implied probability distribution..." [4]

I think the current usage is okay, particularly since it's explained in considerable detail at universal code (data compression) (now linked). Dcoetzee 11:05, 3 December 2008 (UTC)