On the construction of an antidictionary with linear complexity using the suffix tree
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.
antidictionary linear suffix tree source coding minimal forbidden word directed acyclic word graph