Fast adaptive coding algorithm (Q2277426)

This paper proposed an adaptive variable-length source coding algorithm, so-called ``frequency coding''. For any message word \(x_ 1...x_ N\) over an alphabet \(A=\{a_ 1,...,a_ n\},\) denoting \(x_{-kn-h+1}=a_ h\), \(k\geq 0\), \(1\leq h\leq n\), the encoder encodes the symbol \(x_ i\) into the first \(m(x_ i,i)\) digits of the binary code of \(Q(x_ i,i)\), concatenating the result onto previous output, where \(\ell =\lceil \log n\rceil,\) \(w=(2^ r-1)2^{\ell},\) \(m(a_ j,i)=1+r+\ell -\lfloor \log (P(a_ j,i)+1)\rfloor,\) \(Q(a_ j,i)=2\sum^{j-1}_{k=1}(P(a_ k,i)+1)+P(a_ j,i)+1,\) and P(a,i) is the number of occurrences of a in \(x_{i-w}x_{i-w+1}...x_{i-1}.\) It is proven in this paper that, for this coding algorithm, redundances are not greater than O(1) as well as time complexities of encoding and of decoding are not greater than \(O(\log^ 2 n)\).