GammaKodierung

GammaKodierung, often referred to as Elias-Gamma-Kodierung, is a universal code for positive integers used in information theory and data compression. It encodes numbers into a self-delimiting, variable-length bitstream, favoring smaller numbers when their frequencies are nonuniform.

Encoding and decoding: For a positive integer n, let k be the number of bits in the binary representation of n (k = floor(log2 n) + 1). The code consists of k−1 zero bits followed by the k-bit binary representation of n. For example, n = 5 has binary 101 (k = 3), so it encodes as 00 followed by 101, i.e., 00101. n = 1 has binary 1 (k = 1), encoding as 1. Decoding works by counting leading zeros until the first 1 is encountered; this count determines k, and the following k bits yield n.

Properties and variants: GammaKodierung is a prefix code, meaning no codeword is a prefix of another, which allows self-delimiting decoding without separators. Its encoded length grows roughly with 2 log2 n, making it efficient when smaller integers are common. It is a basic form within a family of universal codes, alongside variants such as Elias delta and gamma codes, which adjust the trade-off between prefix length and data length.

Applications: Used in early data compression schemes, succinct data structures, and representations of integer sequences where small values dominate. It is often employed in conjunction with other coding techniques to encode sequences of integers compactly, such as positions, ranks, or indexes in compressed indexes and file formats. The concept is named after Peter Elias, who introduced universal codes for integers in the 1970s.