Run-Length Encoding in a Finite Universe

• Text compression schemes and succinct data structures usually combine sophisticated probability modes with basic coding methods whose average codeword length closely match the entropy of known distributions. In the frequent case where basic coding represents run-lengths of outcomes with probability p, i.e. geometric distribution Pr(i)=pⁱ(1-p), a Golomb code is an optimal instantaneous code, which has the additional advantage that codewords can be computed using only an integer parameter calculated from p, without need for a large or sophisticated data structure. Golomb coding does not, however, gracefully handle the case where run-lengths are bounded by a known integer n, where codewords allocated for the case i>n are wasted. While negligible for large n, this makes Golomb coding unattractive in situations where n is recurrently small, e.g., when representing many short lists, or when the range of n is narrowed down by a recursive algorithm.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Elektroteknik och elektronik -- Datorsystem (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Electrical Engineering, Electronic Engineering, Information Engineering -- Computer Systems (hsv//eng)

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)