A Compact Tree Representation of an Antidictionary
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1973-1984
- Publication Date
- 2017/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1973
- Type of Manuscript
- PAPER
- Category
- Information Theory
Authors
Takahiro OTA
Nagano Prefectural Institute of Technology
Hiroyoshi MORITA
The University of Electro-Communications
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takahiro OTA, Hiroyoshi MORITA, "A Compact Tree Representation of an Antidictionary" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 9, pp. 1973-1984, September 2017, doi: 10.1587/transfun.E100.A.1973.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1973/_p
Copy
@ARTICLE{e100-a_9_1973,
author={Takahiro OTA, Hiroyoshi MORITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Compact Tree Representation of an Antidictionary},
year={2017},
volume={E100-A},
number={9},
pages={1973-1984},
abstract={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.},
keywords={},
doi={10.1587/transfun.E100.A.1973},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - A Compact Tree Representation of an Antidictionary
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1973
EP - 1984
AU - Takahiro OTA
AU - Hiroyoshi MORITA
PY - 2017
DO - 10.1587/transfun.E100.A.1973
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - 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.
ER -
English
