Rényi entropy and pattern matching for run-length encoded sequences

MaRDI QIDQ4989421zbMATH OpenFDO

Authors Jérôme Rousseau

Publication date 25 May 2021

Full work available at URL https://arxiv.org/abs/2003.05500, http://alea.impa.br/articles/v18/18-32.pdf

zbMATH Keywords

data compressionstring matchinglongest common substringmixing processRényi entropy

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Measures of information, entropy (94A17) Stationary stochastic processes (60G10) Ergodicity, mixing, rates of mixing (37A25) Strong limit theorems (60F15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: In this note, we studied the asymptotic behaviour of the length of the longest common substring for run-length encoded sequences. When the original sequences are generated by an $alpha$-mixing process with exponential decay (or $psi$-mixing with polynomial decay), we proved that this length grows logarithmically with a coefficient depending on the R'enyi entropy of the pushforward measure. For Bernoulli processes and Markov chains, this coefficient is computed explicitly.

Recommendations

• Matching strings in encoded sequences
• Longest common substring for random subshifts of finite type
• Critical phenomena in sequence matching
• String matching: The ergodic case
• The rate of convergence of the mean length of the longest common subsequence

Cites work

• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• scientific article; zbMATH DE number 1139639 (Why is no real title available?)
• scientific article; zbMATH DE number 843255 (Why is no real title available?)
• scientific article; zbMATH DE number 934437 (Why is no real title available?)
• A Phase Transition for the Distribution of Matching Blocks
• A suboptimal lossy data compression based on approximate pattern matching
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Computation and Estimation of Generalized Entropy Rates for Denumerable Markov Chains
• Equilibrium states and the ergodic theory of Anosov diffeomorphisms
• Hardness of comparing two run-length encoded strings
• Introduction to strong mixing conditions. Vol. 3.
• Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
• Matching for run-length encoded strings
• Matching strings in encoded sequences
• Matching with shift for one-dimensional Gibbs measures
• Maximal Repetition and Zero Entropy Rate
• Mixing properties of ARMA processes
• Mixing: Properties and examples
• Nonparametric entropy estimation for stationary processes and random fields, with applications to English text
• On computing average common substring over run length encoded sequences
• On the Vocabulary of Grammar-Based Codes and the Logical Consistency of Texts
• On the shortest distance between orbits and the longest common substring problem
• Potential well spectrum and hitting time in renewal processes
• Ruelle's Operator Theorem and g-Measures
• Rényi Entropies and Large Deviations for the First Match Function
• Shortest distance between multiple orbits and generalized fractal dimensions
• The Rényi entropy function and the large deviation of short return times
• The Shortest Possible Return Time of <inline-formula> <tex-math notation="LaTeX">$\beta$ </tex-math> </inline-formula>-Mixing Processes

Cited in

(2)

• scientific article; zbMATH DE number 3876640 (Why is no real title available?)
• Matching strings in encoded sequences

This page was built for publication: Rényi entropy and pattern matching for run-length encoded sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989421)