Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2005

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: de Bruijn words

Sortuj według:

Ogranicz wyniki do:

Fast Data Compression with Antidictionaries

Davidson M., Ilie L.

Fundamenta Informaticae

2005

Vol. 64, nr 1-4

119-134

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.