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

نویسندگان
Naeini, Hojjat ID 1
Kazemi, Ramin ID 2
Behzadi, Mohammad Hasan ID 3

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

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

doi
10.22052/mir.2021.240429.1263
چکیده

‎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‎.

کلیدواژه‌ها
Lempel-Ziv parsing algorithm, phrases, digital search tree, moment