For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Compact Tree Representation of an Antidictionary
Takahiro OTA Hiroyoshi MORITA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2017/09/01
Online ISSN: 1745-1337
Type of Manuscript: PAPER
Category: Information Theory
antidictionary, universal source coding, two-pass, compression via substring enumeration, circular string, tree,
Full Text: PDF(420.6KB)
>>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.