Prediction Suffix Tree
||This article may require cleanup to meet Wikipedia's quality standards. (August 2008)|
|This article may have been copied and pasted from http://perso.univ-st-etienne.fr/largeron/PATREC.pdf ( · ), possibly in violation of Wikipedia's copyright policy. Please remedy this by editing this article to remove any non-free copyrighted content and attributing free content correctly, or flagging the content for deletion. Please be sure that the supposed source of the copyright violation is not itself a Wikipedia mirror. (July 2015)|
The concept of the Markov chain of order L, which we essentially owe to the Russian mathematician Andrej Andreevic Markov (1907), has two drawbacks. First, the number of parameters of the model grows exponentially with the order L of the chain. This brings about computational and storage problems during implementation, including for limited memory length L.
An improvement initially put forward by (Rissanen - 1983) and used particularly in compression data (Weinberger - 1992, Willems - 1995) was the Variable Length Markov chain (Buhlmann - 1999). This model can be represented by a tree, known as Prediction Suffix Tree – PST (Ron - 1996), certain branches of which are depth L and others of an inferior depth to L, whereas the Markov chain of order L corresponds to a complete tree of depth L. By reducing the storage cost, pruning the branches of the tree will enable us to increase the order of the model and, thereby improve performance.
- Prediction suffix trees for supervised classification of sequences