Redundancy analysis in lossless compression of a binary tree via its minimal DAG representation

Let T denote the set of all structurally inequivalent finite rooted ordered binary trees. For each t ϵ e T, let D(t) be the unique minimal DAG representation of t, and let r(t) ϵ (0,1] be the ratio of the number of vertices of D(t) to the number of leaves oft. A lossless prefix encoder φ on {D(t) : t ϵ T} is proposed, and then a two-step lossless encoder φ* on T is defined by φ*(t) =^Δ φ(D(t)) for t ϵ T. Let γ be the function γ(x) =^Δ (x/2)log₂(2/x) for x ϵ (0,1]. It is shown that the normalized pointwise redundancy in encoding each t ϵ T via φ* is O(γ(r(t))). Furthermore, given a binary tree source whose output is a sequence of random trees growing in size, weak sufficient conditions on the source are presented under which the normalized average redundancy of φ* with respect to the source vanishes asymptotically. This result allows for the identification of some families of binary tree sources on which φ* acts as a universal code.