Evaluation of Maximum Redundancy of Data Compression via Substring Enumeration for k-th Order Markov Sources
Ken‐ichi Iwata, Mitsuharu Arimura, Yuki Shima · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2014
Dubé and Beaudoin proposed a lossless data compression called compression via substring enumeration (CSE) in 2010. We evaluate an upper bound of the number of bits used by the CSE technique to encode any binary string from an unknown member of a known class of k-th order Markov processes. We compare the worst case maximum redundancy obtained by the CSE technique for any binary string with the least possible value of the worst case maximum redundancy obtained by the best fixed-to-variable length code that satisfies the Kraft inequality.