A Compact Tree Representation of an Antidictionary

Takahiro OTA  Hiroyoshi MORITA  

Publication
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
Type of Manuscript: PAPER
Category: Information Theory
Keyword: 
antidictionary,  universal source coding,  two-pass,  compression via substring enumeration,  circular string,  tree,  

Full Text: PDF(420.6KB)
>>Buy this Article


Summary: 
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.