A Compact Tree Representation of an Antidictionary

Takahiro OTA  Hiroyoshi MORITA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.9   pp.1973-1984
Publication Date: 2017/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.1973
Type of Manuscript: PAPER
Category: Information Theory
antidictionary,  universal source coding,  two-pass,  compression via substring enumeration,  circular string,  tree,  

Full Text: PDF>>
Buy this Article

In both theoretical analysis and practical use for an antidictionary coding algorithm, an important problem is how to encode an antidictionary of an input source. This paper presents a proposal for a compact tree representation of an antidictionary built from a circular string for an input source. We use a technique for encoding a tree in the compression via substring enumeration to encode a tree representation of the antidictionary. Moreover, we propose a new two-pass universal antidictionary coding algorithm by means of the proposal tree representation. We prove that the proposed algorithm is asymptotic optimal for a stationary ergodic source.