The
Context-Tree Weighting Project
How it all started
In
May 92 dr. Yuri Shtarkov from the Institute for Problems of Information
Transmission (Moscow) visited our group to do some joint research in source
coding. We (Tjalling, Yuri and myself) decided to take a close look at
Rissanen's Context algorithm and related methods. Our first observation was
that weighting was a better principle than making choices (selection).
Playing around with some examples and probably some luck lead to the above
tree-recursive weighting formula. It comes from the first manuscript which was dated
May 14. The formula says that the weighted probability u in node c is the
average of the estimated probability q corresponding to node c and the product
of the weighted probabilities of its children 0c and 1c.
The analysis of this weighting formula made us more enthusiastic every day. We
decided to submit the result to the IEEE International Symposium on Information
Theory which was to be held in San Antonio in January 1993.
A Mini-Course on Universal Source Coding and Context-Tree Weighting
For the paper "Context-Tree Weighting: Basic Properties" published in the May 1995 issue of the IEEE Transactions on Information Theory, Frans Willems, Yuri Shtarkov and Tjalling Tjalkens received the 1996 Paper Award of the IEEE Information Theory Society. Michelle Effros, editor of the IEEE Information Theory Newsletter asked the authors of the prize paper to write a "Reflections on"-contribution. This article contains a mini-course on universal source coding and an introduction to the Context-Tree Weighting Method. The scanned version of this article is here. More details about the computation of the weighted probabilities related to figure 6 can be found here.
The slides of a tutorial lecture (41MB) that was given in Molle, Sweden, for the 1997 ISIT Technical Program Committee meeting in December of 1996 can be found here. It was during this meeting where we could hear for the first time Jim Massey recite the famous poem “Casey at the Bat”.
List of Results
- The Basic Algorithm
- The Generalized Context Weighting
Method
- Extending the Context-Tree Weighting
Method
- Coding for Piecewise-Stationary
Sources
- Implementing the Context-Tree
Weighting Method
- Text-Compression with the
Context-Tree Weighting Method
The
Basic Algorithm
The
basic principles of the context-tree weighting method are described in the
paper "The Context-Tree Weighting Method : Basic Properties" by
F.M.J. Willems, Y.M. Shtarkov, and Tj.J. Tjalkens which appeared in the 1995
May-issue of the IEEE Transactions on Information Theory, pp. 653-664.
Abstract :
We
describe a sequential universal data compression procedure for binary tree
sources that performs the ``double mixture''. Using a context tree, this method
weights in an efficient recursive way the coding distributions corresponding to
all bounded memory tree sources, and achieves a desirable coding distribution
for tree sources with an unknown model and unknown parameters. Computational
and storage complexity of the proposed procedure are both linear in the source
sequence length. We derive a natural upper bound on the cumulative redundancy
of our method for individual sequences. The three terms in this bound can be
identified as coding, parameter and model redundancy. The bound holds for all
source sequence lengths, not only for asymptotically large lengths. The analysis
that leads to this bound is based on standard techniques and turns out to be
extremely simple. Our upper bound on the redundancy shows that the proposed
context tree weighting procedure is optimal in the sense that it achieves the
Rissanen (1984) lower bound.
A postscript version of the full paper (817 kB is available.
The
Generalized Context Weighting Method
The context-tree weighting method was
generalized to sources with structures (the mechanisms that select the
parameters) that are more complex than the tree structure. The generalized
algorithms are again recursive, and they also achieve optimal redundancy
behavior for sources in the model class for which the algorithm is designed.
All this is discussed in the paper "Context Weighting for General Finite
Context Sources," by F.M.J. Willems, Y.M. Shtarkov and Tj.J. Tjalkens.
This paper is published in the September 1996 issue of the IEEE Transactions on
Information Theory, pp. 1514-1520. 
Abstract:
Context
weighting procedures are presented for sources with models (structures) in four
different classes. Although the procedures are designed for universal data
compression purposes, their generality allows application in the area of
classification.
A postscript version of this paper (567 kB) can be downloaded. Also the slides of a presentation (ISIT Trondheim, 1994) can be viewed here.
Extending
the Context-Tree Weighting Method
Abstract:
First
we modify the basic (binary) context-tree weighting method such that the past
symbols are not needed by the encoder and the decoder. Then we describe how to
make the context-tree depth D infinite, which results in optimal redundancy
behavior for all tree sources, while the number of records in the context tree
is not larger than 2T-1. Here T is the length of the source sequence. For this
extended context-tree weighting algorithm we show that with probability one the
compression ratio is not larger than the source entropy for source sequence
length T approaching infinity for stationary and ergodic sources. This research
is the subject of the paper "The Context-Tree Weighting Method:
Extentensions," by F.M.J. Willems which was recently accepted for
publication in the IEEE Transactions on Information Theory.
A postscript version of a one-page summary (164 kB) is available. It appeared in the Proceedings of the IEEE International Symposium on Information Theory, Trondheim, Norway, June 1994. A full version appear in the IEEE Transactions on Information Theory, March 1998, pp. 792-798.
A postscript version of this paper (260 kB) can be downloaded.
Coding
for Piecewise-Stationary Sources
Weighting
techniques also can be applied for efficient coding of sequences generated by
piecewise stationary sources. The transition pattern can be considered as (part
of) the mechanism that selects the parameter(s) of the source, in other words
as (part of) the model.
For a binary memoryless source for which the parameter changes now and then, we could find two weigthing algorithms that achieve redundancies close to or even equal to the (Merhav-) lower bound that is known for this case. We have reported about these results in the paper "Coding for a Binary Independent Piecewise-Identically Distributed Source" by Frans M.J. Willems. This paper is published in the IEEE Transactions on Information Theory, vol. 42, pp. 2210-2217, November 1996.
Abstract:
Two
weighting procedures are presented for compaction of output sequences generated
by binary independent sources whose unknown parameter may change occasionally.
The resulting codes need no knowledge of the sequence length T, i.e they are
strongly sequential, and also the number of parameter changes is unrestricted.
The additional-transition redundancy of the first method was shown to achieve
the Merhav[1993] lower bound, i.e. log(T) bit per transition. For the second
method we could prove that additional-transition redundancy is not more than
(3/2)log(T) bit per transition, which is more than the Merhav bound, however
the storage and computational complexity of this method are also more interesting
than those of the first method. Simulations show that the difference in
redundancy performance between the two methods is negligible.
A postscript version of this paper (571 kB) is available.
Implementing
the Context-Tree Weighting Method
The
implementation of the Context-Tree Weighting algorithm was the subject of
projectwork that we carried out for KPN Research, Leidschendam, The
Netherlands. This resulted in two papers.
The first one "Complexity Reduction of the Context-Tree Weighting Method" by F.M.J. Willems and Tj.J. Tjalkens which was presented at the "18th Benelux Symposium on Information Theory," May 16 & 17, 1997, in Veldhoven, The Netherlands.
Abstract:
We
present a method to decrease the storage and communication complexity of the
context-tree weighting method. This method is based on combining the estimated
probability of a node in the context tree and weighted probabilities of its
children in one single variable. This variable is represented by its logarithm.
A postscript version of this paper (437 kB) is available. It appeared in the Proceedings of the 18th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 15 & 16, 1997, pp. 123-130.
The second one "Implementing the Context-Tree Weighting Method: Arithmetic Coding" by Tj.J. Tjalkens and F.M.J. Willems was presented at the "International Conference on Combinatorics, Information Theory & Statistics," July 18-20, 1997, in Portland, Maine.
Abstract:
The
context-tree weighting algorithm (1995) is an efficient universal source coding
method for tree sources. Although a finite accuracy version of this algorithm
has been analysed by Willems (1996), it is better to implement the algorithm as
proposed by Willems & Tjalkens (1997). There it was suggested to store in
each node s of the context tree, instead of an estimated probability Pe(s) and
a weighted probability Pw(s) the (logarithm of the) ratio Pe(s)/Pw(os)Pw(1s).
This leads to a considerable storage reduction. Here we present the arithmetic
coding procedure that matches to this implementation. It is based on Tjalkens'
Ph.D. thesis (1987) in which tables are used to circumvent multiplications. We
also present a very simple carry-blocking procedure and briefly analyse it.
A postscript version of this paper (356 kB) is available.
Text-Compression
with the Context-Tree Weighting Method
Although
the CTW-method is a binary technique, or was at least presented as a method for
compressing binary source sequences, it is very well possible to apply this
method to compress ASCII- or Byte-files. The ideas that make this possible,
i.e. binary decomposition, zero-redundancy estimator, and weighting only at
symbol-boundaries, are presented at the Data Compression Conference, March
25-27, 1997, Snowbird, Utah. These ideas make it possible to compress e.g. the
"book2"-file in the Calgary Corpus downto 1.875 bit/ASCII. The
DCC-Proceedings contribution "A Context-Tree Weighting Method for
Text-Generating Sources," by Tj.J. Tjalkens, P.A.J. Volf, and F.M.J.
Willems in postscript (35 kB) can be downloaded.
For more results on text-compression please check the publications of Ph.D. student Paul Volf.
Slides of a lecture on ASCII-CTW (8MB).
IEEE Information
Theory Society Paper Award
For
their paper "Context-Tree Weighting: Basic Properties" published in
the May 1995 issue of the IEEE Transactions on Information Theory, Frans
Willems, Yuri Shtarkov and Tjalling Tjalkens received the 1996 Paper Award of the IEEE
Information Theory Society . The award was presented at the IEEE
International Symposium on Information Theory in Ulm, Germany, June 29 - July
4, 1997.
Michelle Effros, editor of the IEEE Information Theory Newsletter asked the authors of the prize paper to write a "Reflections on"-contribution. This article contains a mini-course on universal source coding and an introduction to the Context-Tree Weighting Method. The postscript version (450 kB) of this article can be downloaded.
MATLAB software (under construction)
A CODING VERSION OF CTW:
- CTWCODERS: Three functions
(initCTW, probestimCTW, and updateCTW) that can be used to compute the
integer probability-vectors that are needed by the arithmetic encoder and
decoder to do the actual coding. There is a script testCTW that
demonstrates the usage of the functions. The arithmetic coding functions
are provided below. Nov. 29, 2007.
- ARITHMCODING: A set of
functions doing arithmetic encoding and decoding. The functions
stepBINARencoder and stepBINARdecoder deal with binary datasymbols,
stepARencoder and stepARdecoder can handle non-binary symbols. Based on
the Rubin-paper (IEEE-IT, Nov. 1979). Test-script included. Nov. 29,
2007.
For
(file-compaction) CTW-software please check: www.ele.tue.nl/ctw/
More CTW Papers and
Documents
F.M.J. Willems, Y.M. Shtarkov, and Tj.J. Tjalkens, "Context Tree Weighting: Basic Properties," first manuscript submitted to IEEE Trans. Inform. Theory, summer 1993.
F.M.J. Willems, Y.M. Shtarkov, and Tj.J. Tjalkens, "Context Weighting: General Finite Context Sources," 14th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 17 - 18, 1993, pp. 120 - 127.
Tj.J. Tjalkens, Y.M. Shtarkov, and F.M.J. Willems, "Context Tree Weighting: Multi-alphabet Sources," 14th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 17 - 18, pp. 128 - 135.
Tj.J. Tjalkens, Y.M. Shtarkov, and F.M.J. Willems, "Sequential Weighting Algorithms for Multi-Alphabet Sources," 6th Joint Swedish-Russian International Workshop on Information Theory, Molle, Sweden, August 22 - 27, 1993, pp. 230 - 234.
F.M.J. Willems, Y.M. Shtarkov, and Tj.J. Tjalkens, "Context Tree Weighting: Redundancy Bounds and Optimality," 6th Joint Swedish-Russian International Workshop on Information Theory, Molle, Sweden, August 22 - 27, 1993, pp. 235-239.
P.A.J. Volf and F.M.J. Willems, "Context Maximizing : Finding MDL Decision Trees," 15th Symposium on Information Theory in the Benelux, Louvain-la-Neuve, Belgium, May 30 - 31, 1994, pp. 192 - 199.
Tj.J. Tjalkens, F.M.J. Willems, and Y.M. Shtarkov, "Multi-Alphabet Universal Coding Using a Binary Decomposition Context Tree Weighting Algorithm," 15th Symposium on Information Theory in the Benelux, Louvain-la-Neuve, Belgium, May 30 - 31, 1994, pp. 259 - 265.
P.A.J. Volf and F.M.J. Willems, "A Study of the Context Tree Maximizing Method," 16th Symposium on Information Theory in the Benelux, Nieuwerkerk a/d IJssel, The Netherlands, May 18 & 19, 1995, pp. 3 - 9.
F.M.J. Willems, "Weighting Algorithms," IEEE Information Theory Workshop, Rydzina, Poland, June 25 - 29, 1995, pp. 7.3.1 -7.3.2.
P.A.J. Volf and F.M.J. Willems, "On the Context Tree Maximizing Algorithm," IEEE International Symposium on Information Theory 1995, Whistler, BC, Canada, Sept. 17 - 22, p. 20.
P.A.J. Volf and F.M.J. Willems, "Context-Tree Weighting for Extended Tree Sources," 17th Symposium on Information Theory in the Benelux, Enschede, The Netherlands, May 30 & 31, 1996, pp. 95 - 101.
F. Willems, "Implementing the Context-Tree Weighting Method," ITW 1996, Haifa, Israel.
Tj.J. Tjalkens, P.A.J. Volf, and F.M.J. Willems, "A Context-Tree Weighting Method for Text-Generating Sources," Data Compression Conference, Snowbird, Utah, March 25-27, 1997, pp. 472 (submission, poster).
P.A.J. Volf and F.M.J. Willems, "A Context-Tree Branch-Weighting Algoritm," 18th Symposium on Information Theory in the Benelux, Veldhoven, The Netherlands, May 15 & 16, 1997, pp. 115 - 122.
P.A.J. Volf, "Context-tree Weighting for Text-Sources," IEEE International Symposium on Information Theory 1997, Ulm, Germany, June 29 - July 4, p. 64.
F. Willems and M. Krom, "Live-and-Die Coding for Binary Piecewise I.I.D. Sources," ISIT 1997, Ulm, Germany, June 29 - July 4, 1997.
F.M.J. Willems, "Random Sequence Generation Using the Context-Tree Weighting Method," ITW 1998, San Diego, California, February 8 - 11, 1998.
P.A.J. Volf and F.M.J. Willems, "The Switching Method: Elaborations," 19th Symposium on Information Theory in the Benelux, May 28 - 29, 1998, pp. 13 - 20.
P.A.J. Volf, and F.M.J. Willems, "Switching Between Two Universal Source Coding Algorithms," Data Compression Conference, Snowbird, Utah, March 30 - April 1, 1998, pp. 491 - 500.
J. Aberg, P. Volf, and F. Willems, "Compressing an Incompressible Sequence," IEEE International Symposium on Information Theory 1998, Cambridge, Massachusetts, August 16 - August 21, 1998, p. 134.
F.M.J. Willems, Tj.J. Tjalkens, and P.A.J. Volf, "On Random-Access Data Compaction," Rudy Ahlswede 60, Bielefeld, Germany, 199x. Also one-page summary at IEEE ITW 1999, Kruger Park, South Africa, June 20 - 25, 1999.
P.A.J. Volf, F.M.J. Willems, and Tj.J. Tjalkens, "Complexity Reducing Techniques for the CTW Algorithm," Benelux Symposium, 1999.
Frans Willems, "Some Challenges in Source Coding," ITG 2000, Munich, Germany, January 2000.
F.M.J. Willems, Y.M. Shtarkov, Tj.J. Tjalkens, "Context Tree Maximizing," 2000 Conference on Information Sciences and Systems, Princeton University, March 15-17, 2000. (In fact this was the second part of the CTW manuscript that was submitted in 1993. The first part was published in 1995.)
A. Nowbakht, Tj.J. Tjalkens, and F.M.J. Willems, "Coding for Sources Satisfying a Permutation Property," 22nd Symposium on Information Theory in the Benelux, May 15 - 16, Enschede, The Netherlands, 2001, pp. 77 - 84.
M.L.A. Stassen and Tj.J. Tjalkens, "A Parallel Implementation of the CTW Compression Algorithm," Proc. 22nd Symposium on Information Theory in the Benelux, May 15 - 16, Enschede, The Netherlands, 2001, pp. 85 - 92.
F.M.J. Willems and P.A.J. Volf, "Reducing Model Cost by Weighted Symbol Decomposition," ISIT 2001, Washington DC, June 24 - 29, 2001.
F.M.J. Willems, A. Nowbahkt-Irani, and P.A.J. Volf, "Maximum a-Posteriori Tree Models," ITG 2002, Berlin, Germany, February, 2002.
A. Nowbakht and F.M.J. Willems, "Faster Universal Modeling for Two Source Classes," Proc. 23nd Symposium on Information Theory in the Benelux, May 29 - 31, 2002, Louvain-la-Neuve, Belgium, pp. 29 - 36.
F.M.J. Willems, Tj.J. Tjalkens, and T. Ignatenko, "Context-Tree Weighting and Maximizing: Processing Betas," Inaugural Workshop ITA (Information Theory and its Applications), UCSD Campus, La Jolla, Febr. 6 - 10, 2006. Presentation. Matlabfiles of a demo.
T. Ignatenko, G.-J. Schrijen, B. Skoric, P. Tuyls, and F. Willems, "Estimating the Secrecy Rate of Physical Unclonable Functions with the Context-Tree Weighting Method," to be presented at IEEE ISIT 2006, Seattle, WA, July 9-14, 2006.
F.M.J. Willems, "Using a Universal Coding Technique for Sources with Large Alphabets to Estimate Differential Entropy," Allerton 2006.
F.M.J. Willems, “Two Source Coding Algorithms,” Keynote Lecture at Workshop Information Theory Meets Biology,” Ulm University, Ulm, Germany, February 16-17, 2010. A: Tutorial: Context-Tree Weighting, B: Context Weighting for General Finite Context Sources.
People involved in
this project
- A. Nowbakht
- T. Ignatenko
- Dr. Y. Shtarkov
- Dr.ir. Tj.J.
Tjalkens
- Dr.ir. P.A.J. Volf
- Dr.ir. F.M.J. Willems
If
you have comments or questions regarding this page, you can send me (Frans
Willems) an e-mail.