On the temporal HZY compression scheme
Zacharie Cohen, Yossi Matias, Subramanian Muthukrishnan, S. Cenk Sahinalp, J. Ziv · Symposium on Discrete Algorithms · 2000
Z. Cohen Y. Matias y S. Muthukrishnan z S. C. S. ahinalp x J. Ziv { The HZY compression scheme. We consider ( ; )-HZY compression scheme with temporal ordering. Given an input string T = T [1 : n] from a constant sized alphabet, the ( ; )-HZY scheme compresses T as follows. T is partitioned into disjoint blocks (substrings) of size , T [1 : ]; T [ + 1 : 2 ]; : : :. For 1 k n= , the kth block T [(k 1) + 1 : k ] is then replaced by its codeword Ck, which is the integer pair (x; y); here (i) x , is the size of the context T [(k 1) x : (k 1) ] where T [(k 1) x : k ] is the longest suffix of T [1 : k ] occurring in T [1 : (k 1) ], and (ii) y is the temporal rank of the blockT [(k 1) +1 : k ] defined to be the number of distinct occurrences of the context T [(k 1) x : (k 1) ] between the leftmost occurrence of T [(k 1) x : k ] and its current occurrence. (When counting the number distinct occurrences of a context we only consider its occurrences with distinct blocks following it.) Comments on the HZY compression scheme. The HZY scheme given above is a context-based compression method recently proposed in [HZ98] and independently in [Yok95]. It is a one-pass algorithm as the codeword of a given block T [(k 1) + 1 : k ] depends only on the “past”, i.e., T [1 : (k 1) ]. The critical values of the parameters identified in these works are: = O(1) in [Yok95]; = O(log logn) and = O(logn) in [HZ98]. Also, 2 must hold in order to have compression. A detailed analysis of this scheme is provided in [HZ98], which shows that on any input generated by a stationary ergodic source, the output of the temporal HZY scheme converges to the conditional entropy of that source. No other one-pass compression scheme is known to be optimal under this refined notion of information content which makes this HZY scheme attractive. (See [HZ98] for further details.) Our Results. (i) We provide a tighter and more general bound on the compression attained by the HZY scheme with temporal ordering, (ii) we give the first known efficient algorithm for implementing the scheme, and (iii) we provide Dept of EE, Technion, Israel; [email protected]. yDept of CS, Tel-Aviv University, Israel; supported by Alon Fellowship, the Israel Science Foundation, and the Israeli Ministry of Science; [email protected]. zATT [email protected]. xDept of EECS, Case Western Reserve University; [email protected]. {Department of EE, Technion, Israel; [email protected]. some preliminary experimental results that are promising. Analysis of the compression ratio attained by the HZY scheme. Our analysis here is for binary strings. Consider the string T [ n : ] = T [ n]; : : : ; T [0]; : : : ; T [ ], a sliding-window of length n + over the infinite string T = : : : ; T [0]; : : :; T [ ]. For any = 1; 2; 3; : : : ; O(logn), let EL(T [1 : ] j T [ n : 0]) be the expected number of bits to represent the codeword for block T [1 : ] (in T [ n : 0]). Theorem. EL(C(T [1 : ]) j T [ n : 0]) H(T [1 : ] j T [ t : 0]) + 2 log tmax + O(log logn). Here t = t(T [ n : ]) denotes the context of block T [1 : ], i.e., the largest integer j = 1; 2; : : : such that T [ j i : i] = T [ j : ] for some i = 1; 2; : : :; n j, and tmax denotes maximum context size . Proof. (sketch) H(T [1 : ] j T [ t : 0]) = H(T [1 : ]; i = t j T [ t : 0]) H(i = t j T [ i : 0]). For every integer 0 i tmax, let NT (T [1 : ]; i = t j T [ i : 0]) be the first occurrence of T [1 : ]; i = t among all instances in T with the suffix T [ i : 0]. Then by the conditional Kac’s Lemma proven in [HZ98]: E[NT (T [1 : ]; i = t j T [ i : 0]) j T [ i : 1]; i = t] = 1=P (T [1 : ]; i = t j T [ i : 0]). Thus, by the convexity of the logarithmic function E log(NT (T [1 : ]; i = t j T [ i : 0]) j T [ i : 0]) H(T [1 : ]; i = t j T [ i : 0]). Therefore, E log(NT [ n: ](T [1 : ] j T [ t : 0])) H(T [1 : ]; i = t j T [ t : 0]). But it is possible to generate a universally decodable code for NT [ n: ](T [1 : ] j T [ t : 0]) whose length (in terms of number of bits) is no more than log tmax+logNT [ n: ](T [1 : ] j T [ t : 0])+O(log logn) (or log tmax + logmini=1;:::;tNT [ n: ](T [1 : ] j T [ i : 0]) +O(log logn)). This theorem is valid for any = O(logn) hence is more general than the analysis provided in [HZ98] (which has the requirement that = o(logn) and log logn = o( )). Also, our bounds are tighter and simpler to prove. Corollary. It was demonstrated in [HZ98] that there exists ergodic sources for which, for any universal noiseless encoder: EL(T [1 : ] j T [ n : 0]) H(T [1 : `] j T [ t : 0]) O(log logn). Thus, the HZY algorithm is optimal in a min-max sense. Efficient Algorithm for the HZY scheme. We present the first efficient algorithm for implementing the HZY scheme. At the high level, our algorithm works as follows. The string T is read left to right, block by block. Say the current block isBi = T [i : i+ 1]. The data structure we maintain is the