A Universal Encoding Method with Nonexponential Work Expenditure for a Source of Independent Messages

A method is proposed for the encoding of a source of independent messages the statistical distribution of which is unknown and the redundancy of which tends to zero as the length of the encoding block is increased. The method is distinguished by the simplicity of its computational procedure, and its work expenditure is a power function of the block length. A slight modification of the universal encoding method makes it possible to construct an asymptotically optimal statistical code for a source having a known distribution.