A Note on the Lempel-Ziv Parsing Algorithm under Asymmetric Bernoulli‎ ‎Model

Document Type : Original Scientific Paper

Authors

1 Department of Statistics, Science and Research Branch, Islamic Azad University, Tehran, I. R. Iran

2 Department of Statistics, Imam Khomeini International University, Qazvin, I. R. Iran

Abstract

‎In this paper‎, ‎by applying analytic‎ ‎combinatorics‎, ‎we obtain an asymptotics for the t-th moment‎ ‎of the number of phrases of length l in the Lempel-Ziv parsing algorithms built over a string generated by an asymmetric Bernoulli‎ ‎model‎. We show that the t-th moment is approximated by its Poisson transform‎.

Keywords

References

[1] J. E. Coffman and J. Eve, File structures using hashing functions, Commun.
ACM 13 (1970) 427–432.
[2] M. Drmota and W. Szpankowski, Un(expected) behavior of digital search tree
profile, SIAM (2009) 130–138.
[3] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University
Press, Cambridge, 2008.
[4] E. Gilbert and T. Kadota, The Lempel-Ziv algorithm and message complexity,
IEEE Trans. Inform. Theory 38 (1992) 1839–1842.
[5] P. Jacquet and W. Szpankowski, Asymptotic behavior of the Lempel-Ziv pars-
ing scheme and [in] digital search trees, Theor. Comput. Sci. 144 (1-2) (1995)
161–197.
[6] R. Kazemi, On the phrases in Lempel-Ziv parsing algorithm, Int. J. Aca. Res.
(IJAR) 4 (4) (2012) 112–115.
[7] R. Kazemi and M. Q. Vahidi-Asl, The variance of the profile in digital search
trees, Discrete Math. Theor. Comput. Sci. 13 (3) (2011) 21–38.
[8] P. Kirschenhofer, H. Prodinger and W. Szpankowski, On the variance of the
external path in a aymmetric digital search trie, Discrete Appl. Math. 25
(1989) 129–143.
[9] A. Lempel and J. Ziv, On the complexity of finite sequences, IEEE Inform.
Theory 22 (1) (1976) 75–81.
[10] G. Louchard and W. Szpankowski, Average profile and limiting distribution
for a phrase size in the Lempel-Ziv parsing algorithm, IEEE Trans. Inform.
Theory 41 (1995) 478–488.
[11] G. Park, H. K. Hwang, P. Nicodeme and W. Szpankowski, Profile of tries,
SIAM J. Comput. 8 (2009) 1821–1880.
[12] A. Wyner and J. Ziv, Some asymptotic properties of the entropy of a station-
ary ergodic data source with applications to data compression, IEEE Trans.
Inform. Theory 35 (1989) 1250–1258.
[13] J. Ziv, On classification with empirically observed statistics and universal
data compression, IEEE Trans. Inform. Theory 34 (1988) 278–286.
[14] J. Ziv, Compression, Test of Randomness, and Estimating the Statistical
Model of Individual Sequence–Sequences, Combinatorics, Compression, Secu-
rity, and Transmission. Ed. by R. M. Capocelli, Springer-Verlag, New York,
1990, pp. 366–373.
[15] J. Ziv and A. Lempel, Compression of individual sequences via variable-rate
coding, IEEE Trans. Inform. Theory 24 (5) (1978) 530–536.
Mathematics Interdisciplinary Research
Volume 6, Issue 3
September 2021
Pages 215-223

Files

Share

How to cite

Statistics