On the Construction of an Antidictionary of a Binary String with Linear Complexity
Takahiro Ota, Hiroyoshi Morita · 2006
An antidictionary of a binary string is a set of 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 for a binary string 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