Compression by Substring Enumerationデータ圧縮法の効率的実現

摘要

2010年にDubeとBeaudoinによって提案された無歪みデータ圧縮法Compression by Substring Enumeration(CSE)について，興味深い性質が徐々に明らかになっている．一方，明らかなむだがあることが指摘されている．むだの一種として，入力記号列が一意に特定できる符号語が出力されたあとも過剰に符号語を出力することがある．本論文では，そのようなむだと実装上のむだとを統一的な視点で解消する方法を提案する．また，提案法が原論文の方法より劣ることがないことを示す．