Context tree weighting
The context tree weighting method (CTW) is a lossless compression and prediction algorithm by {{harvnb|Willems|Shtarkov|Tjalkens|1995}}. The CTW algorithm is among the very few such algorithms that offer both theoretical guarantees and good practical performance (see, e.g. {{harvnb|Begleiter|El-Yaniv|Yona|2004}}).
The CTW algorithm is an “ensemble method”, mixing the predictions of many underlying variable order Markov models, where each such model is constructed using zero-order conditional probability estimators.
References
- {{Citation
| last1=Willems
| last2=Shtarkov
| last3=Tjalkens
| year=1995
| title=The Context-Tree Weighting Method: Basic Properties
| journal=IEEE Transactions on Information Theory
| publication-place=IEEE Transactions on Information Theory
| volume=41
| number=3
| pages=653–664
| doi=10.1109/18.382012
| url=https://ieeexplore.ieee.org/document/382012
}}
- {{Citation
| last1=Willems
| last2=Shtarkov
| last3=Tjalkens
| year=1997
| title=Reflections on "The Context-Tree Weighting Method: Basic Properties"
| publication-place=IEEE Information Theory Society Newsletter
| volume=47
| number=1
| citeseerx=10.1.1.109.1872
}}
- {{Citation
| last1=Begleiter
| last2=El-Yaniv
| last3=Yona
| year=2004
| title=On Prediction Using Variable Order Markov Models
| publication-place=Journal of Artificial Intelligence Research
| volume=22
| pages=385–421
| url=https://www.jair.org/index.php/jair/article/view/10394
| journal=Journal of Artificial Intelligence Research
| doi=10.1613/jair.1491
| s2cid=47180476
| arxiv=1107.0051
}}
External links
- [http://www.data-compression.info/Algorithms/CTW/ Relevant CTW papers and implementations]
- [https://web.archive.org/web/20150302190939/http://www.ele.tue.nl/ctw/ CTW Official Homepage]
{{Compression methods}}
Category:Lossless compression algorithms
{{comp-sci-stub}}