Worst-case analysis of the Iterated Longest Fragment algorithm

For parallel machine architecture the Iterated Longest Fragment algorithm w as investigated by Stauffer and Hirschberg [Proc. 8th Int. Parallel Process . Symp., 1994, pp. 344-348] for compressing a text with a static dictionary . Later Nagumo, Lu and Watson [Inform. Process. Lett. 59 (1996) 91-96] prov ed that the algorithm can be implemented in an on-line way for the classica l architecture as well. Beside some experimental results the efficiency of the algorithm has not been analyzed yet. In this paper we will investigate the asymptotic worst-case behaviour of the ILF algorithm for several types of static dictionaries. (C) 2001 Elsevier Science B.V. All rights reserved.