Dynamic-history predictive compression (Q1105564)

The problem of compressing a discrete finite ergodic source sequence is approached from a predictive point of view. An algorithm is described that dynamically builds a conditional probability tree by adding leaves in proportion to their potential for reducing the entropy of the tree. This results in a tree that is containable but which can still adapt to unusual source characteristics. An implementation of the algorithm produced compression competitive with other contemporary data compression algorithms.