Lossless Data Compression via Substring Enumerationのマルコフ情報源に対する最悪冗長度

摘要

DubeとBeaudoinはCompression via Substring Enumeration（CSE）と呼ばれるユニバーサル無歪みデータ圧縮法を2010年に提案した．本稿では，た次マルコフ情報源からの任意の個別系列に対してCSE符号化を行った場合の冗長度の上界について評価する．その結果，CSEの個別最悪冗長度とクラフトの不等式を満たす最適な固定長－可変長符号で達成可能な最悪冗長度の差は，符号化する系列長れに対して，高々logn程度であることを明らかにする．