Title :
Straight-Line Programs: A Practical Test
Author :
Burmistrov, Ivan ; Khvorost, Lesha
Author_Institution :
Fac. of Math. & Mech., Ural State Univ., Ekaterinburg, Russia
Abstract :
We present an improvement of Rytter´s algorithm that constructs a straight-line program for a given text and show that the improved algorithm is optimal in the worst case with respect to the number of AVL-tree rotations. Also we compare Rytter´s and ours algorithms on various data sets and provide a comparative analysis of compression ratio achieved by these algorithms, by LZ77 and by LZW.
Keywords :
data compression; string matching; text analysis; tree data structures; AVL-tree rotation; LZ-compression; LZ77 encoding algorithm; LZW encoding algorithm; Rytter algorithm; compression ratio; data sets; straight-line programs; Algorithm design and analysis; Approximation algorithms; DNA; Estimation; Grammar; Indexes; Vegetation; AVL-tree; LZ-compression; straight-line program;
Conference_Titel :
Data Compression, Communications and Processing (CCP), 2011 First International Conference on
Conference_Location :
Palinuro
Print_ISBN :
978-1-4577-1458-0
Electronic_ISBN :
978-0-7695-4528-8
