Skip to Main content Skip to Navigation
Conference papers

Text 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. Our algorithms can also be presented as "compilers" that create compressors dedicated to any previously fixed source. The techniques used in this paper are from Information Theory and Finite Automata.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619991
Contributor : Maxime Crochemore <>
Submitted on : Wednesday, March 20, 2013 - 7:08:23 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Friday, June 21, 2013 - 2:55:10 AM

File

9806-TC.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Maxime Crochemore, Filippo Mignosi, Antonio Restivo, Sergio Salemi. Text Compression Using Antidictionaries. International Conference on Automata, Languages an Programming (Prague, 1999), 1999, France. pp.261-270, ⟨10.1007/3-540-48523-6_23⟩. ⟨hal-00619991⟩

Share

Metrics

Record views

353

Files downloads

604