Talk:Elias omega coding

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

???

This article has not yet received a rating on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

Implied probability[edit]

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)[reply]

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)[reply]

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)[reply]

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)[reply]