loading...
Compressed by the Suffix Tree
Snowbird, Utah March 28-March 30
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2006.11Data Compression Conference (DCC'06)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Martin Senft, Charles University, Czech Republic
A close inspection of Fiala and Green?s implementation of Ziv-Lempel?77 dictionary compression method reveals a surprising inefficiency: The match they are searching for from the root down the suffix tree can be obtained for free from the suffix tree construction algorithm! This observation suggests that the output of this compression method is in a way just a description of the suffix tree construction for the input string. If taken one step further this leads to the idea that there exists a whole family of compression methods replacing the input string with a description of the suffix tree construction for this string. This family contains some (multi-)dictionary methods not dissimilar to those of Bloom or Hoang et.al., as well as some Prediction by Partial Matching variants. We give the general description of this family along with details about some of its members, discuss implementation issues and show some early experimental results. A possible application to other suffix structures like the Compact Directed Acyclic
Citation:
Martin Senft, "Compressed by the Suffix Tree," dcc, pp.183-192, Data Compression Conference (DCC'06), 2006
Usage of this product signifies your acceptance of the Terms of Use.