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

Takahiro OTA  Hiroyoshi MORITA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E90-A   No.11   pp.2533-2539
Publication Date: 2007/11/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e90-a.11.2533
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
antidictionary,  minimal forbidden word,  suffix tree,  directed acyclic word graph,  linear,  source coding,  

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

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.