Title :
A factor-graph approach to the context-tree weighting method
Author :
Vontobel, Pascal O.
Author_Institution :
Coordinated Sci. Lab., Illinois Univ., Urbana, IL, USA
Abstract :
Factor graphs (FG) are graphical models with origins in coding theory. The sum-product and the max-product algorithms (SPA/MPA), which operate by message passing in an FG, subsume a great variety of algorithms in coding, signal processing, and artificial intelligence. This paper aims at showing that it is possible to give an FG/SPA interpretation of one of the best data compression algorithms, namely the context-tree weighting (CTW) method. An arithmetic encoder/decoder needs the conditional probabilities of the next symbol can be obtained by performing the SPA on the FG which represents the joint pmf/pdf of all occuring random variables. Once the CTW algorithm is formulated in the FG/SPA-framework, new extensions of the algorithm become readily apparent.
Keywords :
arithmetic codes; data compression; encoding; graph theory; message passing; probability; arithmetic encoder-decoder; coding theory; conditional probabilities; context-tree weighting method; data compression; factor-graph approach; max-product algorithms; message passing; random variables; sum-product algorithms; Arithmetic; Artificial intelligence; Data compression; Decoding; Graphical models; Message passing; Parity check codes; Random variables; Signal processing algorithms; Tree graphs;
Conference_Titel :
Data Compression Conference, 2004. Proceedings. DCC 2004
Print_ISBN :
0-7695-2082-0
DOI :
10.1109/DCC.2004.1281547