Context Set Weighting method
Hee Sun Kim, Zsolt Talata · 2016
Contexts of stationary ergodic sources are considered not necessarily consecutive sequences of symbols of the past. The introduced context set model of a source provides a code that can achieve less parameter redundancy than the code the context tree and generalized context tree models provide. The problem of coding sources with unknown context set is addressed for multialphabet sources. Information on the maximum memory length of the source is not required; it may be even infinite. The Context Set Weighting method is introduced to efficiently calculate a mixture of the Krichevsky-Trofimov distributions over possible context sets. The coding distribution is proved to provide a code whose model redundancy does not exceed the order of the parameter redundancy. An algorithm is provided to compute the Context Set Weighting in a polynomial time.