  Prediction suffix trees (PST) provide an effective tool for sequence
modelling and prediction. Current prediction techniques for PSTs rely on exact
matching between the suffix of the current sequence and the previously observed
sequence. We present a provably correct algorithm for learning a PST with
approximate suffix matching by relaxing the exact matching condition. We then
present a self-bounded enhancement of our algorithm where the depth of suffix
tree grows automatically in response to the model performance on a training
sequence. Through experiments on synthetic datasets as well as three real-world
datasets, we show that the approximate matching PST results in better
predictive performance than the other variants of PST.
