Data compression using antidictionaries

Abstract : We give a new text-compression scheme based on forbidden words ("antidictionary"). We prove that our algorithms attain the entropy for balanced binary sources. They run in linear time. Moreover, one of the main advantages of this approach is that it produces very fast decompressors. A second advantage is a synchronization property that is helpful to search compressed data and allows parallel compression. The techniques used in this paper are from information theory and finite automata.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619579
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, February 13, 2013 - 6:14:43 PM
Last modification on : Tuesday, October 30, 2018 - 5:04:09 PM
Long-term archiving on : Tuesday, May 14, 2013 - 2:55:09 AM

File

0007-DCA.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, Filippo Mignosi, Antonio Restivo, Sergio Salemi. Data compression using antidictionaries. Proceedings of the I.E.E.E., 2000, 88 (11), pp.1756-1768. ⟨10.1109/5.892711⟩. ⟨hal-00619579⟩

Share

Metrics

Record views

234

Files downloads

234