The zeroth order empirical entropy (see [1]}, [2]}) of \(T[1,n]\)  is defined as \(H_0(T) = \sum _{c \in \Sigma } \frac{n_c}{n} \log \frac{n}{n_c}\) , where \(n_c\)  is the number of symbols \(c\)  in \(T\)  and \(\frac{n_c}{n}\log \frac{n}{n_c} = 0\)  whenever \(n_c = 0\) . For a string \(W\) , let \(T_W\)  be a string formed by concatenating all symbols immediately following occurrences of \(W\)  in \(T[1,n]\) ; e.g., \(T_{ab} = aac\)  for \(T = abababc\) . The \(k\) th order empirical entropy of \(T[1,n]\)  is defined as \(H_k(T) = \sum _{W \in \Sigma ^k} \frac{|T_W|}{n} H_0(T_W)\) , where \(\Sigma ^k\)  is the set of all strings of length \(k\)  over \(\Sigma \)  (see [1]}, [4]}, [2]}). If \(T\)  is clear from the context, \(H_k(T)\)  is denoted by \(H_k\) . It is well known that \(\log \sigma \ge H_0 \ge H_1 \ge \cdots \)  and \(H_k\)  makes sense as a measure of string compression only for \(k < \log _\sigma n\)  (see [6]} for a deep discussion).
