Please login using the form on menu list.|
It is required to login for Full-Text PDF.
On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree
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
minimal forbidden word,
directed acyclic word graph,
Full Text: PDF(250.2KB)
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.