Dynamic Shannon coding

We present the first algorithm for one-pass instantaneous coding which, given ℓ>0 and a string S of length m over an alphabet of size n, is guaranteed to encode S using at most bits (H denotes the 0th-order empirical entropy of S), a proportional length of time, and no codewords longer than logn+ℓ+1 bits.