For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2007/11/01
Online ISSN: 1745-1337
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)>>
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.