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

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 decoder 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.