In this report we look at sequence prediction in the context of predictive text. We propose a method called Sequence Trees and define it formally. We also implement and test several optimizations to improve the space and time complexity of our method. Sequence trees are finally evaluated using two other methods n-grams and classification trees as benchmark methods on the domain of predictive text.
The sequence tree predictor's accuracy within the predictive text domain is better than its classification tree and n-gram counterparts. While its space requirement is a limiting factor the method requires significantly less space than classification trees. The n-gram predictor uses even less space, but also has a lower prediction accuracy than sequence trees. Using the suggested optimizations we however achieve both high prediction and low spacial requirements in the domain of predictive text.