Communications in Information and Systems

Volume 3 (2003)

Number 2

Fast codes for large alphabets

Pages: 139 – 152

DOI: https://dx.doi.org/10.4310/CIS.2003.v3.n2.a4

Authors

Boris Ryabko (Siberian State University of Telecommunication and Computer Science, Novosibirsk, Russia)

Jaakko Astola (Tampere University of Technology, Tampere, Finland)

Karen Egiazarian (Tampere University of Technology, Tampere, Finland)

Abstract

We address the problem of constructing a fast lossless code in the case when the source alphabet is large. The main idea of the new scheme may be described as follows. We group letters with small probabilities in subsets (acting as super letters) and use time consuming coding for these subsets only, whereas letters in the subsets have the same code length and therefore can be coded fast. The described scheme can be applied to sources with known and unknown statistics.

Keywords

fast algorithms, source coding, adaptive algorithm, cumulative probabilities, arithmetic coding, data compression, grouped alphabet

Published 1 January 2003