Efficient data compression by straight-line programs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 45-68
Voir la notice de l'article provenant de la source Math-Net.Ru
We present two algorithms that construct a context-free grammar for a given text. The first one is an improvement of Rytter's algorithm that constructs grammar using AVL-trees. The second one is a new approach that constructs grammar using cartesian trees. Also we compare both algorithms and Rytter's algorithm on various data sets and provide a comparative analysis of compression ratio achieved by these algorithms, by LZ77 and by LZW.
@article{ZNSL_2012_402_a3,
author = {I. S. Burmistrov and A. V. Kozlova and E. B. Kurpilyansky and A. A. Khvorost},
title = {Efficient data compression by straight-line programs},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {45--68},
publisher = {mathdoc},
volume = {402},
year = {2012},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a3/}
}
TY - JOUR AU - I. S. Burmistrov AU - A. V. Kozlova AU - E. B. Kurpilyansky AU - A. A. Khvorost TI - Efficient data compression by straight-line programs JO - Zapiski Nauchnykh Seminarov POMI PY - 2012 SP - 45 EP - 68 VL - 402 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a3/ LA - ru ID - ZNSL_2012_402_a3 ER -
%0 Journal Article %A I. S. Burmistrov %A A. V. Kozlova %A E. B. Kurpilyansky %A A. A. Khvorost %T Efficient data compression by straight-line programs %J Zapiski Nauchnykh Seminarov POMI %D 2012 %P 45-68 %V 402 %I mathdoc %U http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a3/ %G ru %F ZNSL_2012_402_a3
I. S. Burmistrov; A. V. Kozlova; E. B. Kurpilyansky; A. A. Khvorost. Efficient data compression by straight-line programs. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 45-68. http://geodesic.mathdoc.fr/item/ZNSL_2012_402_a3/