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

zbMATH Open1469.60094arXiv2003.05500MaRDI QIDQ4989421FDOQ4989421

Authors: Jérôme Rousseau 

Publication date: 25 May 2021

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.

Full work available at URL: https://arxiv.org/abs/2003.05500

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

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)

Cites Work

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

Cited In (1)

• Title not available (Why is that?)

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)