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. |
Year | Venue | Keywords |
---|---|---|
1999 | ICALP | new text compression scheme,synchronization property,main advantage,information theory,fast decompressors,parallel compression,text compression,linear time,balanced binary source,finite automata,forbidden words,finite automaton,pattern matching,data compression |
Field | DocType | ISBN |
Information theory,Synchronization,Computer science,Algorithm,Theoretical computer science,Finite-state machine,Data compression,Time complexity,Pattern matching,Parallel compression,Binary number | Conference | 3-540-66224-3 |
Citations | PageRank | References |
18 | 2.10 | 6 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maxime Crochemore | 1 | 2655 | 281.75 |
Filippo Mignosi | 2 | 569 | 99.71 |
Antonio Restivo | 3 | 697 | 107.05 |
Sergio Salemi | 4 | 145 | 41.24 |