Readme.txt

This file describes the implementation of the lossy continuous 
alphabet compressor and other files related to our paper.
This implementation expands on Shirin Jalali's implementation
in several ways:

1. From bits (Jalali) to finite alphabet (NEW) of arbitrary cardinality.

2. Enhancements to Shirin's code including modified data structures and 
global variables that accelerate the Matlab code.

3. Instead of a discrete alphabet (Jalali), the new implementation
maps from finite alphabet to real-valued reproduction levels. This
concept is similar to a 1999 paper by Yang and Zhang.

Dror, 4.12.2011
-----------------

MAIN MATLAB FILES
-----------------
main_profiler.m
This is a wrapper file similar to main_Laplace04082011.m and 
main_AR04082011.m (details below) but greatly simplified. It generates
an input, compresses it, and invokes Matlab's profiler. This is the
first file you should look at when trying to use this package.

encoder_MCMC_03102011.m - The actual compressor. Sets up data 
structures for contexts; runs d_update and count_update_all each 
iteration to update symbol counts, moments, entropy, and distortion. 
I incorporated sanity checks that verify integrity of various data 
structures and computations. This implementation uses 
count_update_all.m (below), which includes several accelerations.

count_update_all.m - evaluates all possible symbols and computes
Gibbs distribution; then generates new symbol and updates data
structures accordingly. Instead of working directly on the context
counts data structure, only locations of changes are saved; this
accelerates performance when the context count matrix is big.

main_Laplace_04082011.m
main_AR_04082011.m
Thse two files run compress using multiple alphabet sizes and multiple
RD slopes for Laplace and autoregressive (AR) sources. For the most 
part these are wrapper files around encoder_MCMC.m, which is the actual 
compressor. Each file generates a data file and plot that compares the
rate distortion function, simulation results, entropy coding, etc.

DATA FILE
---------
laplace_RD_load.mat
Contains data about the rate distortion limit of the Laplace 
distribution. This data is used in main_Laplace_04082011.m to plot 
the RD function.


OTHER MATLAB ROUTINES
---------------------
alph2int.m - converts string over finite alphabet into integer.

bad_comparison.m - lots of printouts when the database loses its
integrity (useful for debugging).

count.m - creates depth-k context counts for finite alphabet.

d_update.m - computes possible changes in distortion for different
possible new symbols; this is run before counts_update_all.m but
could be grouped together. The code is highly vectorized, yet short
and not difficult to understand.

distortion.m - computes distortion between sequences. Used in encoder
at the beginning and to verify integrity of data structures.

entropy.m - computes per-context entropy. Redundancy for unknown
conditional empirical statistics is not accounted for, and so this
is a slight under-estimate of actual coding length.

H_m.m - computes conditional empirical entropy for entire matrix m of 
context counts (entire sequence).

initz.m - initializes z sequence from x based on some heuristic.

moments.m - computes moments of the form X^m_alpha that appear
in DCC 2010 paper; used for fast update of distortion despite
change in mapping that appears for many symbols.

