UCSC-CRL-90-40: ON ADAPTATION TO MULTIPLE CONTEXT BINARY SOURCES

08/01/1990 09:00 AM
Computer Engineering
An introduction and entry into the literature of practical deterministic algorithms that adaptively estimate the relative frequency distribution of binary sequences is provided. Deterministic adaptation appraoches typically maintain and adjust a count ratio that is based on past symbols seen in the past sequence. Adapters are finite state machines and some algorithms use a small number of states by restricting the count numberator value, at a cost of wandering about the optimum index in the case of stationary sources. Issues of adaptation inertia (or speed) are covered. A performance measure of Rissanen and Langdon, the ideal code length IL(M,F) of the data file F under a given context model M, is supplemented by another closed form code length estimator, the enumerative code length EL(M,F) of Cleary and Witten. The novel application of IL or EL to calculate the information content of the binary adapter output allows a new means of comparison of the context model and adaptive statistics model. The binary adapter treatment includes results from reports not generally known or available. Wandering binary adapters are defined, then described in the statistical significance testing metaphor, and designs are presented that employ a simple wandering heuristic. A simple example illustrates the mean- median anomaly that differentiates significance testing on a count ratio random variable versus a runlength random variable. Goladap, an adaptive Golomb code, uses the Golomb coding operation itself as a trigger for adaptation, and the runlength variable for adaptation.

This report is not available for download at this time.