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

Takahiro OTA  Hiroyoshi MORITA 

Publication
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
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Algorithms and Data Structures
Keyword: 
antidictionary,  minimal forbidden word,  suffix tree,  directed acyclic word graph,  linear,  source coding, 

Full Text: PDF(250.2KB)

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.