Fast Data Compression with Antidictionaries

• Autorzy: Davidson M. , Ilie L.
• Języki publikacji: EN

Abstrakty

EN

We consider the data compression using antidictionaries and give algorithms for faster compression and decompression. While the original method of Crochemore et al. uses finite transducers with e-moves, we (de)compress using e-free transducers. This is provably faster, assuming data non-negligibly compressible, but we have to consider the overhead due to building the new machines. In general, they can be quadratic in size compared to the ones allowing e-moves; we prove this bound optimal as it is reached for de Bruijn words. However, in practice, the size of the e-free machines turns out to be close to the size of the ones allowing e-moves and therefore we can achieve significantly faster (de)compression. We show our results for the files in Calgary corpus.

Słowa kluczowe

EN

text compression; antidictionaries; e-free transducers; de Bruijn words

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 119--134
• Opis fizyczny: Biblogr. 9 poz., tab., wykr.

Twórcy

autor

Davidson M.

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada

autor

Ilie L.

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada

Bibliografia

• [1] A. Aho, M. Corasick, Efficient string matching: An aid to bibliographic search, Comm. ACM, 18, 6 (1975), 333–340.
• [2] N.G. de Bruijn, A combinatorial problem, Proc. Kon. Ned. Akad. Wetensch., 49 (1946), 758–764.
• [3] M. Crochemore, C. Hancart, Automata for pattern matching, in: G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, Vol. II, Springer-Verlag, Berlin, 1997, 399–462.
• [4] M. Crochemore, F. Mignosi, A. Restivo, S. Salemi, Text compression using antidictionaries, in: J. Wiedermann, P. van Emde Boas and M. Nielsen, eds., Proc. of ICALP’99, LNCS 1644, Springer-Verlag, Berlin, 1999, 261–270.
• [5] M. Crochemore, F. Mignosi, A. Restivo, S. Salemi, Data compression using antidictionaries, in: J. Storer, ed., I.E.E.E. Special Issue on Lossless Data Compression, 88, 11 (2000), 1756–1768.
• [6] A. Lempel, J. Ziv, On the complexity of finite sequences IEEE Trans. Information Theory, 22, 1 (1976), 75–81.
• [7] S. Marcus, Contextual grammars and natural languages, in: G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, Vol. II, Springer-Verlag, Berlin, 1997, 215–235,
• [8] Gh. Päun, Marcus Contextual Grammars, Kluwer Academic Publishers, Dordrecht, 1997.
• [9] Y. Shibata,M. Takeda, A. Shinohara, S. Arikawa, Pattern matching in text compressed by using antidictionaries, in: M. Crochemore, M. Paterson, eds., Proceedings of CPM’99, LNCS 1645, Springer-Verlag, Berlin, 1999, 37–49.