On the Construction of an Antidictionary with Linear Complexity Using the Suffix Tree
T. OTA, H. MORITA · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2007
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.