Fractal compression rate curves in lossless compression of balanced trees
Sang-youn Oh, John C. Kieffer · 2010
Let α be an integer ≥ 2. We define a finite rooted oriented tree to be α-balanced if (1) there is no vertex with > α children, (2) for each vertex having exactly α children, the subtrees rooted at these children have numbers of leaves differing by at most 1, and (3) each child of each internal vertex withα(n) be logarithm to base two of the number of α-balanced trees having n leaves, which is roughly the codeword length needed to losslessly compress these trees via fixed-length binary codewords. Let {{x}} J denote the fractional part of x. The compression rate curve Cαis defined to be the set of limit points of the set of points of form ({{logαn}}, Hα(n)/n). Two results about Cαare presented. The first result is that Cαis the graph of a unique real-valued nonconstant continuous function defined on [0,1]. The second result is that Cαis a 2-D fractal which is the attractor of an iterated function system S(α) consisting of α piecewise contractive 2-D mappings. For α = 2, 3, 4, we illustrate how a large number of points on Cαcan be rapidly generated via S(α).