a note on sequence prediction over large alphabets注意在序列预测在大字母.pdfVIP

Algorithms 2012, 5, 50-55; doi:10.3390/a5010050 OPEN ACCESS algorithms ISSN 1999-4893 /journal/algorithms Article A Note on Sequence Prediction over Large Alphabets Travis Gagie Department of Computer Science and Engineering, Aalto University, 00076 Aalto, Finland; E-Mail: travis.gagie@aalto.fi Received: 14 November 2011; in revised form: 11 February 2012 / Accepted: 13 February 2012 / Published: 17 February 2012 Abstract: Building on results from data compression, we prove nearly tight bounds on how well sequences of length can be predicted in terms of the size of the alphabet and the length of the context considered when making predictions. We compare the performance achievable by an adaptive predictor with no advance knowledge of the sequence, to the performance achievable by the optimal static predictor using a table listing the frequency of each -tuple in the sequence. We show that, if the elements of the sequence are chosen uniformly at random, then an adaptive predictor can compete in the expected case if , for a constant , but not if . Keywords: sequence prediction; alphabet size; analysis 1. Introduction The relation between compression and prediction dates back at least as far as William of Ockham in the fourteenth century. This relation was not properly formalized, however, until the notion of Kolmogorov complexity was developed in the twentieth century [1–3]. Since then, there have been many efforts to harness compression algorithms for prediction, with a