On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree

Takahiro OTA; Hiroyoshi MORITA

doi:10.1093/ietfec/e90-a.11.2533

On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree

Takahiro OTA, Hiroyoshi MORITA

Full Text Views

0

Cite this

Summary :

The antidictionary of a string is the set of all words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.11 pp.2533-2539

Publication Date: 2007/11/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.11.2533

Type of Manuscript: PAPER

Category: Algorithms and Data Structures

Cite this

Copy

Takahiro OTA, Hiroyoshi MORITA, "On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 11, pp. 2533-2539, November 2007, doi: 10.1093/ietfec/e90-a.11.2533.
Abstract: The antidictionary of a string is the set of all words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.11.2533/_p

Copy

@ARTICLE{e90-a_11_2533,
author={Takahiro OTA, Hiroyoshi MORITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree},
year={2007},
volume={E90-A},
number={11},
pages={2533-2539},
abstract={The antidictionary of a string is the set of all words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.},
keywords={},
doi={10.1093/ietfec/e90-a.11.2533},
ISSN={1745-1337},
month={November},}

Copy

TY - JOUR
TI - On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2533
EP - 2539
AU - Takahiro OTA
AU - Hiroyoshi MORITA
PY - 2007
DO - 10.1093/ietfec/e90-a.11.2533
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 2007
AB - The antidictionary of a string is the set of all words of minimal length that never appear in this string. Antidictionaries are in particular useful for source coding. We present a fast and memory-efficient algorithm to construct an antidictionary using a suffix tree. It is proved that the complexity of this algorithm is linear in space and time, and its effectiveness is demonstrated by simulation results.
ER -