Geodesic
Efficient data compression by straight-line programs
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part IV, Tome 402 (2012), pp. 45-68 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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},
     year = {2012},
     volume = {402},
     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
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
%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/

[1] D. Knut, Iskusstvo programmirovaniya, v. 3, Sortirovka i poisk, 2-e izd., “Vilyams”, M., 2007

[2] A. Polozov, Dekartovo derevo: Chast 3. Dekartovo derevo po neyavnomu klyuchu, Elektronnyi resurs, http://habrahabr.ru/blogs/algorithm/102364/

[3] A. Apostolico, G. M. Landau, S. Skiena, “Matching for Run-Length Encoded Strings”, J. Complexity, 15 (1999), 4–16 | DOI | MR | Zbl

[4] I. Burmistrov, L. Khvorost, “Straight-line programs: a practical test”, Proc. Int. Conf. Data Compression, Commun., Process., CCP, 2011, 76–81 | DOI

[5] M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, A. Shelat, “The smallest grammar problem”, IEEE Trans. Information Theory, 51 (2005), 2554–2576 | DOI | MR | Zbl

[6] T. Kida, T. Matsumoto, Y. Shibata, M. Takeda, A. Shinohara, S. Arikawa, “Collage system: a unifying framework for compressed pattern matching”, Theor. Comput. Sci., 298 (2003), 253–272 | DOI | MR | Zbl

[7] Y. Lifshits, “Processing compressed texts: A tractability border”, Lect. Notes Comput. Sci., 4580, 2007, 228–240 | DOI | Zbl

[8] W. Matsubara, S. Inenaga, A. Ishino, A. Shinohara, T. Nakamura, K. Hashimoto, “Computing longest common substring and all palindromes from compressed strings”, Lect. Notes Comput. Sci., 4910, 2008, 364–375 | DOI | Zbl

[9] W. Rytter, “Application of Lempel–Ziv factorization to the approximation of grammar-based compression”, Theor. Comput. Sci., 302 (2003), 211–222 | DOI | MR | Zbl

[10] R. Seidel, C. Aragon, “Randomized search trees”, Algorithmica, 16 (1996), 464–497 | DOI | MR | Zbl

[11] Y. Shibata, M. Takeda, A. Shinohara, S. Arikawa, “Pattern matching in text compressed by using antidictionaries”, Lect. Notes Comput. Sci., 1645, 1999, 37–49 | DOI | MR | Zbl

[12] A. Tiskin, “Faster subsequence recognition in compressed strings”, J. Math. Sci., 158 (2009), 759–769 | DOI | MR | Zbl

[13] T. Welch, “A technique for high-performance data compression”, IEEE Computer, 17 (1984), 8–19 | DOI

[14] J. Ziv, A. Lempel, “A universal algorithm for sequential data compression”, IEEE Trans. Information Theory, 23 (1977), 337–343 | DOI | MR | Zbl

[15] J. Ziv, A. Lempel, “Compression of individual sequences via variable-rate coding”, IEEE Trans. Information Theory, 24 (1978), 530–536 | DOI | MR | Zbl