The redundancy of universal lossy data compression for discrete memoryless sources is considered in terms of type and d-ball covering. It is shown that there exists a universal d-semifaithful code whose rate redundancy is upper bounded by (A-1/2)n-1ln n+o(n-1ln n), where A is the cardinality of source alphabet and n is the block length of the code. This new bound is tighter than known ones, and moreover, it turns out to be the attainable minimum of the universal coding proposed by Davisson.

Let {Xk}k=- be a stationary and ergodic information source, where each Xk takes values in a standard alphabet A with a distance function d: A A [0, ) defined on it. For each sample sequence X = (, x-1, x0, x1, ) and D > 0 let the approximate D-match recurrence time be defined by Rn (x, D) = min {m n: dn (Xn1, Xm+nm+1) D}, where Xji denotes the string xixi+1 xj and dn: An An [0, ) is a metric of An induced by d for each n. Let R (D) be the rate distortion function of the source {Xk}k=- relative to the fidelity criterion {dn}. Then it is shown that lim supn-1/n log Rn (X, D) R (D/2) a. s.