CODEWITHSUNDEEP
encodingcompression
user1325120
user1325120

Reputation: 85

Elias Gamma Coding and upper bound

While reading about Elias Gamma coding on wikipedia, I see it mentions that:

"Gamma coding is used in applications where the largest encoded value is not known ahead of time."

and that:

"It is used most commonly when coding integers whose upper-bound cannot be determined beforehand."

I don't really understand what is meant by these sentences, because whenever this algorithm is coded, the largest value of the test data or range of the test data would be known before hand. Any help is appreciated!

Upvotes: 1

Views: 1002

Answers (1)

Rubens
Rubens

Reputation: 14778

As far as I'm acquainted with Elias-gamma/delta encoding, the first sentence simply states that these compression methods are global, which means that it does not rely on the input data to generate the code. In other words, these methods do not need to process the input before performing the compression (as local methods do); it compresses the data with a function that does not depend on information from the database.

As for the second sentence, it may be taken as a guarantee that, although there may be some very large integers, the encoding will still perform well (and will represent such values with feasible amount of bytes, i.e., it is a universal method). Notice that, if you knew the biggest integer, some approaches (like minimal hashes) could perform better.

As a last consideration, the same page you referred to also states that:

Gamma coding is used in applications where the largest encoded value is not known ahead of time, or to compress data in which small values are much more frequent than large values.

This may be obtained by generating lists of differences from the original lists of integers, and passing such differences to be compressed instead. For example, in a list of increasing numbers, you could generate:

list: 1 5 29 32 35 36 37
diff: 1 4 24 3  3  1  1

Which will give you many more small numbers, and therefore a greater level of compression, than the first list.

Upvotes: 3

Related Questions