A time improvement over the Mycielski algorithm for predictive signal coding: Mycielski-78

Abstract

The Mycielski algorithm is commonly known for applications requiring high quality predictions due to its infinite-past rule based prediction method. Since it repeatedly searches from the beginning of the data source, the complexity becomes non-polynomial, resulting in a limited practical use in multimedia applications, including coding. In this work, we present a time improvement over the Mycielski method by incorporating a codebook for the search which is dynamically constructed during the coding process. The construction method is symmetrical in the encoder and de-coder parts, therefore reconstruction is assured. The idea and strategy resembles the time improvement of the celebrated LZ-78 method over the LZ-77 compression method, where the non-polynomial search is shortened by incorporating a codebook. Analogously, we call the faster method proposed here, the Mycielski-78 method.