Worst-case analysis of the Iterated Longest Fragment algorithm

Citation
J. Bekesi et G. Galambos, Worst-case analysis of the Iterated Longest Fragment algorithm, INF PROCESS, 79(3), 2001, pp. 147-153
Citations number
10
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
0020-0190 → ACNP
Volume
79
Issue
3
Year of publication
2001
Pages
147 - 153
Database
ISI
SICI code
0020-0190(20010731)79:3<147:WAOTIL>2.0.ZU;2-T
Abstract
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.