Efficient Method of Adaptive Arithmetic Coding for Sources with Large Alphabets

We consider the problem of constructing an adaptive arithmetic code for the case of a large source alphabet. We propose a method with encoding/decoding time, which is an order less than that for known methods. We also propose an implementation of the method with the use of a data structure called an “imaginary sliding window,” which makes it possible to essentially decrease the encoder/decoder memory capacity.