loading...
Simple Linear-Time Off-Line Text Compression by Longest-First Substitution
Snowbird, Utah March 27-March 29
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2007.702007 Data Compression Conference (DCC ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ryosuke Nakamura, Kyushu University
Hideo Bannai, Kyushu University
Shunsuke Inenaga, Kyushu University
Masayuki Takeda, Kyushu University
We consider grammar based text compression with longest first substitution, where non-overlapping occurrences of a longest repeating substring of the input text are replaced by a new non-terminal symbol. We present a new text compression algorithm by simplifying the algorithm presented in [dl. We give a new formulation of the correctness proof introducing the sparse lazy sufix tree data structure. We also present another type of longest first substitution strategy that allows better compression. W e show results of preliminary experiments comparing grammar sizes of the two versions of the longest first strategy and the most frequent strategy.
Citation:
Ryosuke Nakamura, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, "Simple Linear-Time Off-Line Text Compression by Longest-First Substitution," dcc, pp.123-132, 2007 Data Compression Conference (DCC'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.