Efficient Run-Length Encoding of Binary Sources with Unknown Statistics

We present a new binary entropy coder of the Golomb family, with an adaptation strategy that is nearly optimum in a maximum-likelihood sense. This new encoder can be implemented efficiently in practice, since uses only integer arithmetic and no divisions. That way, the proposed encoder has a complexity nearly identical to that of popular adaptive Rice coders. However, whereas Golomb-Rice coders have an excess rate with respect to the source entropy of up to 4.2% for binary sources with unknown statistics, the proposed encoder has an excess rate of less than 2%.