Abstract

We consider the parsing method to be used in dynamic dictionary based data compression. We show that (1) the commonly used greedy parsing may result in far from optimal compression with respect to the dictionary in use; (2) a one-consider whether there is an efficient dynamic parsing lookahead greedy parsing scheme obtains optimality with remethod that achieves optimality with respect to this spect to any dictionary construction schemesthat satisfy the scheme on all input strings. We call a parsing method prefix property; and (3) there is a data structure which en-optimal with respect to a given dictionary construction ables efficient on-line implementation method.